g : { A ∣ A is a structure } → { 0 , 1 }
is said to be finitary iff there exists a natural number n such that for all structures A and B, if A ( P_{i} ) = B ( P_{i} ) for every i < n, then g ( A ) = g ( B ).
Prove that for all finitary g, there is a sentence φ such that g is the truth table for φ.
( Q_{0,0} ∧ Q_{0,1} ∧ ⋅ ⋅ ⋅ ∧ Q_{0,n} ) ∨ ( Q_{1,0} ∧ Q_{1,1} ∧ ⋅ ⋅ ⋅ ∧ Q_{1,n} ) ∨ ⋅ ⋅ ⋅ ∨ ( Q_{m,0} ∧ ⋅ ⋅ ⋅ ∧ Q_{m,n} )
where each Q_{i,j} is either P_{j} or ¬ P_{j}.
(This is called disjunctive normal form.)
As a hint, think about the truth table of φ.
( Q_{0,0} ∨ Q_{0,1} ∨ ⋅ ⋅ ⋅ ∨ Q_{0,n} ) ∧ ( Q_{1,0} ∨ Q_{1,1} ∨ ⋅ ⋅ ⋅ ∨ Q_{1,n} ) ∧ ⋅ ⋅ ⋅ ∧ ( Q_{m,0} ∨ ⋅ ⋅ ⋅ ∨ Q_{m,n} )
where each Q_{i,j} is either P_{j} or ¬ P_{j}.
(This is called conjunctive normal form.)
The two previous exercises show that { ⊥ , ¬ , ∧ , ∨ } and { ⊤ , ¬ , ∧ , ∨ } are complete sets of symbols.
Hint: For 2.4.2.2, consider the structure A such that A ( P_{n} ) = 1 for every n.
Let Σ be a theory such that
Prove that for every sentence, there is a logically equivalent sentence that belongs to Σ.
(In other words, ⊨ is a partial ordering.)
(In other words, ╞╡ is an equivalence relation.)
Let ⊨_{n} be the logical consequence relation ⊨ restricted to to Σ_{n}.
It follows easily from Exercise 2.6 that ⊨_{n} is a partial ordering of Σ_{n}.
Let ╞╡_{n} be the logical equivalence relation restricted to Σ_{n}.
It follows easily from Exercise 2.6 that ╞╡_{n} is an equivalence relation on Σ_{n}.


