Subsection B.7.1 Addition as a Binary Operation
A binary operation \(*\) on set \(X\) is just a function \(*:X\times X\rightarrow X\text{.}\) So the image of the ordered pair \((x,y)\) would normally be denoted \(*((x,y))\text{.}\) However, this is usually abbreviated as \(*(x,y)\) or even more compactly as \(x*y\text{.}\) With this convention, we now define a binary operation \(+\) on the set \(\nonnegints\) of natural numbers. This operation is defined as follows for every natural number \(n\in\nonnegints\text{:}\)
\(n+0=n\text{.}\)
For all \(k\in\nonnegints\text{,}\) \(n+s(k) = s(n+k)\text{.}\)
We pause to make it clear why the preceding two statements define \(+\text{.}\) Let \(n\) be an arbitrary natural number. Then let \(\mathbb{M}\) denote the set of all natural numbers \(m\) for which \(n+m\) is defined. Note that \(0\in \mathbb{M}\) by part (i). Also note that for all \(k\in \nonnegints\text{,}\) \(s(k)\in \mathbb{M}\) whenever \(k\in \mathbb{M}\) by part (ii). This shows that \(\mathbb{M}=\nonnegints\text{.}\) Since \(n\) was arbitrary, this allows us to conclude that \(n+m\) is defined for all \(n,m\in \nonnegints\text{.}\)
We read \(n+m\) as \(n\) plus \(m\text{.}\) The operation \(+\) is also called addition.
Among the natural numbers, the successor of zero plays a very important role, so important that it deserves its own special symbol. Here we follow tradition and call the natural number \(s(0)\) one and denote it by \(1\text{.}\) Note that for every natural number \(n\text{,}\) we have \(n+1=n+s(0)=s(n)\text{.}\) In particular, \(0+1=1\text{.}\)
With this notation, the Principle of Induction can be restated in the following form.
Principle B.14. Principle of Induction.
Let \(\mathbb{M}\subseteq \nonnegints\text{.}\) Then \(\mathbb{M} =\nonnegints\) if and only if
\(0\in \mathbb{M}\text{;}\) and
\(\forall k\in \nonnegints\quad(k\in \mathbb{M})
\Longrightarrow(k+1\in \mathbb{M})\text{.}\)
Theorem B.15. Associative Property of Addition.
\(m+(n+p) = (m+n)+p\text{,}\) for all \(m,n,p\in \nonnegints\text{.}\)
Proof.
Let \(m,n\in \nonnegints\text{.}\) Then let \(\mathbb{M}\) denote the set of all natural numbers \(p\) for which \(m+(n+p)=(m+n)+p\text{.}\) We show that \(\mathbb{M}=\nonnegints\text{.}\)
Note that
\begin{equation*}
m+(n+0) = m+n = (m+n)+0
\end{equation*}
which shows that \(0\in \mathbb{M}\text{.}\)
Now assume that \(k\in \mathbb{M}\text{,}\) i.e., \(m+(n+k) = (m+n)+k\text{.}\) Then
\begin{equation*}
m+[n+(k+1)]=m+[(n+k)+1]=[m+(n+k)]+1= [(m+n)+k]+1=(m+n)+(k+1).
\end{equation*}
Notice here that the first, second, and fourth equalities follow from the second part of the definition of addition while the third uses our inductive assumption that \(m+(n+k)=(m+n)+k)\text{.}\) This shows that \(k+1\in \mathbb{M}\text{.}\) Therefore, \(\mathbb{M}= \nonnegints\text{.}\) Since \(m\) and \(n\) were arbitrary elements of \(\nonnegints\text{,}\) the theorem follows.
In proofs to follow, we will trim out some of the wording and leave only the essential mathematical steps intact. In particular, we will (i) omit reference to the set \(\mathbb{M}\text{,}\) and (ii) drop the phrase “For all \(k\in\nonnegints\)” For example, to define addition, we will just write (i) \(n+0=n\text{,}\) and (ii) \(n+(k+1) = (n+k)+1\text{.}\)
Lemma B.16.
\(m+(n+1) = (m+1)+n\text{,}\) for all \(m,n\in\nonnegints\text{.}\)
Proof.
Fix \(m\in \nonnegints\text{.}\) Then
\begin{equation*}
m+(0+1)=m+1= (m+0)+1.
\end{equation*}
Now assume that \(m+(k+1)=(m+1)+k\text{.}\) Then
\begin{equation*}
m+[(k+1)+1]=[m+(k+1)]+1=[(m+1)+k]+1=(m+1)+(k+1).
\end{equation*}
We next prove the commutative property, a task that takes two steps. First, we prove the following special case.
Lemma B.17.
\(n+0 = 0+n=n\text{,}\) for all \(n\in \nonnegints\text{.}\)
Proof.
The statement is trivially true when \(n= 0\text{.}\) Now suppose that \(k+0=0+k=k\) for some \(k\in \nonnegints\text{.}\) Then
\begin{equation*}
(k+1) +0 = k+1 = (0+k)+1= 0+(k+1).
\end{equation*}
Theorem B.18. Commutative Law of Addition.
\(m+n=n+m\) for all \(m,n\in \nonnegints\text{.}\)
Proof.
Let \(m\in \nonnegints\text{.}\) Then \(m+0=0+m\) from the preceding lemma. Assume \(m+k=k+m\text{.}\) Then
\begin{equation*}
m+(k+1)=(m+k)+1=(k+m)+1= k+(m+1) = (k+1)+m.
\end{equation*}
Lemma B.19.
If \(m,n\in\nonnegints\) and \(m+n=0\text{,}\) then \(m=n=0\text{.}\)
Proof.
Suppose that either of \(m\) and \(n\) is not zero. Since addition is commutative, we may assume without loss of generality that \(n\neq0\text{.}\) Then there exists a natural number \(p\) so that \(n=s(p)\text{.}\) This implies that \(m+n=m+s(p)=s(m+p)=0\text{,}\) which is impossible since \(0\) is not the successor of any natural number.
Theorem B.20. Cancellation Law of Addition.
If \(m,n,p\in \nonnegints\) and \(m+p=n+p\text{,}\) then \(m=n\text{.}\)
Proof.
Let \(m,n\in \nonnegints\text{.}\) Suppose that \(m+0=n+0\text{.}\) Then \(m=n\text{.}\) Now suppose that \(m=n\) whenever \(m+k=n+k\text{.}\) If \(m+(k+1)=n+(k+1)\text{,}\) then
\begin{equation*}
s(m+k)=(m+k)+1=m+(k+1)=n+(k+1)=(n+k)+1=s(n+k).
\end{equation*}
Since \(s\) is an injection, this implies \(m+k=n+k\text{.}\) Thus \(m=n\text{.}\)