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 Σ.
Assume that for every natural number n, there is a member of T of length n.
A famous result called Konig's Infinity Lemma says that there exists an infinite sequence < b_{i} ∣ i = 0, 1, 2, … > such that, for every natural number n, the finite sequence < b_{i} ∣ i < n > belongs to T.
Prove this fact by writing down a certain theory Σ that depends on T, verifying that the hypothesis of Theorem 2.10 holds, applying Theorem 2.10 to find a model A of Σ and using A to find an appropriate < b_{i} ∣ i = 0, 1, 2, … >.
(In fact, this is a rather convoluted way to prove Konig's Infinity Lemma but the connection to the Compactness Theorem is interesting.)
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 } .