Prove Proposition 2.2.5 (Hint: fix two of the variables and induct on the third)
-
\(\bullet\) Show that \((a+b)+c=a+(b+c)\) for each \(a,b,c\in\mathbb{N}\).
-
\(\Vdash\) { Proof by induction on \(a\) }
-
\(\bullet\) Base case: show that \((a+b)+c=a+(b+c)\), when
-
– \(a=0\)
-
\(\Vdash\) \((0+b)+c=0+(b+c)\)
-
\(\equiv\) { definition of addition: \(0 + m := m\) }
- \(b+c=b+c\)
-
\(\square\)
-
\(\bullet\) Inductive step: show that \(((a\pp)+b)+c=(a\pp)+(b+c)\), when
-
– \((a+b)+c=a+(b+c)\)
-
\(\Vdash\) \(((a\pp)+b)+c\)
-
\(=\) { definition of addition: \((n\pp)+m := (n+m)\pp\) }
- \(((a+b)\pp)+c\)
-
\(=\) { definition of addition: \((n\pp)+m := (n+m)\pp\) }
- \(((a+b)+c)\pp\)
-
\(=\) { inductive hypothesis,
-
\(~~~~~\) Substitution Axiom: \(a = b \implies f(a) = f(b)\) }
- \((a+(b+c))\pp\)
-
\(=\) { definition of addition: \((n\pp)+m := (n+m)\pp\) }
- \((a\pp)+(b+c)\)
-
\(\square\)
-
-
\(\square\)