The diagram on the left indicates that, considering Σ_{0} under ╞╡_{0}, there are only two equivalence classes, those of ⊥ and ⊤.
Also, moving up the left diagram corresponds to the relation ⊨_{0} between members of the equivalence classes.
The diagram on the right indicates that, considering Σ_{1} under ╞╡_{1}, there are only four equivalence classes, those of ⊥, P_{0}, ¬ P_{0} and ⊤.
Also, moving up the right diagram corresponds to the relation ⊨_{1} between members of the equivalence classes.
Now choose a complete set of representatives for Σ_{2} under ╞╡_{2} and draw a corresponding diagram for the partial ordering ⊨_{2}.
Assume that for every natural number n, either P_{n} belongs to Σ or ¬ P_{n} belongs to Σ.
In other words, address the ¬in, R1, R2 and R3 rules in the righttoleft direction of the proof.
Describe a computer algorithm for listing all of the proofs from Σ.
Running the algorithm, the hypothetical computer would output p_{0} , then p_{1} , then p_{2} etc. so that
{ q ∣ q is a proof from Σ } = { p_{n} ∣ n is a natural number }
Your algorithm will use Σ as an oracle, which means that in addition to the usual commands, it may query whether a given sentence belongs to Σ.
You write a program based on your algorithm from Exercise 2.14 and run the program on your hypothetical computer. Will it perform as expected? Explain.
{ } ⊢ ( φ → ψ ) ↔ ( ( ¬ ψ ) → ( ¬ φ ) ).
The sentence ( ¬ ψ ) → ( ¬ φ ) is called the contrapositive of the sentence φ → ψ.
Prove that there is a sentence χ such that
φ ⊨ χ but χ ⊭ φ
and
χ ⊨ ψ but ψ ⊭ χ .
Suggestions:
1) Think about the special case in which φ is F and ψ is any satisfiable sentence.
2) Think about how this is related to Exercise 2.7.
Let φ be a sentence built up from P_{n} for n ∈ I.
Let ψ be a sentence built up from P_{n} for n ∈ J.
Assume φ ⊨ ψ.
Prove that there is a sentence χ that is built up from P_{n} for n ∈ I ∩ J such that φ ⊨ χ and χ ⊨ ψ .
Suggestion: First think about I = { 0 , 1 } and J = { 1 , 2 } .
Define a graph to be a pair ( V , E ) where V is a set and E ⊆ V × V such that, for all x , y ∈ V,
and
Two vertices are said to be adjacent iff they form an edge.
A function c : V ↦ k is called a kcoloring iff c ( x ) ≠ c ( y ) for all ( x , y ) ∈ E.
In other words, a graph coloring assigns different colors to adjacent vertices.
Often, we consider a positive natural number k = { 0 , ... , k1 } as the set of colors, in which case there are k many colors.
It is easy to see that for every subset W ⊆ V, if we put
F = E ∩ ( W × W ),
then ( W , F ) is also a graph.
We refer to ( W , F ) as the subgraph of ( V , E ) that is induced by F in this situation.
Now we have the terminology needed for the following two exercises.
Recall that ω = { 0 , 1 , 2 , 3 , etc } and 2 = { 0 , 1 }.
For m,n ∈ ω, let φ_{m,n} be the sentence
( ¬ P_{m} ∧ P_{n} ) ∨ ( P_{m} ∧ ¬ P_{n} )
Let Σ be the theory
{ φ_{m,n}  (m,n) ∈ E }.
Prove that the following three statements are equivalent:
Recall that 3 = { 0 , 1 , 2 }.
Prove that the following two statements are equivalent:
Q_{n,i} equal to P_{3n+i}.
For yourself, perhaps, think of Q_{n,0} as a red light bulb, Q_{n,1} as a yellow light bulb, and Q_{n,2} as a green light bulb for each n ∈ ω.
Now seek inspiration from Exercise 2.19 but you will need to define and use a different theory.
Bonus exercise: A result of De Bruijn and Erdős says that, for every positive natural number k, Exercise 2.20 remains true if 3 is replaced by k. Generalize your solution to Exercise 2.20 to prove this.
Of course, this is not the only justifications of { ( P_{0} ∧ P_{1} ) ∧ P_{2} } ⊢ P_{0}.
Prove that every justification of { ( P_{0} ∧ P_{1} ) ∧ P_{2} } ⊢ P_{0} uses rule R2 in its final line.
Hint: For each of the fourteen rules other than R2, explain why it cannot be used in the final line of a justification of { ( P_{0} ∧ P_{1} ) ∧ P_{2} } ⊢ P_{0}.
We will use the function restriction notation from Chapter 1.
In particular, if r ∈ S and m < n = dom ( r ), then r ↾ m = < r ( i )  i < m > ∈ S.
We say that T is a binary tree iff T ⊆ S and, for every r : n → 2 and m < n, if r belongs to T, then r ↾ m belongs to T.
In particular, S is a binary tree.
An infinite branch through T is a function b : ω → 2 such that b ↾ n ∈ T for every n ∈ ω.
A famous result called Kőnig's Infinity Lemma says that if T is an infinite binary tree, then there is an infinite branch through T.
You may not use Kőnig's Infinity Lemma in this exercise because you are going to prove it.
Let f : ω → T be a bijection.
Whenever n ∈ ω and dom ( f ( j ) ) = n, let δ_{n,j} be the conjunction of P_{j} and all those ¬ P_{i} with i ≠ j and dom ( f ( i ) ) = n.
Written another way, δ_{n,j} is the sentence
P_{j} ∧ ( ⋀ { ¬ P_{i}  dom ( f ( i ) ) = n and i ≠ j } ) .
Let φ_{n} be the disjunction of all those δ_{n,j} with dom ( f ( j ) ) = n.
Written another way, φ_{n} is the sentence
⋁ { δ_{n,j}  dom ( f ( j ) ) = n } .
Let ψ_{n} be the conjunction of all the sentences δ_{n,j} → δ_{m,i} with m ≤ n = dom ( f ( j ) ) and f ( i ) = f ( j ) ↾ m.
Written another way, ψ_{n} is the sentence
⋀ { δ_{n,j} → δ_{m,i}  m ≤ n = dom ( f ( j ) ) and f ( i ) = f ( j ) ↾ m } .
Let Γ_{n} = { φ_{n} , ψ_{n} }.
Let Σ_{n} = ⋃ { Γ_{m}  m ≤ n }.
Let Σ = ⋃ { Σ_{n}  n ∈ ω }.
b = ⋃ { f ( j )  A ( P_{j} ) = 1 } ,
then:
You may not use Compactness Theorem 2.10 in this exercise because you are going to learn a different proof of it.
Let f : ω → Σ be a bijection.
Let Σ_{n} = { f ( j )  j < n and f ( j ) is built up from P_{i} for i < n }.
Let S = { r  r is a function from n to 2 for some n ∈ ω }.
Let T be the subset of S that consists of functions r : n → 2 such that, for every structure A, if A ( P_{i} ) = r ( i ) for all i < n, then A is a model of Σ_{n}.
Let b : ω → 2 be an infinite branch through T.
Define a structure A by setting A ( P_{i} ) = b ( i ) for all i ∈ ω.
Prove that A is a model of Σ
You may not use Kőnig's Infinity Lemma in this exercise because you are going to learn its traditional proof.
Notation:
Each T_{r} is a subtree of T but it might not be infinite.
Define a function b : ω → 2 by recursion by setting
b ( n ) = 0 iff T_{( b ↾ n )∧< 0 >} is infinite.
b ( n ) = 1 iff T_{( b ↾ n )∧< 0 >} is finite.
[PDF]