(D2.2.1): Addition of natural numbers. Let \(m\) be a natural number. To add 0 to \(m\), define \(0+m=m\). Assume inductively we have defined how to add \(n\) to \(m\). Then we define \((n\texttt{++})+m=(n+m)\+\)
Note that we have not yet showed commutativity.
(L2.2.2): For every natural number \(n\), \(n+0=n\).
We prove this via induction. The base case is \(0+0\). The inductive case is when \(n+0=n\). We know that \((n\+)+0=(n+0)\+\) from the definition of addition.
(L2.2.3): For any natural numbers \(n,m\), we have \(n+(m\+)=(n+m)\+\)
To prove this, fix \(m\) and induct on \(n\). The base case is when \(n=0\). Then assume it is true for \(n\) and show it is true for \(n\+\). You do this by using the definition of addition as well as the inductive hypothesis.
Note: We can now say that \(n\+=n+1\).
Proof: \(n+1=n+(0\+)=(n+0)\+=n\+\)
(P2.2.4): Addition is commutative: \(n+m=m+n\)
Proof: Fix \(m\). Base case is when \(n=0\). Inductive hypothesis: It is true for \(n\), show that it is true for \(n\+\). Make use of L2.2.3.
(P2.2.5): Addition is associative: \(a+(b+c)=(a+b)+c\).
To prove this, fix \(a,b\) and induct on \(c\).
(P2.2.6): Cancellation Law: Let \(a,b,c\) be natural numbers such that \(a+b=a+c\). Then \(b=c\).
Note that we cannot invoke subtraction!
Proof: Induct on \(a\). The base case is trivial. Let it be true for \(a\). Now consider what happens if \((a\+)+b=(a\+)+c\). You can show this is equivalent to \((a+b)\+=(a+c)\+\). From the Peano axiom P2.4, this means \(a+b=a+c\) and the conclusion follows from the inductive hypothesis.
(D2.2.7) We define a positive natural number to be one that is not equal to 0.
(P2.2.8): Let \(a\) be positive and \(b\) a natural number. Then \(a+b\) (and \(b+a\)) is positive.
Assume otherwise. This means that \(a+b=0\). If \(b=0\), then \(a+0=0\) which implies \(a=0\) which is a contradiction. Thus, \(b\) is not 0. Therefore \(b\) is a successor to some natural number \(k\). Thus \(a+(k\+)=0\) But the LHS is \((a+k)\+\). We know that \(a+k\) is a natural number. However, Axiom 2.3 states that 0 is not the successor to any number, which is a contradiction. Thus if \(a\) is positive, there is no natural number such that \(a+b=0\).
You could also induct on \(b\).
(C2.2.9): Of course, as a corollary, if \(a+b=0\), then \(a=0,b=0\).
(L2.2.10): Let \(a\) be positive. Then there is exactly one \(b\) such that \(b\+=a\)
Proof: Assume \(b\ne c\) and \(b\+=c\+=a\). This violates Axiom 2.4.
It is a given that \(a\ne 0\). From A2.5, we can show that every non-zero number has a predecessor.
(D2.2.11): Ordering of the natural numbers. \(n\ge m\) iff \(n=m+a\) for some natural number \(a\). It is strictly greater than \(m\) if \(n\ge m\) and \(n\ne m\).
With this we can show there is no largest natural number because \(n\+>n\).
(P2.2.12) (Properties of ordering of natural numbers). Let \(a,b,c\) be natural numbers. Then the following properties hold:
- Reflexivity: \(a \geq a\)
- Transitivity: If \(a\ge b\) and \(b\ge c\) then \(a\ge c\)
- Anti-symmetry: If \(a\ge b\) and \(b\ge a\) then \(a=b\)
- Addition preserves order. \(a\ge b\) iff \(a+c\ge b+c\)
- \(a<b\) iff \(a\+\le b\)
- \(a<b\) iff \(b=a+d\) for some positive \(d\).
Proof of reflexivity: By definition, \(a\ge a\) iff \(a=a+n\) for some \(n\). Let \(n=0\)
Proof of transitivity: \(a\ge b\) implies \(a=b+m\). Similarly, \(b=c+n\). Substitute \(b\) into the first expression and use associativity to get \(a=c+(n+m)\).
Proof of anti-symmetry: We have \(a=b+n\) and \(b=a+m\). This means \(a=(a+m)+n\). Thus \(a=a+0=a+(m+n)\). Utilizing cancellation we get \(0=m+n\) and hence \(m=n=0\). Thus \(a=b\).
Proof of addition preserving order: Let \(a\ge b\). Then \(a=b+n\) and \(a+c=(b+n)+c\). Utilizing commutativity and associativity, we get \(a+c=(b+c)+n\) which gives \(a+c\ge b+c\).
Now let \(a+c\ge b+c\). Thus \(a+c=(b+c)+n\) Manipulate till we get \(a+c=(b+n)+c\). Utilize cancelation to get \(a=b+n\) and the conclusion follows.
Proof of 5: Let \(b>a\). Then \(b=a+m\) and \(b\ne a\). It follows that \(m\ne0\). Thus it has a predecessor. Let \(n\+=m\). Thus \(b=a+(n\+)=(a+n)\+=(a\+)+n\) which implies \(b\ge a\+\).
Conversely, let \(b\ge a\+\). Then \(b=(a\+)+m=(a+m)\+=a+(m\+)\). Since \(m\+\ne0\), we have \(b\ne a\). Thus \(b>a\).
Proof of 6: Let \(b>a\). Then \(b=a+d\) and \(b\ne a\). If \(d=0\) then \(b=a\), which is a contradiction. Hence \(d\) is positive.
Conversely, let \(b=a+d\) where \(d\) is positive. This means \(b\ge a\). Assume \(b=a\). This implies \(a=a+d\). \(a+0=a+d\) Using cancellation, we get \(d=0\) which is a contradiction. Hence \(b\ne a\).
(P2.2.13): Trichotomy of the natural numbers. If \(a,b\) are natural numbers, then exactly one of the following is true: \(a<b,a=b,a>b\)
Proof:
If \(a>b\), then clearly \(a\ne b\) Can \(a>b\) and \(b>a\) at the same time? If so, then \(b=a+m\) and \(a=b+n\) where \(m,n>0\). Substituting one equation into the other, we get \(b=a+m=(b+n)+m=b+(n+m)=b+0\). This implies \(m+n=0\) from cancellation, which implies \(m=n=0\), a contradiction.
Can none of these statements be true? Let’s prove one of them has to be true using induction. Fix \(b\). Let \(a=0\). If \(b=0\) then \(a=b\). If \(b>0\), then \(b=0+b\) which implies \(b\ge 0\). Since \(b\ne 0\), we have \(b>0\) and thus \(b>a\).
Now assume at least one of them is true for \(a\). Consider \(a\+\). If \(a>b\), then \(a=b+d\) with \(d\ne0\). And \(a\+=(b+d)\+=b+(d\+)\). Clearly, \(d++\ne0\) from Axiom 2.3. Thus \(a\+\ne b\) and \(a\+>b\).
If \(a=b\), then \(a\+=(b+0)\+=b+(0\+)=b+1\). Hence \(a\+>b\).
If \(a<b\), we know from P2.2.12 that \(a\+\le b\). This means either \(a\+=b\) or \(a\+<b\).
(P2.2.14): Strong principle of induction: Let \(m_{0}\) be a natural number and let \(P(m)\) be a property pertaining to any natural number \(m\). Now if, for each \(m\ge m_{0}\) we have the property that: If \(P(m')\) is true for all \(m_{0}\le m'<m\), then it is true for \(m\). If this holds, then \(P\) is true for all \(m\ge m_{0}\).
Proof:
Let \(Q(n)\) be the property that \(P(m)\) is true for all \(m_{0}\le m<n\) and apply induction on it. The base case \(n=0\) is vacuously true. If it is true for \(n\), then the induction hypothesis states it is true for all \(m\le m'\le n<n\+\). We know there is no number between \(n\) and \(n\+\). Thus it is true for \(n\+\).
How does this differ from the original principle of induction?
- We need not have 0 as the base case.
- We can have it true for multiple \(m'\).
Not sure if the second property is all that useful.
Finally, let’s discuss the Principle of Backwards Induction (E2.2.6): Let \(P(m)\) be a property for natural numbers such that when \(P(m\+)\) is true, so is \(P(m)\). If \(P(n)\) is true, then it is true for all natural \(m\le n\).
To prove this, apply induction on \(n\). The base case \(n=0\) is vacuously true. We should also prove that there is no natural number less than 0. For the general case \(n\+\), we need to show there is no natural number in between \(n\) and \(n\+\). Then we are done.
Finally, let’s prove a basic fact: \(n\+=n+1\). To show this, note that \(n\+=n\++0=(n+0)\+=n+(0\+)=n+1\)