© Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Exercises for Chapter 3

Exercise 3.1

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 ) ) .

Exercise 3.2

Exercise 3.3

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

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

Exercise 3.4

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

Exercise 3.5

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

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

    F^B ( π ( x₀ ) , … , π ( x_n-1 ) )   =   π ( F^A ( x₀ , … , x_n-1 ) )   for every n-ary function symbol F and x̅ ∈ | A |ⁿ

    R^B ( π ( x₀ ) , … , π ( x_n-1 ) )   iff   R^A ( x₀ , … , x_n-1 )   for every n-ary relation symbol R and x̅ ∈ | A |ⁿ

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

Prove that for every formula φ , if φ has free variables u₀, … , u_n-1, then for all x̅ ∈ | A |ⁿ ,

    ( B , π ( x₀ ) , … , π ( x_n-1 ) ) ⊨ φ ( u₀ / c_{π ( x0 )} ) ⋅ ⋅ ⋅ ( u_n-1 / c_{π ( xn-1 )} )

iff

    ( A , x₀ , … , x_n-1 ) ⊨ φ ( u₀ / c_x0 ) ⋅ ⋅ ⋅ (u_n-1 / c_xn-1 ).

Exercise 3.6

Exercise 3.7

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.

Exercise 3.8

Define δ₁ 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₀ ≈ v_i   for 1 ≤ i ≤ n.

For n ≥ 1, define ψ_n to be the sentence   ∃ v₁ ∃ v₂ ⋅ ⋅ ⋅ ∃ v_n   δ_n .

For n ≥ 1, define χ_n to be the sentence   ∃ v₁ ⋅ ⋅ ⋅ ∃ v_n   (   δ_n   ∧   ∀ v₀   ε_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".

Exercise 3.9

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.

Exercise 3.10

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

Explain why your φ has this property.

Exercise 3.11

Find a satisfiable sentence that has no finite models.

Exercise 3.12

• the notation ∃ u̅ abbreviates ∃ u₀ ⋅ ⋅ ⋅ ∃ u_n-1
• the notation ∀ u̅ abbreviates ∀ u₀ ⋅ ⋅ ⋅ ∀ u_n-1

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

    ∃ u̅⁰ ∀ u̅¹ ⋅ ⋅ ⋅ Q u̅^k ψ

    ∀ u̅⁰ ∃ u̅¹ ⋅ ⋅ ⋅ Q u̅^k ψ

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

(This is called prenex normal form.)

Exercise 3.13

Exercise 3.14

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

Exercise 3.15

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 ).

Exercise 3.16

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

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

Exercise 3.17

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 ( ℤ , < ) .

Exercise 3.18

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

Exercise 3.19

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 ψ₀ )   ∨   ⋅ ⋅ ⋅   ∨   ( ∃ 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. "

Exercise 3.20

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.

Exercise 3.21

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.

Exercise 3.22