Exercise 2.3.3 (Proporsition 2.3.5 )

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\)