Section 2
2.2.1
Proposition 2.2.5 (Addition is associative). For any natural numbers $a,b,c$, we have $(a+b)+c = a+(b+c)$.
We prove the statement by induction on $c$.
Base Case ($c=0$):
\[\begin{aligned} (a+b)+0 &\overset{(i)}{=} a+b\\ &\overset{(i)}{=} a+(b+0)\\ &= a+(b+c)\\ \end{aligned}\]where in $(i)$ we use Lemma 2.2.2 in the textbook.
Inductive Hypothesis: Assume that for natural number $c$, $(a+b)+c = a+(b+c)$ is true.
Inductive Step: we show that $(a+b)+(c++) = a+(b+(c++))$ is true, under the assumption that the inductive hypothesis is true.
\[\begin{aligned} (a+b)+(c++) &\overset{(i)}{=} ((a+b)+c)++\\ &\overset{(ii)}{=} (a+(b+c)) ++ \\ &\overset{(i)}{=} a + ((b+c)++) \\ &\overset{(i)}{=} a + (b + (c++)) \end{aligned}\]where in $(i)$ we use Lemma 2.2.3 in the textbook, in $(ii)$ we use the inductive hypothesis. Thus, by the principle of induction, we conclude that for any natural numbers $a,b,c$, we have $(a+b)+c = a+(b+c)$.
Q.E.D.
2.2.2
Lemma 2.2.10. Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b++ = a$.
We prove the statement by induction on $a$.
Base Case ($a=1$):
\[\begin{aligned} 0 ++ &= 1\\ \Rightarrow b &= 0 \end{aligned}\]Inductive Hypothesis: Assume that for positive natural number $a$, there exists exactly one natural number $b$ such that $b++ = a$.
Inductive Step: we show that there exists exactly one natural number $b$ such that $b++ = a++$, under the assumption that the inductive hypothesis is true.
\[\begin{aligned} b++ &= a++\\ \overset{(i)}{\Rightarrow} b &= a\\ \end{aligned}\]where in $(i)$ we use the peano axioms (if $n++ = m++$, then we must have $n = m$), and $b = a$ is a natural number since $a$ is a positive natural number. Thus, by the principle of induction, we conclude that for any positive natural number $a$, there exists exactly one natural number $b$ such that $b++ = a$.
Q.E.D.
2.2.3
Proposition 2.2.12 (Basic properties of order for natural numbers).
Let $a, b, c$ be natural numbers. Then:
(a) (Order is reflexive) $a \ge a$.
There exists natural number $0$ such that $a = a + 0$, which implies $a \ge a$ by definition. Q.E.D.
(b) (Order is transitive) If $a \ge b$ and $b \ge c$, then $a \ge c$.
(c) (Order is anti-symmetric) If $a \ge b$ and $b \ge a$, then $a = b$.
(d) (Addition preserves order) $a \ge b$ if and only if $a + c \ge b + c$.
(e) $a < b$ if and only if $a++ \le b$.
(f ) $a < b$ if and only if $b = a + d$ for some positive number $d$.