11.2 Arithmetic
So we have a collection of very fundamental properties (axioms) that \(\mathbb N\) satisfies based on those we might expect ordinals to have, but notice that at no point have we used a ‘\(+\)’ sign or a ‘\(\ast\)’ sign. We now show how to introduce the cardinal properties which allow us to perform arithmetic operations with \(\mathbb N\). Intuitively, it should be clear that the purpose of the successor function \(s\) is to represent the idea of ‘adding 1’. How do we do that formally?
We define the binary operation of addition using an inductive process.
Let \(x,y\in\mathbb N\) and define \[ x+y=\begin{cases}x&\text{if }y=0\\s(x+z)&\text{if }y=s(z), z\in\mathbb N.\end{cases} \]
\(1+1=2\).
Proof. \[ 1+1 = 1+s(0) = s(1+0) = s(1) = 2. \]
We can (easily) demonstrate that all the basic properties of addition can be derived from these axioms and this definition. For example
For all \(x,y\in\mathbb N, x+y=y+x\).
Proof. We use the principle of induction for this, but note that we actually use three inductive arguments. Let \[ A=\{x\in\mathbb N|x+y=y+x\text{ for all }y\in\mathbb N\}. \] If we can show that the set \(A\) satisfies the conditions of axiom 3 then \(A=\mathbb N\) and so the theorem is true. To show that \(0\in A\) we let \[ B=\{y\in\mathbb N|0+y=y+0\}. \] Since it is clear that \(0+0=0+0\) (actually we really need the missing axioms from Peano’s list to deduce this formally) then \(0\in B\). Now suppose that \(y\in B\) and consider \(s(y)\). Then \[ \begin{array}{rcll} 0+s(y)&=&s(0+y)\\ &=&s(y+0)&\text{ since }y\in B\\ &=&s(y)&\text{ by definition of }+\\ &=&s(y)+0&\text{ by definition of }+ \end{array} \] and so it follows that \(s(y)\in B\). Consequently \(B\) satisfies the conditions of axiom 3 and so \(B=\mathbb N\). This is equivalent to saying that \(0\in A\).
Now suppose that \(x\in A\) and consider \(s(x)\). We wish to show that \(s(x)\in A\) and to do so consider \[ C=\{y\in\mathbb N|y+s(x)=s(x)+y\}. \] Since \(B=\mathbb N\) then \(0\in C\). Now suppose that \(y\in C\) and consider \(s(y)\). \[ \begin{array}{rcll} s(y)+s(x)&=&s(s(y)+x)&\text{by definition of }+\\ &=&s(x+s(y))&\text{ since }x\in A\\ &=&s(s(x+y))&\text{ by definition of }+\\ &=&s(s(y+x))&\text{since }x\in A\\ &=&s(y+s(x))&\text{by definition of }+\\ &=&s(s(x)+y)&\text{since }y\in C\\ &=&s(x)+s(y)&\text{by definition of }+ \end{array} \] and so \(s(y)\in C\). Consequently, \(C\) satisfies the conditions of axiom 3 and so \(C=\mathbb N\). This is equivalent to saying that \(s(x)\in A\) and so \(A\) satisfies the conditions of axiom 3 and so \(A=\mathbb N\) as required.
For all \(x,y,z\in\mathbb N, (x+y)+z=x+(y+z)\).
The proof is left as an exercise, albeit a rather tricky one.
We cannot subtract natural numbers in general but we do have
For all \(x,y,z\in \mathbb N\), if \(x+z=y+z\) then \(x=y\).
Proof. Let \(A=\{z\in\mathbb N| x=y\text{ whenever }x+z=y+z\}\). Then since \(x+0=x\) and \(y+0=y\) then it is clear that \(0\in A\). Now suppose that \(z\in A\) and consider \(s(z)\). Suppose that \(x+s(z)=y+s(z)\) for some \(x,y\in \mathbb N\). Then \(s(x+z) = s(y+z)\) and since \(s\) is an injection then \(x+z=y+z\). Since \(z\in A\) then \(x=y\) and so \(s(z)\in A\). Hence \(A\) satisfies the conditions of axiom 3 and so \(A=\mathbb N\) as required.
If \(x+y=0\) then \(x=y=0\).
Proof. If \(y\not=0\) then \(y=s(z)\) for some \(z\in\mathbb N\) and so \(0=x+y=s(x+z)\). But \(0\not\in\text{ im }(s)\) and so we have a contradiction and hence \(y=0\). Consequently \(x=x+0=x+y=0\) and the result follows.
Once we have defined addition we can proceed to define multiplication, \(\ast\), in a similar fashion.
Let \(x,y\in \mathbb N\) and define \[ x\ast y=\begin{cases}0&\text{if }y=0\\x+x\ast z&\text{if }y=s(z), z\in\mathbb N.\end{cases} \]
Hence \[ \begin{array}{rcl} x\ast0&=&0\\ x\ast1&=&x\ast s(0) = x+x\ast0 = x+0=x\\ x\ast2&=&x\ast s(1) = x+x\ast1 = x+x\\ \end{array} \] and so on.
\[2*2=4\]
Proof. \[\begin{gather*} 2*2 = 2*s(1) = 2+2*1 = 2 + 2*s(0) = 2 + 2 + 2*0 = 2+2 +0 = 2+2\\= 2+s(1) = s(2+1) = s(2+s(0)) = s(s(2+0)) = s(s(2)) = s(3) = 4. \end{gather*}\]
Let \(x,y,z\in\mathbb N\). Then
- \(x\ast y = y\ast x\);
- \((x\ast y)\ast z = x\ast (y\ast z)\);
- \((x+y)\ast z = x\ast z + y\ast z\)
Returning to our ordinal view of \(\mathbb N\), we can finally define a partial order on \(\mathbb N\) as follows. Let \(x,y\in\mathbb N\). We define \[ x\le y\text{ if and only if }x=0\text{ or }\exists z,w\in\mathbb N\text{ such that }x=s(z), y=s(w)\text{ and }z\le w. \] It is straightforward to show that \(\le\) is a partial order (reflexive, anti-symmetric and transitive)
\(\le\) is a partial order.
Proof. Notice first that \(\{x\in\mathbb N|s(x)\le 0\}=\emptyset\). This is because, otherwise \(0=s(w)\) and \(x\le w\). But this is a contradiction by axiom 2.
- Let \(A = \{x\in\mathbb N|x\le x\}\). Clearly \(0\in A\) and if \(x\in A\) then \(x\le x\) and so \(s(x)\le s(x)\) which means that \(s(x)\in A\). Hence by axiom 3 \(A=\mathbb N\) and \(\le\) is reflexive.
- Let \(B = \{x\in\mathbb N|\text{ if }\exists y\in\mathbb N, x\le y\land y\le x\text{ then } x=y\}\). Suppose that \(\exists y\in\mathbb N\) such that \(0\le y\land y\le 0\). Then \(y=0\) by the above remark. Hence \(0\in B\). Suppose now that \(x\in B\) and suppose that \(\exists y\in\mathbb N\) such that \(s(x)\le y\land y\le s(x)\). Then as \(s(x)\ne 0\) it follows that \(\exists w\in \mathbb N\) such that \(y=s(w)\) and \(x\le w\land w\le x\). Hence \(x=w\) as \(x\in B\). Consequently, \(s(x)=s(w) = y\) and so \(s(x)\in B\). By axiom 3, \(B=\mathbb N\) and \(\le\) is anti-symmetric.
- Let \(C=\{x\in\mathbb N|\text{ if }\exists y,z\in\mathbb N, x\le y\land y\le z\text{ then }x\le z\}\). Since \(0\le z\) for all \(z\in\mathbb N\) then \(0\in C\). Suppose now that \(x\in C\) and that \(\exists y,z\in\mathbb N\) such that \(s(x)\le y\land y\le z\). Then by the above remark, \(y\ne0\) and so \(y=s(a)\) and \(x\le a\). From the second inequality, \(z=s(b)\) and \(a\le b\). Since \(x\in C\) then \(x\le b\) and so \(s(x)\le s(b)\) and \(s(x)\in C\) as required. Hence \(C=\mathbb N\) and \(\le\) is transitive.
A more useful and practical definition is given in the following theorem.
For all \(x,y\in\mathbb N\) \[ x\le y\text{ if and only if there exists }z\in\mathbb N\text{ such that }x+z=y. \]
Proof. Let \(A=\{x\in\mathbb N|\text{ if }\exists y\in\mathbb N\ x\le y\text{ then }\exists z\in\mathbb N\ x+z=y\}\). Suppose that \(\exists y\in\mathbb N\ 0\le y\). Then \(0+y = y+0 = y\) and so \(0\in A\). Suppose now that \(x\in A\) and suppose also that \(\exists y\in\mathbb N\ s(x)\le y\). Then \(\exists z\in \mathbb N\ y=s(z)\land x\le z\). Since \(x\in A\) then \(\exists w\in\mathbb N\ x+w=z\). Hence \[ y=s(z) = s(x+w) = s(w+x) = w+s(x) = s(x)+w \] and so \(s(x)\in A\). By axiom 3, \(A=\mathbb N\).
Conversely let \(B=\{x\in\mathbb N|\text{ if }\exists y,z\in\mathbb N\ x+z=y\text{ then }x\le y\}\). Since \(0\le y\) for all \(y\in\mathbb N\) then \(0\in B\). Suppose now that \(x\in B\) and that \(\exists y,z\in\mathbb N\ s(x)+z=y\). Now \(y = s(x)+z = z+s(x) = s(z+x) = s(x+z)\) and since \(x\in B\) then \(x\le x+z\) and so \(s(x)\le s(x+z)=y\). Hence \(s(x)\in B\) and so \(B=\mathbb N\) by axiom 3.
For all \(x\in\mathbb N, x\le s(x)\). Moreover, if \(x\le y\le s(x)\) then either \(y=x\) or \(y=s(x)\).
Proof. Since \(x+1=s(x)\) then the result follows from Theorem 11.11. Suppose now that \(x\le y\le s(x)\) and that \(x\not=y\). Then there exists \(w,z\in\mathbb N\) such that \(x+w=y, y+z=s(x)\) and since \(y\ne x\) then \(w\ne0\) and so \(w=s(w')=w'+1\) for some \(w'\in\mathbb N\). Hence \(x+(w+z) = y+z=s(x)=x+1\) and so \(w+z=1\) by Theorem 11.5. But then \((w'+z)+1 = w+z=1=0+1\) and so \(w'+z=0\) again by Theorem 11.5. Hence by Lemma 11.6, \(w'=z=0\) and so \(y=y+0=s(x)\) as required.
Let \(x,y,z\in\mathbb N\). Then
- either \(x\le y\) or \(y\le x\) (\(\le\) is a total order);
- if \(x\le y\) then \(x+z\le y+z\) and \(x\ast z\le y\ast z\) (notice that, in particular \(s(x)\le s(y)\) and so \(s\) is monotonic);
- any non-empty set of natural numbers has a least element (‘The Well Ordering Principle’).
Proof. Let \(x,y,z \in\mathbb N\).
- Let \(x\in\mathbb N\) and let \(A_x=\{y\in\mathbb N|\text{either }x\le y\text{ or }y\le x\}\). We show that \(A_x=\mathbb N\). By definition, \(0\in A_x\). Suppose that \(y\in A_x\) and consider \(s(y)\). If \(x\le y\) then by lemma 11.12, \(x\le s(y)\) by transitivity of \(\le\) and so \(s(y)\in A_x\). On the other hand if \(y\le x\) then \(y+z=x\) for some \(z\in\mathbb N\). If \(z=0\) then \(x=y\), and so \(s(x)=s(y)\) and by Lemma 11.12, \(x\le s(y)\) and again \(s(y)\in A_x\). Otherwise \(z=s(w)=w+1\) for some \(w\in\mathbb N\). Hence \(s(y)+w = (y+1)+w=y+(w+1)=y+z=x\) and so \(s(y)\le x\). Hence \(s(y)\in A_x\) as required and so \(A_x\) satisfies the conditions of axiom 3 and therefore \(A_x=\mathbb N\).
- If \(x\le y\) then there exists \(w\in\mathbb N\) such that \(x+w=y\). Consequently \((x+z)+w=(x+w)+z=y+z\) and so \(x+z\le y+z\). Similarly, \(x\ast z +w\ast z=y\ast z\) and so \(x\ast z\le y\ast z\).
- Let \(\emptyset\not=B\subseteq\mathbb N\) and suppose, by way of contradiction, that \(B\) has no least element. Let \(A=\{x\in\mathbb N|y\notin B\text{ for all }y\le x\}\). Then \(0\in A\) by definition, since if \(0\in B\) then it would be the least element of \(B\). Suppose that \(x\in A\) and consider \(s(x)\). We wish to show that \(s(x)\in A\) or in other words, \(s(x)\not\in B\) and \(y\notin B\) whenever \(y\le s(x)\). We prove both these parts separately. First, suppose, by way of contradiction, that \(s(x)\in B\). Then for any \(z\in B\) it follows by part (1), and since \(x\in A\), that \(x\le z\) and \(x\not= z\) (otherwise, we would have \(z\le x\) and \(x\in A\) so \(z\notin B\)). So there exists \(w\in\mathbb N\) such that \(x+w=z\) and \(w\not=0\). Hence \(w=s(w')\) for some \(w'\in\mathbb N\) and so \(s(x)+w'=(x+1)+w' = x+ (w'+1) = x+s(w') = x+w=z\). Consequently, \(s(x)\le z\) and so \(s(x)\) is the least element of \(B\). But this is a contradiction and so \(s(x)\notin B\). Now if \(y\le s(x)\) then \(y+w=s(x)\) for some \(w\in\mathbb N\). If \(w=0\) then \(y=s(x)\), while if \(w=s(w')=w'+1\) for some \(w'\in\mathbb N\) then \((y+w')+1 = y+w=s(x)=x+1\). Hence by Theorem 11.5, \(y+w'=x\) and so \(y\le x\). Since \(x\in A\) then \(y\notin B\). Either way it follows that \(y\notin B\). Therefore \(s(x)\in A\) and so \(A\) satisfies the conditions of axiom 3 and hence \(A=\mathbb N\). Consequently \(B=\emptyset\) which is a contradiction and so \(B\) has a least element.
This means that Peano’s axioms imply the 10 axioms we introduced at the start of the course, that relate to positive integers.