Mathematical Logic Final Solutions
Exercise 3
Use Soundedness Theorem for first-order logic to prove that T1 is independent of the other axioms, that is
T2, T3 b T1, T2, T3 b ¬T1
Proof. We first give an L-structure R such that R € T2, T3 and R B T1. The universe is N w , where w is something other than a natural number. Let
S be the successor function so that S(x) = x + 1, if x N and S(w) = w. Define the relation < by
<= {(a, b)|a, b ∈ R} ∪ {(w, w)}
It is easy to see that R € T2, T3 . Also R B T1 since w < w. Thus by soundedness theorem, we have T2, T3 b T1.
Next we give another L-structure R such that R € T2, T3 and R B T1. Ther universe in this case is simply R, where < is given by the usual inequality and S the successor function. It follows that R € T2, T3 and R B T1 as x < x for all x N. Thus by Soundedness theorem, we have T2, T3 b T1,
which completes the proof.
Exercise 4
Is T a consistent theory? Justify your answer.
Proof. T is a consistent theory. By completeness theorem it suffices to give a model R for this theory. The universe is the natural numbers N, with < the ususal strict inequality. S is the usual successor function, i.e., S(x) = x + 1 for x N. It is easy to see that all T1, T2, T3 are satisfied. Hence it is a consistent theory.
Exercise 5
Give a T -deduction of x[ Sx < Sx]. Give a full deduction. Name all the logical axioms and inference rules involved in the deduction.
Proof. First note that from T1, we know that x[ x < x]. Since Sx is substitutable for x, we apply Q1 and conclude that Sx < Sx. Now we have shown
∀x[¬x < x] → ¬Sx < Sx
We apply QR and conclude that ∀x[¬Sx < Sx], which completes the proof.
Exercise 6
Sketch a T -deduction of x[ Sx = x]. ame all the logical axioms and infer- ence rules involved in the deduction.
Proof. Note that
¬x < x ∧ (x < Sx) → ¬x = Sx
Here we are using T1 and T3 and the fact that the above statement is a tautology (one can use a Truth table to prove this). Hence we apply PC and QR and conclude that ∀x[¬x = Sx].
Exercise 7
Prove that any model for T is infinite.
Proof. Assume, on the contrary, that there is a finite model. Suppose the universe is some finite set. Let x be an element in this set. Note that by T3, we have x < Sx and Sx < S2x. Since the set is finite, there must exist j, i ∈ N with i =ƒ j such that Six = Sjx. Assume without loss of generality that i < j(here < means the usual order for natural numbers). By T2 andT3, we conclude that Six < Sjx. But since Six = Sjx, we have Six < Six, which contradicts Axiom T1. Therefore any model for T must be infinite.
Exercise 8
Prove that we have
R € φ → N0 € φ
for any purely existential sentence φ.
Proof. Let φ be a purely existential sentence. By the inductive definition, one can prove inductively from N0 axioms that N0 € φ, hence N0 φ by completeness theorem.
Exercise 9
Prove that
N0 b ∀x[x < 6 → (x = 0 ∨ x = 1 ∨ x = 2 ∨ x = 3 ∨ x = 4 ∨ x = 5)]
Proof. We will give another LNT -structure R such that R € N0 but R B
∀x[x < 6 → (x = 0 ∨ x = 1 ∨ x = 2 ∨ x = 3 ∨ x = 4 ∨ x = 5). The
universe is the set of all integers Z with usual addition and standard strict ordering of integers. It is clear that this model satisfy all N0 axioms, namely, R € N0(all purely existential properties that hold in natural numbers also
hold in integers). However, R B ∀x[x < 6 → (x = 0 ∨ x = 1 ∨ x = 2 ∨ x = 3 ∨ x = 4 ∨ x = 5), since x can also be all negativer integers.
Exercise 10
N € φ ⇔ N0 € φ
for any purely existential sentence? Justify your answer.
Proof. First suppose N φ for any purely existential sentence φ. By sound- edness theorem, we have R € φ. Then by what we have proved in Problem 8, we have N0 φ.
Next we suppose that N0 φ. By soundedness theorem, we have N0 € φ. Since φ is purely existential, by N0 axioms we conclude that N € φ. Finally, by completeness theorem, we must have N € φ, which completes the proof.
Exercise 11
Do we have
N € φ ⇔ N0 € φ
for any Σ-sentence φ? Justify your answer.
Proof. This is not true. From Problem 9 we have
N0 b ∀x[x < 6 → (x = 0 ∨ x = 1 ∨ x = 2 ∨ x = 3 ∨ x = 4 ∨ x = 5)]
However it is easy to see that N € ∀x[x < 6 → (x = 0 ∨ x = 1 ∨ x = 2 ∨ x = 3 ∨ x = 4 ∨ x = 5)] by a standard N -deduction.
Exercise 12
Does there exist an LNT -structure R such that R € N and R B N0? Justify your answer.
Proof. Yes, there exists one. Let R be one LNT -structure whose universe is N w , where w is an element other than natural numbers. Addition is the usual addition of numbers with a + w = w for all a N w . S is the sucessor function with S(x) = x + 1 if x N and S(w) = w. The relation < is defined by
<= {(a, b)|a, b ∈ N} ∪ {(a, w)|a ∈ N ∪ {w}}
It is easy to see that R € N . However R B N0. For instance, w + 5 = in the usual standard structure, but nevertheless R € w + 5 = w + 3