% Copyright (C) He Guanyuming 2020
% The file is licensed under the MIT license.

\section{Natural Numbers}
\subsection{The Peano Axioms}

\subsection{Addition of Natural Numbers}
\begin{prop}
(Exercise 2.2.1) \label{exercise2.2.1}
The addition of natural numbers is associative. That is, $(a+b)+c=a+(b+c)$.
\end{prop}
\begin{proof}
Use induction: First, $(0+b)+c=b+c=0+(b+c)=b+c$.

Then, assume that $(n+b)+c=n+(b+c)$, thus 
\begin{align*}
(S(n)+b)+(c)
&= S(n+b)+c\\
&= S(n+b+c)\\
&= S(n+(b+c)) \tag{By assumption}\\
&= S(n)+(b+c)
\end{align*}
, which closes the induction. \qedhere
\end{proof}

\begin{prop}
(Exercise 2.2.2) \label{exercise2.2.2}
For any positive natural number $n$, there is exactly one natural number $m$ that $S(m) = n$. 
\label{prop5}
\end{prop} 

\begin{proof}
Use induction: When $n=0$, the statement is vacuously right.

Assume that the statement is true for a natural number $n$, thus
\begin{description}
\item[Existence] 
\[
S(S(m)) = S(n)
\]
\item[Uniqueness]
It is obvious according to axiom 3.
\end{description}
\end{proof}

\begin{prop}
(Exercise 2.2.3) \label{exercise2.2.3}
\begin{enumerate}
\item Order is reflective $a \geq a$
\item Order is transitive $a \geq b \wedge b \geq c \Longrightarrow a \geq c$
\item Order is anti-symmetric $a \geq b \wedge b \geq a \Longrightarrow a=b$
\item Addition preserves order $a \geq b \Longrightarrow a+c \geq b+c$
\item $a<b \Longleftrightarrow S(a) \leq b$
\item $a<b$ Iff for positive natural number $c$, $b=a+c$
\end{enumerate}
\end{prop}
\begin{proof}
(1) It is immediately proven by $a=a+0$.

(2) 
\begin{align*}
a \geq b &\wedge b \geq c \Longrightarrow \\
a = b+m &\wedge b = c+n \Longrightarrow \\
a = c+n+m &= c+(n+m) \Longrightarrow \\
a &\geq c 
\end{align*}

(3)
By definition of order, 
\begin{align*}
a \geq b &\wedge b \geq a \Longrightarrow \\
a = b+m &\wedge b = a+n \Longrightarrow \\
a &= a+(n+m) \Longrightarrow \\
n+m&=0 \Longrightarrow \tag{By Lemma \ref{lem3}}\\
n=m&=0 \Longrightarrow \tag{By Corollary \ref{coro1}} \\
b=a+0&=a
\end{align*}

(4)
\begin{align*}
a \geq b &\equiv \\
a = b+n &\equiv \\
a+c=(b+n)+c=b+(n+c)=b+(c+n)=(b+c)+n &\equiv \\
a+c \geq b+c
\end{align*}

