Proposition B.13.
Let \(n\) be a natural number with \(n\neq0\text{.}\) Then there is a natural number \(m\) so that \(n=s(m)\text{.}\)
Section B.7 Formal Development of Number Systems
Up to this point, we have been discussing number systems in an entirely informal manner, assuming everyone knew all that needed to be known. Now let’s pause and put things on a more firm foundation. So for the time being, do a memory dump and forget everything you have ever learned about numbers and arithmetic. The set of natural numbers has just been delivered on our door step in a big box with a warning label saying Assembly Required. We open the box and find a single piece of paper on which the following “instructions” are printed. These defining properties of the natural numbers are known as the Peano Postulates.
-
There is a non-empty set of elements called natural numbers. There is natural number called zero which is denoted \(0\text{.}\) The set of all natural numbers is denoted \(\nonnegints\)
-
There is a one-to-one function \(s:\nonnegints \injection \nonnegints\) called the successor function. For each \(n\in \nonnegints\text{,}\) \(s(n)\) is called the successor of \(n\text{.}\)
-
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(s(k)\in \mathbb{M})\text{.}\)
-
Property Item iv in the list of Peano Postulates is called the Principle of Mathematical Induction, or just the Principle of Induction. As a first application of the Principle of Induction, we prove the following basic property of the natural numbers.
Proof.
Let \(\mathbb{S}=\{n\in\nonnegints:\exists m\in\nonnegints, n=s(m)\}\text{.}\) Then set \(\mathbb{M}=\{0\}\cup\mathbb{S}\text{.}\) We show that \(\mathbb{M}=\nonnegints\text{.}\) First, note that \(0\in\mathbb{M}\text{.}\) Next, we will show that for all \(k\in\nonnegints\text{,}\) if \(k\in\mathbb{M}\text{,}\) then \(s(k)\in\mathbb{M}\text{.}\) However, this is trivial since for all \(k\in\nonnegints\text{,}\) we have \(s(k)\in\mathbb{S}\subseteq\mathbb{M}\text{.}\) We conclude that \(\mathbb{M}=\nonnegints\text{.}\)
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{.}\)
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{.}\)
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.
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.
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.
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.
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.
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.
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{.}\)
You have attempted of activities on this page.
