Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 3 exercises

# 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

Find a formula φ such that { ∀ v ∃ u φ } ⊭ ∃ u ∀ v φ .

#### Exercise 3.3

Consider a language with constant symbols c and d.

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

Prove that for every sentence φ, there is a sentence φ* such that
• φ* is logically equivalent to φ and
• φ* is built up without the logical symbols ∨ , → , ↔ and ∀.

#### Exercise 3.5

Let A and B be structures in a common first-order language.

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

cB   =   π ( cA )   for every constant symbol c

FB ( π ( x0 ) , … , π ( xn-1 ) )   =   π ( FA ( x0 , … , xn-1 ) )   for every n-ary function symbol F and x̅ ∈ | A |n

RB ( π ( x0 ) , … , π ( xn-1 ) )   iff   RA ( x0 , … , xn-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 u0, … , un-1, then for all x̅ ∈ | A |n ,

( B , π ( x0 ) , … , π ( xn-1 ) ) ⊨ φ ( u0 / cπ ( x0 ) ) ⋅ ⋅ ⋅ ( un-1 / cπ ( xn-1 ) )

iff

( A , x0 , … , xn-1 ) ⊨ φ ( u0 / cx0 ) ⋅ ⋅ ⋅ (un-1 / cxn-1 ).

#### Exercise 3.6

Let Σ be a theory with arbitrarily large finite models. Prove that Σ has an infinite model.

#### Exercise 3.7

Consider the language with no constant, relation or function symbols.

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

Consider the language with no constant, relation or function symbols.

Define δ1 to be the sentence ⊤.

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

For each natural number n ≥ 1, define εn to be the disjunction of of the formulas   v0 ≈ vi   for 1 ≤ i ≤ n.

For n ≥ 1, define ψn to be the sentence   ∃ v1 ∃ v2 ⋅ ⋅ ⋅ ∃ vn   δn .

For n ≥ 1, define χn to be the sentence   ∃ v1 ⋅ ⋅ ⋅ ∃ vn   (   δn   ∧   ∀ v0   ε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

Consider the language with no constant, relation or function symbols.

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

Consider the language with a binary relation symbol R.

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

Explain why your φ has this property.

#### Exercise 3.11

Consider the language with a unary function symbol F.

Find a satisfiable sentence that has no finite models.

#### Exercise 3.12

If u̅ = ( u0 , … , un-1 ) is an n-tuple of variables, then:
• the notation ∃ u̅ abbreviates ∃ u0 ⋅ ⋅ ⋅ ∃ un-1
• the notation ∀ u̅ abbreviates ∀ u0 ⋅ ⋅ ⋅ ∀ un-1
We say that φ is quantifier-free if it is built up without the two quantifier symbols ∃ and ∀.

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

∃ u̅0 ∀ u̅1 ⋅ ⋅ ⋅ Qk ψ

∀ u̅0 ∃ u̅1 ⋅ ⋅ ⋅ Qk ψ

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

(This is called prenex normal form.)

#### Exercise 3.13

Let Σ be a finite theory.

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

#### Exercise 3.14

Let Σ be a finite theory.

Assume Σ is complete.

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

#### Exercise 3.15

Let A = ( ω , < ) = ( | A | , RA ).

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

#### Exercise 3.16

Let A be a structure and Y be a set.

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

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 / cx ) ( v / cy )

Prove that the shift functions,

x ↦ x + n

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

#### Exercise 3.18

Let Σ and Τ be theories with no models in common.

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

#### Exercise 3.19

Consider the language with just the unary relation symbol S.

Part 1

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

| Ai | = ω for every i ∈ ω.

Ai and Aj are not isomorphic for all distinct i , j ∈ ω.

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

Part 2

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

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:

• " SA has at least n elements. "
• " SA has exactly n elements. "
• " | A | - SA has at least n elements. "
• " | A | - SA has exactly n elements. "

#### Exercise 3.20

Consider the language with just the binary relation symbol R.

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

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

#### Exercise 3.21

Consider the language with just the unary function symbol F.

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

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

#### Exercise 3.22

Without leaving out any steps, give a justification for the deduction { ∃ v ¬ φ } ⊢ ¬ ∀ v φ .