## Section B.12 Notation for Natural Numbers

In some sense, we already have a workable notation for natural numbers. In fact, we really didn't need a special symbol for \(s(0)\text{.}\) The natural number \(0\) and the sucessor function \(s\) are enough. For example, the positive integer associated with the number of fingers (including the thumb) on one hand is \(s(s(s(s(s(0)))))\text{,}\) our net worth is \(0\text{,}\) and the age of Professor Trotter's son in years when this section was first written was

Admittedly, this is not very practical, especially if some day we win the lottery or want to discuss the federal deficit. So it is natural (ugh!) to consider alternative notations.

Here is one such scheme. First, let's decide on a natural \(b>s(0)\) as base. We will then develop a notation which is called the base \(b\) notation. We already have a special symbol for zero, namely \(0\text{,}\) but we need additional symbols for each natural number \(n\) with \(0\lt n\lt b\text{.}\) These symbols are called digits. For example, the positive integer \(b=s(s(s(s(s(s(s(s(0))))))))\) is called eight, and it makes a popular choice as a base. Here are the symbols (digits) customarily chosen for this base: \(1=s(0)\text{,}\) \(2=s(1)\text{;}\) \(3=s(2)\text{;}\) \(4=s(3)\text{;}\) \(5=s(4)\text{;}\) \(6=s(5)\text{;}\) and \(7=s(6)\text{.}\) Technically speaking, it is not necessary to have a separate symbol for \(b\text{,}\) but it might be handy regardless. In this case, most people prefer the symbol \(8\text{.}\) We like this symbol, unless and until it gets lazy and lays down sideways.

So the first \(8\) natural numbers are then \(0\text{,}\) \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) \(4\text{,}\) \(5\text{,}\) \(6\) and \(7\text{.}\) To continue with our representation, we want to use the following basic theorem.

### Theorem B.34.

Let \(n,d\in \nonnegints\) with \(d>0\text{.}\) Then there exist unique natural numbers \(q\) and \(r\) so that \(n=qd+r\) and \(0\le r \lt d\text{.}\)

### Proof.

Let \(d\in \nonnegints\) with \(d>0\text{.}\) We first show that for each \(n\in\nonnegints\text{,}\) there exists \(q,r\in\nonnegints\) so that \(n=qd+r\) and \(0\le r\lt d\text{.}\) If \(n=0\text{,}\) we can take \(q=0\) and \(r=0\text{.}\) Now suppose that \(k=qd+r\) and \(0\le r\lt m\) for some \(k\in \nonnegints\text{.}\)

Note that \(r\lt d\) implies \(r+1\le d\text{.}\) If \(r+1\lt d\text{,}\) then \(k+1=qd+(r+1)\text{.}\) On the other hand, if \(r+1=d\text{,}\) then \(k+1=(q+1)d+0\text{.}\)

Now that existence has been settled, we note that the uniqueness of \(q\) and \(r\) follow immediately from the cancellation properties.

Now suppose that for some \(k\in \nonnegints\text{,}\) with \(k\ge 7\text{,}\) we have defined a base eight notation for the representation of \(k\text{,}\) for all \(n\) with \(0\le n\le k\text{,}\) and that in each case, this representation consists of a string of digits, written left to right, and selected from \(\{0,1,2,3,4,5,6,7\}\text{.}\) Write \(k+1=qb+r\) where \(0\le r\lt b\text{.}\) Note that \(q\le k\text{,}\) so that we already have a representation for \(q\text{.}\) To obtain a representation of \(k+1\text{,}\) we simply append \(r\) at the (right) end.

For example, consider the age of Professor Trotter's son. It is then written as 22. And to emphasize the base eight notation, most people would say \(22\text{,}\) base \(8\) and write \((22)_8\text{.}\)

Among the more popular bases are base 2, where only the digits 0 and 1 are used, and base sixteen, where sixteen is the popular word for \((20)_8\text{.}\) Here the digit symbols are

Another popular choice, in fact the one in most widespread use in banks, shopping centers and movie theatres, is base ten. Ten is the natural number A, base sixteen. Also, ten is \((12)_8\text{.}\) Most folks use the digits \(0,1,2,3,4,5,6,7,8,9\) for base ten notation. And when no other designation is made, then it is assumed that the natural number is written base ten. So of course, Professor Trotter's son is 18 and is a freshman at Georgia Tech. Which explains why his hair is as white as it is.

For any base \(b>1\text{,}\) caution must be exercised when discussing multiplication, since writing the product \(m\times n\) in the abbreviated form \(mn\) causes us some grief. For example, if \(b = 8\text{,}\) then writing the product \(372\times4885\) as \(3724885\) is ambiguous. For this reason, when using base \(b\) notation, the product symbol \(\times\) (or some variation of \(\times\)) is always used.

### Subsection B.12.1 Alternate Versions of Induction

Many authors prefer to start the development of number systems with the set of positive integers and defer the introduction of the concept of zero. In this setting, you have a non-empty set \(\posints\text{,}\) a one-to-one successor function \(s:\posints\injection\posints\) and a positive integer called one and denoted \(1\) that is not the successor of any positive integer. The Principle of Induction then becomes: If \(\mathbb{M}\subseteq\posints\text{,}\) then \(\mathbb{M} =\posints\) if and only if

\(1\in \mathbb{M}\text{;}\) and

\(\forall k\in \nonnegints\quad(k\in \mathbb{M}) \Longrightarrow(s(k)\in \mathbb{M})\text{.}\)

More generally, to show that a set \(\mathbb{M}\) contains all integers greater than or equal to an integer \(n\text{,}\) it is sufficient to show that (i) \(n\in\mathbb{M}\text{,}\) and (ii) For all \(k\in\ints,\,(k\in\mathbb{M}\Longrightarrow(k+1\in\mathbb{M})\text{.}\)

Here is another version of induction, one that is particularly useful in combinatorial arguments.

#### Theorem B.35.

Let \(\mathbb{M}\subseteq\posints\text{.}\) If \(\mathbb{M}\neq\posints\text{,}\) then there is a unique least positive integer \(n\) that does not belong to \(\mathbb{M}\text{.}\)