24.118: Paradox and Infinity PS 3: Suggested solutions

October 30, 2001

I.

(2 pts each)

(a) The code for ‘s0’ is 2^{5} + 2^{4} = 48

(b) The code for ‘0=0’ is 2^{2} + 2^{26} + 2^{7} = 67, 108, 996

II.

(5 pts each)

First, some general comments.

To show that a sentence of the form ‘∀xRx’ is a theorem of Peano arithmetic, one has to use induction (axiom PA7): First, one proves that ‘R0’ is an axiom of PA, then one proves that ‘∀x(Rx → RSx)’ is a theorem of PA. Then PA7 licenses the conclusion that ‘∀xRx’ is a theorem of PA.

Some of you did the following in the induction steps: Assume ‘∀xRx’ as induction hypothesis and show ∀xRsx’. This doesn’t work as induction step. You are just assuming what you need to prove. You want to prove that ‘∀x(Rx → Rsx)’. To do this, assume ‘Rx’ (for arbitrary but fixed x) and show ‘Rsx’ (ie R holds of the successor of the element for which you assumed R to hold).

Some of you write down proofs in reverse. That is, you start out assuming what you need to prove and then derive some obvious theorem of PA from it (such as ‘x=x’). This is usually not the way to go: Firstly, merely deriving a theorem T from a statement S (even if all the steps you take are valid) does not show that the statement S is itself a theorem (in fact, (a) if S is the negation of a theorem, you can derive every statement from it; and (b) if T is a theorem, you can derive it from every statement). Secondly, even if your proof is such that it manages to avoid the first trap, it can go wrong, because not all the steps that work in one direction also work in the other. In particular, PA2 allows you to go from ‘(sx = sx)’ to ‘(x = x)’. It does not allow you to go the other way and if you want to do so, you need to do some work to show that this is permissible.

Some of you tried to avoid using induction by assuming that every element has a name of the form ‘S … S0’ (with n Ss for some n). This, however, doesn’t work, because there are domains in which PA is true but in which not every element has such a name. (The reason for this will not be covered in this class.) You really have to use induction.

When you write down what you take to be a proof of some theorem, make sure it is obvious what the structure of your proof is and what licences the steps you take (ie what axiom, theorems and/or rules allows you to take these steps). You can do whatever you like when figuring out how the proof goes, but when you want to present it to others for evaluation (or to yourself a week later), it should be well laid-out and annotated.

On to the problems. We will do (a) in all detail and outline the major steps of (c), (b) being perfectly analogous to (a). To improve legibility, we’ll use variables x, y, z.

(a) Claim: ∀x∀y∀z((x + y) + z = x + (y + z)) (a)

Proof: We want to prove a universally quantified statement, so we need to use induction. The formula we subsitute for R in the induction-axiom is

∀y∀z((x + y) + z = x + (y + z))

In order to apply induction, we need to prove two things.

(i) ∀y∀z((0 + y) + z = 0 + (y + z))

(ii) ∀x∀y∀z[(x + y) + z = x + (y + z) → (Sx + y) + z = Sx + (y + z)]

(i) This has itself two universal quantifiers in front so we need to use induction twice. First, we will show Subclaim 1:

∀z((0 + 0) + z = 0 + (0 + z))

Base case:

(0 + 0) + 0 = 0 + (0 + 0) (Commutativity of +)

Induction step: Assume

(0 + 0) + z = 0 + (0 + z)

Then

(0 + 0) + Sz = S((0 + 0) + z) (PA4)
= S(0 + (0 + z)) (Induction hypothesis)
= (0 + S(0 + z)) (PA4)
= (0 + (0 + Sz)) (PA4)

Then induction allows us to conclude subclaim 1. Next, we prove

Subclaim 2:

∀y∀z((0 + y) + z = 0 + (y + z))

Base case:

∀z((0 + 0) + z = 0 + (0 + z))

This is just an instance of subclaim 1, so we’re done.

Induction step: Assume

∀z(0 + y) + z = 0 + (y + z)

Then

(0 + Sy) + z = (Sy + 0) + z Commutativity of +
= Sy + z PA3
= (Sy + z) + 0 PA3
= 0 + (Sy + z) Commutativity of +

Applying induction, we get subclaim 2. This establishes (i) above. Next we continue with the induction step of our main claim.

(ii) Assume

∀y∀z((x + y) + z = x + (y + z))

Then

(Sx + y) + z = (y + Sx) + z Commutativity of +
= S(y + x) + z PA4
= z + S(y + x) Commutativity
= S(z + (y + x)) PA4
= S(z + (x + y)) Commutativity
= S((x + y) + z) Commutativity
= S(x + (y + z)) Induction hypothesis
= S((y + z) + x) Commutativity
= (y + z) + Sx PA4
= Sx + (y + z) Commutativity

So we get (ii). Now apply induction (PA7) to (i) and (ii) to get

∀x∀y∀z((x + y) + z = x + (y + z))

This concludes the proof.

(b) Analogous to (a) (b)

(c) Claim: ∀x¬x < x (c) That is, ∀x¬∃y(x + Sy = x). Again, we use induction. Base case:

¬∃y(0 + Sy = 0)

This is the same as

∀y¬(0 + Sy = 0)

By simple transformation, you can see that this is just PA1. Induction step: Suppose

∀y¬(x + Sy = x)

We want to show that ∀y¬(Sx + Sy = Sx). Suppose not, that is suppose that for some y

(Sx + Sy = Sx)

Then

S(Sx + y) = Sx PA4
Sx + y = x PA2
y + Sx = x PA2
S(y + x) = x PA4
x + Sy = x Commutativity, PA4

The last line contradicts the induction hypothesis. Hence, we conclude that ∀y¬(Sx + Sy = Sx). Now, apply induction to conclude that ∀x¬∃y(x + Sy = x), which is the same as ∀x¬x < x.