2.3.3. Prove Proposition 2.3.5 (Hint: modify the proof of Proposition of 2.2.5 and use the distribution law.)
-
\(\bullet\) Show that \((a\times b)\times c=a\times(b\times c)\) for each \(a,b,c\in\mathbb{N}\).
-
\(\Vdash\) { Proof by induction on \(a\) }
-
\(\bullet\) Base case: Show that \((a\times b)\times c=a\times(b\times c)\), when
-
– \(a=0\)
-
\(\Vdash\) \((0\times b)\times c=0\times(b\times c)\)
-
\(\equiv\) { Definition 2.3.1: \(\forall m.~0\times m:=0\) }
- \(0\times c=0\)
-
\(\equiv\) { Definition 2.3.1: \(\forall m.~0\times m:=0\) }
- \(0=0\)
-
\(\square\)
-
\(\bullet\) Inductive step: Show that \(((a\pp)\times b)\times c=(a\pp)\times(b\times c)\) for each \(a,b,c\in\mathbb{N}\)., when
-
– \((a\times b)\times c=a\times(b\times c)\)
-
\(\Vdash\) \(((a\pp)\times b)\times c\)
-
\(=\) { Definition 2.3.1: \((n\pp)\times m:=(n\times m)+m\) }
- \(((a\times b)\times b)\times c\)
-
\(=\) { Proposition 2.3.4: \((b+c)a=ba+ca\) }
- \((a\times b)\times c+b\times c\)
-
\(=\) { inductive hypothesis }
- \(a\times(b\times c)+(b\times c)\)
-
\(=\) { Definition 2.3.1: \((n\pp)\times m:=(n\times m)+m\) }
- \((a\pp)\times(b\times c)\)
-
\(\square\)
-
-
\(\square\)