(5)
\begin{align*}
a<b &\Longleftrightarrow \\
b=a+p &\Longleftrightarrow \\
b+1=a+p+1=a+1+p=S(a)+p \\
=S(a)+S(n) \tag{By proposition \ref{prop5}, $p$ is always some natural number $n$'s successor}\\
=S(a)+n+1 &\Longleftrightarrow \\
b=S(a)+n &\Longleftrightarrow \tag{By cancellation law} \\
b \geq S(a)
\end{align*} \label{prop.5}

(6)
On one hand, $b=a+c$ immediately gives $a<b$.

On the other hand, according to (5), $a<b$ gives 
\begin{align*}
S(a) \leq b  &\Longrightarrow\\
b = S(a) + n& \\
= a+1+n = a+(n+1)&
\end{align*}, where $n+1$ is positive. \label{prop.6}
\end{proof}

\begin{prop}
(Exercise 2.2.4) \label{exercise2.2.4}
For two natural number $m,n$, $m$ either $>$, or $=$, or $<n$.
\end{prop}
\begin{proof}
Tao's book has proven that at most one statement can be true at a time.

Now we are proving the remnant. Use induction: When $m=0$, for any natural number $n$, 
$0=n$, or $0 \neq n$. Under the latter case:
\begin{lem}
$n$ is positive $\Longleftrightarrow n>0$
\end{lem}
\begin{proof}
On one hand, $n>0$ immediately gives $n$ is positive.

On the other hand, $n=0+n$ gives $n \geq 0$. And $n$ being positive implies that $n \neq 0$. 
So $n > 0$.
\end{proof}

According to the lemma, in this situation, $0<n$. So 0 either $<$ or $=$ $n$.

Assume that we have proven the statement for a natural number $m$, thus when $m<n$, according to 
Proposition \ref{prop.5}, $S(m) \leq n$, so $S(m)$ either $<$ or $=n$. When $m=n$, 
$S(m)=n+1 \Longrightarrow S(m) > n$ by Proposition \ref{prop.6}. When $m>n$, according to Proposition 
\ref{prop.6}, 
\[
m=n+p \Longrightarrow S(m)=n+(p+1) \Longrightarrow S(m)>n
\]. This closes the induction, implying that at least one of the three statements is true.
\end{proof}

\declareexercise{2.2.5}
\begin{proof}
Let $Q(n)$ be a property of a natural number $n$ such that $Q(n)$ is true iff for all $m_0\leq m'<n$, 
$P(m')$ is always true. Use induction: $Q(0)$ is vacuously true.

Assume that $Q(n)$ is true. Here we will be using the proposition we just proved, for because we have 
known that there will and only will be one true statement, we can classify the conditions as 
following: When $S(n)<m_0$, $Q(S(n))$ is also vacuously true. When $S(n)=m_0$, $Q(S(n))$ is true 
because $P(m_0)$ is true. And when $S(n)>m_0$:

First we need to prove that $n$ is the only natural number $\geq m_0$ which satisfies $m_0 \leq n<S(n)$ 
but doesn't satisfy $m_0 \leq n<n$, so that we only need to prove $P(n)$ is true in the induction, 
which is obvious.
\begin{lem}
There is no natural number between $n$ and $S(n)$. That is, there is no such natural number $m$ that 
$n<m<S(n)$. \label{lem5}
\end{lem}
\begin{proof}
Presume the negation. Thus, $m=n+p \wedge S(n)=m+q$, where $p,q$ are positive. Substituting $m$ 
with $n+p$ we have $S(n)=n+p+q$. Let $p=S(a)=a+1$, which is always possible according to Proposition 
\ref{prop5}. Thus $n+1=n+1+a+q \Longrightarrow n=n+a+q$, which means $a+q$ has to be 0, and which is 
impossible.
\end{proof}

Given a natural number $a$, it either $\geq$ or $<S(n)$, and also either $\geq$ or $<n$. Should it 
satisfy $m_0 \leq a<S(n)$ but doesn't satisfy $m_0 \leq a<n$, it then must satisfy $n \leq a<S(n)$, 
that is, either $a=n$ or $n<a<S(n)$. The latter, according to the lemma, is impossible. So $n$ is the 
only natural number $\geq m_0$ which satisfies $m_0 \leq n<S(n)$ but doesn't satisfy $m_0 \leq n<n$.

Then $Q(S(n)) \Longleftrightarrow Q(n) \wedge P(n)$, which is true. This closes the induction. So $Q(n)$ is 
true for all natural number $n \geq m_0$. And this implies that $P(n)$ is true.
\end{proof}

\declareexercise{2.2.6}
\begin{proof}
Use induction: When $n=0$, for all natural number $m\leq 0$, $P(m)$ is true.

Assume that we have proven for a natural number $n$ that if $P(n)$ is true, then for all natural number 
$m\leq n$, $P(m)$ is also true. Thus, $P(S(n)) \Longrightarrow P(n) \Longrightarrow \forall m\leq n, P(m)$
is true. According to Lemma \ref{lem5}, 
$(\forall m\leq n, P(m)) \wedge P(S(n)) \Longleftrightarrow \forall m \leq S(n), P(m)$. This closes the 
induction.
\end{proof}

\subsection{Multiplication of Natural Numbers}
\begin{lem}
(Exercise 2.3.1) \label{exercise2.3.1}
Multiplication is commutative. That is, $a \times b = b \times a$.
\end{lem}
\begin{proof} I

Try to imitate the way we prove the commutativity of addition.

\begin{lem}
\[
0 \times a = a \times 0 \label{lem2.3.1}
\]
\end{lem}
\begin{proof}
Use induction: $0 \times 0 = 0$. Assume that $n \times 0 = 0$ is 
true. Thus, $S(n) \times 0 = (n \times 0) + 0 = 0$, which closes the induction.
\end{proof}

\begin{lem}
\[
a \times S(b) = a \times b + a \label{lem2.3.2}
\]
\end{lem}
\begin{proof}
Use induction: $0 \times S(b) = 0 = 0 \times b + 0$.

Assume that $a \times S(b) = ab + a$ is true. Thus, 
\begin{align*}
S(a)S(b) 
&= aS(b) + S(b) \tag{By Def.}\\
&= ab + a + S(b) \tag{By assumption}\\
&= ab+S(a)+b \tag{By addition's properties}\\
&= (ab+b)+S(a) \tag{By addition's properties}\\
&= S(a)b + S(a) \tag{By Def.}
\end{align*}, which closes the induction.
\end{proof}

Now use induction on $a$. First, when $a=0$, by Lemma \ref{lem2.3.1} we have $ab=ba$. 

Assume that $ab=ba$ is true. Thus,
\begin{align*}
S(a)b
&=ab+b \\
&=ba+b  \\
&=bS(a) \tag{Lemma \ref{lem2.3.2}}
\end{align*}, which close the induction.

\end{proof}

\begin{proof} II In this proof we will use the distribution law of multiplication.

First, we have Lemma \ref{lem2.3.1}

Before we prove the remnant, we need to prove the distribution law. That 
is, $a \times (b+c) = ab + ac$ \label{distriLaw}
\begin{proof}
Use induction: $0 \times (b+c)= 0\times b+0\times c=0$.

Assume that $a \times (b+c) = ab + ac$ is ture. Thus, 
\begin{align*}
S(a) \times (b+c)
&= (a(b+c))+(b+c) \\
&= (ab+ac)+(b+c) \tag{By assumption} \\
&= (ab)+b+(ac)+c \\
&= S(a)b+S(a)c
\end{align*}, which closes the induction.
\end{proof}

We still have to prove $n \times 1 = n$ before proceeding. Use induction: $0 \times 1 = 0$. Assume that 
$n \times 1 = n$. Thus, $S(n) \times 1 = (n\times 1)+1=n+1=S(n)$.

Now we can proceed the proof. Assume that $a \times b = b \times a$. Thus, 
\begin{align*}
S(a)b
&= (ab)+b \\
&= (ba)+b \tag{By assumption} \\
&= b(a+1) \tag{By $b\times 1=b$ and the distribution law}\\
&= b \times S(a)
\end{align*}. This closes the induction.
\end{proof}

\begin{lem} \label{lem2.3.3}
(Exercise 2.3.2) \label{exercise2.3.2}
\[mn \neq 0 \Longleftrightarrow m \neq 0 \wedge n \neq 0\]
\end{lem}

\begin{proof}
On one hand,
let $m=S(a),\ n=S(b)$, where $a,b$ are natural numbers.
\begin{align*}
mn 
&= S(a)S(b) \\
&= aS(b) + S(b)
\end{align*}

which, if $a \neq 0$, is the sum of two positive numbers, and is thus positive, and which, if $a = 0$,
is a positive number $S(b)$.

On the other hand, if either of $m,n$ is 0, then $mn$ must be zero. So $mn \neq 0 \Longrightarrow m \neq 0 
\wedge n \neq 0$.
\end{proof}

Distribution law has been proved \hyperref[distriLaw]{here}.

\begin{prop}
(Exercise 2.3.3) \label{exercise2.3.3}
\[
(ab)c = a(bc)
\]
\end{prop}
\begin{proof}
Use induction on $a$.
First, $(0b)c=0c=0=0(bc)$.

Assume that $(ab)c = a(bc)$ is true. Thus, 
\begin{align*}
(S(a)b)c
&= (ab+b)c \\
&= c(ab+b) \tag{Commutativity} \\
&= c(ab) + cb \tag{Distribution law} \\
&= (ab)c + bc \tag{Commutativity} \\
&= a(bc) + bc \tag{The induction hypothesis} \\
&= S(a)(bc)
\end{align*}. And now we can close the induction.
\end{proof}

\begin{prop}
\label{prop2.3.1}
Multiplication preserves order. That is, if $a>b \wedge c>0$, then $ac > bc$.
\end{prop}
\begin{proof}
\begin{align*}
a>b 
&\Longrightarrow \\ a = b + p 
&\Longrightarrow \\ ac = bc + pc
\end{align*}
According to Lemma \ref{lem2.3.3}, $pc$ is positive. Therefore, $ac>bc$.
\end{proof}

\begin{coro}
Cancellation law. 
\[
ac=bc \wedge c \neq 0 \Longrightarrow a=b
\]
\end{coro}
\begin{proof}
Either $a=b$, or $a<b$, or $a>b$. Suppose that $a \neq b$. Therefore, $ac$ either $<$ or $>bc$, which, 
according to Proposition \ref{prop2.3.1}, gives a contradiction. So $a=b$.
\end{proof}

\begin{prop}
(Exercise 2.3.4) \label{exercise2.3.4}
\[
(a+b)^2=a^2+2ab+b^2
\]
(Suppose that we have known $n^2=n \times n$)
\end{prop}
\begin{proof}
\begin{align*}
(a+b)(a+b) 
&= (a+b)a+(a+b)b \tag{Distribution law} \\
&= a(a+b) + b(a+b) \tag{Commutativity} \\
&= a^2+ab+ba+b^2 \tag{Distribution law} \\
&= a^2+ab+ab+b^2 \tag{Commutativity}
\end{align*}

Now we prove that $2ab = ab+ab$.
\begin{align*}
2ab
&=S(1)ab \\
&=(1ab)+ab\\
&=(S(0)ab)+ab\\
&=(0ab+ab)+ab\\
&=ab+ab
\end{align*}

The proof is over. \qedhere
\end{proof}

\begin{prop}
(Exercise 2.3.5) \label{exercise2.3.5}
Euclidean algorithm. For any natural number $n$, positive number $p$, there exist natural numbers $m,r$ 
such that $n=mp+r$.
\end{prop}
\begin{proof}
For any natural number $p$, we induct on $n$. Firstly, $0=0p+0$. 

Assume that the statement for $n$ is true. We know that $r<p$. Then $S(r)$ either $=$ or $<p$ 
(Proposition \ref{prop.5}). On the latter case, simply let $r'=S(r),\ m'=m$, which satisfies the 
restriction $0\leq r' <p$ 

On the former case, let $m'=S(m),\ r'=0$, and we have
\begin{align*}
m'p+r'
&= S(m)p+0\\
&= mp + p\\
&= mp + S(r) \tag{$p=S(r)$}\\
&= S(mp+r)\\
&= S(n)
\end{align*}.
And now we can close the induction.
\end{proof}