MATH 2090  Problem Set #3 (On Ch.12)

York University

Faculties of Pure and Applied Science, Arts, Atkinson MATH 2090. Problem Set #3. Posted October 19 , 2003

Due in the Course Box. November 6, 2003

Section A

In your proofs (formal or not) it is imperative to clearly state what tools you use (e.g., WLUS, sWLUS, MP, Leibniz, Monotonicity, Deduction Theorem, Generalization, Auxiliary Variable metatheorem, which axiom(s), etc.)

1. (5 Marks) Let F = ∅. Calculate (give the simplest possible answer).

(1) ⋃ F

(2) ⋂ F

In problems 2–7 you may apply informal proofs, however, the only facts you may use are Logic, the Peano axioms, and whatever we proved from those in class [by the time of me writing this we have only proved 0 ≤ x and x < y < z ⇒ x < z in class]. So, do Not assume in your proofs that you “know” anything about ℕ that we have not proved in class from the axioms.

2. (5 Marks) Grade the following wrong “proof” by contradiction of P A ⊢ ¬Sx = x. You must locate all errors precisely.

Proof. We argue by contradiction, so let as assume the opposite of the required conclusion:

Sx = x  (1)

Now this yields S0 = 0 by doing specialisation on the generalisation— (∀x)Sx = x—of (1). But this contradicts the specialisation ¬S0 = 0 that we obtain from the first Peano axiom (∀x)¬Sx = 0. □

3. (5 Marks) OK, now give a correct inductive proof of P A ⊢ ¬Sx = x.

4. (5 Marks) Here is another incorrect “proof” I want you to grade carefully and find all logical errors. Prove P A ⊢ ¬x < x.

Proof. We do induction.

Basis: Verify ¬0 < 0. That follows from the first <-axiom, that is, (∀x)¬x < 0, by specialisation.

We now add the I.H.

¬x < x  (2)

and “goto” proving

¬Sx < Sx  (3)

Now, (3) equivales to

¬(Sx = x ∨ Sx < x)  (4)

by the 2nd <-axiom, so I need to prove that Sx = x ∨ Sx < x yields false.

I argue by cases:

Case 1. If I have Sx = x, then, in particular I have S0 = 0 (specialisation from (∀x)Sx = x) which contradicts ¬S0 = 0 obtained from the first axiom for “S” ((∀x)¬Sx = 0).

Case 2. If I have Sx < x, then, in particular I have S0 < 0 which contradicts the first <-axiom: (∀x)x < 0 (just specialise [x := S0]). □

5. (5 Marks) OK, now give a correct inductive proof of P A ⊢ ¬x < x.

6. (5 Marks) Prove from the Peano axioms,

PA ⊢ (∀x, y, z)(x + y) + z = x + (y + z)

NB. “(∀x, y, z)” is a lazy way to write “(∀x)(∀y)(∀z)”.

Hint. Do (simple) induction on z.

7. (5 Marks) Prove from Peano axioms

PA ⊢ (∀x)0 + x = x

Hint. Caution! We do not have commutativity from class or

anywhere else, so do not use it! Do (simple) induction on x.

Below you are also asked to do informal proofs, but you are allowed to “know a lot” about the natural numbers. Your tools will be logic, your knowledge, and Induction (simple or CVI, as the case demands).

You are not to use the Peano axioms (except for Induction). Of course, \underline{you are responsible to use} correct principles, and, as always, please do not perform any leaps of logic/faith.

8. (5 Marks) Recall from class that GS notation “(∑ i|0 ≤ i ≤ n : f(i))” means ∑_{i<n} f(i), which in turn denotes a function g(n) of the variable n over ℕ that is given inductively by

g(0) = f(0)
g(n + 1) = g(n) + f(n + 1)

After this clarification/reminder do 12.4(d), p.242 of the GS text.

9. (10 Marks) Also do from the text p.244–246 \underline{informally}:

{12.15, 12.27}

In problem 12.15—that is required to be done by induction—attach the intuitive meaning to the concept “number of elements of a finite set”, just as we did at the end of our set theory notes (Part II). I.e., never mind the GS “axiom 11.12”.

By the way, the symbol “#S” in GS, where S is a set, is what we have denoted by “|S|” in class and in the notes.