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 ( Pi ) = B ( Pi ) 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 φ.
( Q0,0 ∧ Q0,1 ∧ ⋅ ⋅ ⋅ ∧ Q0,n ) ∨ ( Q1,0 ∧ Q1,1 ∧ ⋅ ⋅ ⋅ ∧ Q1,n ) ∨ ⋅ ⋅ ⋅ ∨ ( Qm,0 ∧ ⋅ ⋅ ⋅ ∧ Qm,n )
where each Qi,j is either Pj or ¬ Pj.
(This is called disjunctive normal form.)
As a hint, think about the truth table of φ.
( Q0,0 ∨ Q0,1 ∨ ⋅ ⋅ ⋅ ∨ Q0,n ) ∧ ( Q1,0 ∨ Q1,1 ∨ ⋅ ⋅ ⋅ ∨ Q1,n ) ∧ ⋅ ⋅ ⋅ ∧ ( Qm,0 ∨ ⋅ ⋅ ⋅ ∨ Qm,n )
where each Qi,j is either Pj or ¬ Pj.
(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 ( Pn ) = 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 ⊥, P0, ¬ P0 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 Pn belongs to Σ or ¬ Pn belongs to Σ.
In other words, address the
¬-in, R1, R2 and R3 rules in the right-to-left direction
of the proof.
Describe a computer algorithm for listing all of the proofs from Σ.
Running the algorithm, the hypothetical computer would
output p0 , then p1 , then p2 etc.
so that
{ q ∣ q is a proof from Σ }
= { pn ∣ 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.
Exercise 2.14
Let Σ be a theory.
Exercise 2.15
What if your hypothetical computer were your actual computer
but it could run forever without breaking down when left in
isolation without any sort of interaction with other devices or beings.
In particular, it has its own limitless power source.
{ } ⊢ ( φ → ψ ) ↔ ( ( ¬ ψ ) → ( ¬ φ ) ).
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 ⊥ and ψ is any satisfiable sentence.
2) Think about how this is related to Exercise 2.7.
Let φ be a sentence built up from Pn for n ∈ I.
Let ψ be a sentence built up from Pn for n ∈ J.
Assume φ ⊨ ψ.
Prove that there is a sentence χ that is built up from Pn 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 k-coloring 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 , ... , k-1 } 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
( ¬ Pm ∧ Pn ) ∨ ( Pm ∧ ¬ Pn )
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:
Qn,i equal to P3n+i.
For yourself, perhaps, think of Qn,0 as a red light bulb, Qn,1 as a yellow light bulb, and Qn,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 { ( P0 ∧ P1 ) ∧ P2 } ⊢ P0.
Prove that every justification of { ( P0 ∧ P1 ) ∧ P2 } ⊢ P0 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 { ( P0 ∧ P1 ) ∧ P2 } ⊢ P0.
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 Pj and all those ¬ Pi with i ≠ j and dom ( f ( i ) ) = n.
Written another way, δn,j is the sentence
Pj ∧ ( ⋀ { ¬ Pi | 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 ( Pj ) = 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 Pi 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 ( Pi ) = 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 ( Pi ) = 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 Tr 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]