- 0. Memorize the four Rules of Inference for Proof by Induction given in the table of the same name in lecture notes in section 7.2 (below the Theorem 19 about equivalent forms). We will have a quiz on those definitions.
- 1. Prove the following theorems. Use semiformal proofs using any of the shortcuts we discussed, but for reasons you can only use the rules from Logic, the Peano Axioms, the definition of 1,2,3,… that I wrote on the board, and any theorems or lemmas we proved. You can use the results of an earlier assigned or proven problem in the proof of a later problem but not vice-versa. You cannot use “by arithmetic” as a reason. All quantiied variables are assumed to be natural numbers. Hint: You can use the Lemma we proved in class! It’s very helfpul!
- (a) Theorem (addition is commutative): $$\forall n,\forall m, m+n=n+m$$
- (b) Theorem (harder than $1+1$): $$2+2=2\cdot 2$$
- (c) Theorem (associativity of addition): $$\forall m,\forall n,\forall p, m+(n+p)=(m+n)+p$$
- (d) Theorem (multiplicative identity): $\forall n, n\cdot 1=n$ and $1\cdot n=n$
(Hint: you don’t need induction to prove the first equality but you need it for the second.)
- (e) Theorem (good thing we have $1+1$): $$1\leq 2$$
- (f) Theorem (just as we expected): $\forall n,\sigma(n)=n+1$
- (g) Theorem (strong induction): Prove that part (a) implies part (c) in Theorem 19 of the Lecture Notes.