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

York University

Faculties of Pure and Applied Science, Arts, Atkinson MATH 2090. Problem Set #3. Posted February 8, 2002

Due in the Course Box. Monday, February 25, 2002

Section N

In your proofs it is imperative to clearly state what tools you use (e.g., WLUS, SLCS, MP, PSL, Monotonicity, Deduction Theorem, Weak Generalization, which axiom(s), etc.)

1. Recall from class that “(Σi|0 ≤ i < n : i)” means ∑_{i<n} i and the latter is a function f(n) of the variable n over ℕ given inductively by

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

After this clarification/reminder do 12.4(b), p.242.

2. Also do from the text p.244–246:

{12.9, 12.15, 12.20}

In problem 12.15 attach the intuitive meaning of number of elements to the symbol #A, where A is a set (i.e., never mind the GS “axiom 11.12”).

Conventions AND notation from class apply!

(a) Convert GS-assertions to “standard mathematical notation” before you start any proof.

(b) Do not use Peano formal axioms in any of the \underline{above} proofs

Also do

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

• Prove, this time formally from Peano Axioms (see Web-posting),

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.

• Prove, formally from Peano Axioms

PA ⊢ (∀x)0 + x = x

Hint. Caution! You do not have commutativity yet! Do (simple) induction on x.

• Now do simple induction on y to prove commutativity: Prove, formally from Peano Axioms

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

Hint. Prove, formally from Peano Axioms, a (trivial) Lemma: PA ⊢ (∀x)Sx = x + S0. Then use associativity and previous problem.