Prove that the sentence

( ∃ u ∀ v R ( u , v ) ) ∧ ( ∀ u ∃ v S ( u , v ) )

is logically equivalent to both

∃ u ∀ v ∃ w ( R ( u , v ) ∧ S ( v , w ) ).

and

∀ u ∃ v ∃ v' ∀ w ( R ( v' , w ) ∧ S ( u , v ) )

but not to

∀ u ∃ v ∀ w ( R ( v , w ) ∧ S ( u , v ) ) .

Let φ be a formula with distinct free variables u and v.

Prove that φ ( u / c ) ( v / d ) equals φ ( v / d ) ( u / c ).

- φ
^{*}is logically equivalent to φ and -
φ
^{*}is built up without the logical symbols ∨ , → , ↔ and ∀.

Suppose that π : | A | → | B | is a bijection such that:

c^{B}
= π ( c^{A} ) for every constant symbol c

F^{B} ( π ( x_{0} ) , … , π ( x_{n-1} ) )
=
π ( F^{A} ( x_{0} , … , x_{n-1} ) )
for every n-ary function symbol F and x̅ ∈ | A |^{n}

R^{B} ( π ( x_{0} ) , … , π ( x_{n-1} ) )
iff R^{A} ( x_{0} , … , x_{n-1} )
for every n-ary relation symbol R and
x̅ ∈ | A |^{n}

We call π and __isomorphism__ from A and B
and write π : A ≈ B.

Prove that for every formula φ ,
if φ has free variables u_{0}, … , u_{n-1},
then for all x̅ ∈ | A |^{n} ,

( B , π ( x_{0} ) , … , π ( x_{n-1} ) )
⊨ φ ( u_{0} / c_{π ( x0 )} )
⋅ ⋅ ⋅ ( u_{n-1} / c_{π ( xn-1 )} )

iff

( A , x_{0} , … , x_{n-1} )
⊨ φ ( u_{0} / c_{x0} )
⋅ ⋅ ⋅ (u_{n-1} / c_{xn-1} ).

Prove that for every sentence φ in this language, one of the following holds.

- There is a natural number m such that for all n ≥ m, if A is a structure of size n, then A ⊨ φ.
- There is a natural number m such that for all n ≥ m, if A is a structure of size n, then A ⊨ ¬ φ.

**Hint:** In this language, all countably infinite structures are
isomorphic.

Define δ_{1} to be the sentence ⊤.

For each natural number n ≥ 2,
define δ_{n} to be the conjunction of the formulas
¬ ( v_{i} ≈ v_{j} )
for 1 ≤ i < j ≤ n.

For each natural number n ≥ 1,
define ε_{n} to be the disjunction of
of the formulas
v_{0} ≈ v_{i}
for 1 ≤ i ≤ n.

For n ≥ 1, define ψ_{n} to be the sentence
∃
v_{1}
∃
v_{2}
⋅
⋅
⋅
∃
v_{n}
δ_{n}
.

For n ≥ 1, define χ_{n} to be the sentence
∃
v_{1}
⋅
⋅
⋅
∃
v_{n}
(
δ_{n}
∧
∀ v_{0}
ε_{n}
)
.

Let φ be a satisfiable sentence in this language.

Prove that there is a sentence φ^{*} such that

- φ
^{*}is is logically equivalent to φ and -
φ
^{*}is a disjunction of various sentences of the kinds ψ_{m}and χ_{n}.(Possibly with no disjuncts of one kind or the other.)

**Hint:** Intuitively, ψ_{n} says "there are at least n points"
and χ_{n} says "there are exactly n points".

Give an example of a theory Σ such that no finite theory has the same logical consequences as Σ.

Explain why your Σ has this property.

**Note:** This is stronger than saying no finite subtheory of Σ
has the same logical consequences.

Find a sentence φ such that both φ and ¬ φ have arbitrarily large finite models.

Explain why your φ has this property.

Find a satisfiable sentence that has no finite models.

- the notation
∃ u̅ abbreviates
∃ u
_{0}⋅ ⋅ ⋅ ∃ u_{n-1} - the notation
∀ u̅ abbreviates
∀ u
_{0}⋅ ⋅ ⋅ ∀ u_{n-1}

Prove that for every sentence, there is a logically equivalent sentence in one of the two forms:

∃ u̅^{0}
∀ u̅^{1}
⋅ ⋅ ⋅
**Q** u̅^{k}
ψ

∀ u̅^{0}
∃ u̅^{1}
⋅ ⋅ ⋅ **Q** u̅^{k}
ψ

where **Q** is either ∀ or ∃
depending on the parity of k
and ψ is quantifier-free.

(This is called __prenex__ normal form.)

Describe a computer algorithm to output all the logical consequences of Σ.

Assume Σ is complete.

Describe a computer algorithm that decides whether a sentence in the language of Σ is a logical consequence of Σ.

Prove that for every n ∈ ω,
there is a formula φ in the language of A with a free variable v
such that ( A , n )
⊨ ∀ v ( φ ↔ v ≈ c_{n} ).

Suppose π : | A | → Y is a bijection.

Find a structure B such that | B | = Y and π is an isomorphism from A to B.

**Part 1**

An __automorphism__ of a structure A is an isomorphism from A to A.

Describe all automorphisms of ( ℤ , < ).

**Part 2**

A set S ⊆ | A | is __definable over__ A
iff there is a formula φ in the language of A with free variable u
such that, for every x ∈ | A |,

x ∈ S
iff
( A , x ) ⊨ φ ( u / c_{x} ) .

Prove that ℤ and { } are the only subsets of ℤ that are definable over ( ℤ , < ) .

**Part 3**

A function f : | A | → | A | is said to be __definable over__ A
iff there is a formula φ in the language of A with free variables
are u and v, and, for all x , y ∈ | A |,

f ( x ) = y
iff
( A , x , y ) ⊨ φ ( u / c_{x} )
( v / c_{y} )

Prove that the shift functions,

x ↦ x + n

are the only functions from ℤ to ℤ that are definable over ( ℤ , < ) .

Use the Compactness Theorem to prove that there is a sentence φ such that Σ ⊨ φ and Τ ⊨ ¬ φ.

**Part 1**

Find a countable family { A_{i} ∣ i ∈ ω } of
structures such that:

| A_{i} | = ω for every i ∈ ω.

A_{i} and A_{j} are not isomorphic
for all distinct i , j ∈ ω.

For every countable infinite structure B in this language,
there exists i ∈ ω
such that B ≈ A_{i}.

**Part 2**

For each i ∈ ω,
find a consistent theory Σ_{i}
such that
every countable model of Σ_{i} is isomorphic to A_{i} .

**Part 3**

Prove that for every sentence in this language, there exists a logically equivalent sentence of the form

( ∃ u̅ ∀ v ψ_{0} )
∨ ⋅ ⋅ ⋅ ∨
( ∃ u̅ ∀ v ψ_{n-1} )

where each ψ_{m} is quantifier-free.

**Hint:** The idea is similar to Exercise 3.8.
In this language, you can express:

- " S
^{A}has at least n elements. " - " S
^{A}has exactly n elements. " - " | A | - S
^{A}has at least n elements. " - " | A | - S
^{A}has exactly n elements. "

Let { A_{i} ∣ i ∈ ω } be a countable family of structures.

Prove there exists a countable structure B such that,
for all i ∈ ω,
B is not isomorphic to A_{i}.

Let { A_{i} ∣ i ∈ ω } be a countable family of structures.

Prove there exists a countable structure B such that,
for all i ∈ ω,
B is not isomorphic to A_{i}.