2.2: Natural Numbers. Induction

The element 1 was introduced in Axiom 4(b). Since addition is also assumed known, we can use it to define, step by step, the elements

$$2=1+1,3=2+1,4=3+1, \text{ etc.}$$

If this process is continued indefinitely, we obtain what is called the set $N$ of all natural elements in the given field $F .$ In particular, the natural elements of $E^{1}$ are called natural numbers. Note that

$$(\forall n \in N) \quad n+1 \in N$$

*A more precise approach to natural elements is as follows. $A$ subset $S$ of a field $F$ is said to be inductive iff

$$\begin{align} (i)& \hskip 4pt 1 \in S \text{ and } \\ (ii)& \hskip 4pt (\forall x \in S) \hskip 4pt x+1 \in S \end{align}$$

Such subsets certainly exist; e.g., the entire field $F$ is inductive since

$$1 \in F \text{ and } (\forall x \in F) \hskip 4pt x+1 \in F.$$

Define $N$ as the intersection of all inductive sets in $F$.

Theorem $\PageIndex{1}$

The set $N$ so defined is inductive itself. In fact, it is the "smallest" inductive subset of $F$ (i . e ., contained in any other such subset).

Proof

We have to show that

$$\begin{align} (i)& \hskip 4pt 1 \in N, \text{ and } \\ (ii)& \hskip 4pt (\forall x \in N) \hskip 4pt x+1 \in N. \end{align}$$

Now, by definition, the unity 1 is in each inductive set; hence it also belongs to the intersection of such sets, i.e., to $N .$ Thus $1 \in N,$ as claimed.

Next, take any $x \in N .$ Then, by our definition of $N, x$ is in each inductive set $S ;$ thus, by property $(i i)$ of such sets, also $x+1$ is in each such $S$ ; hence $x+1$ is in the intersection of all inductive sets, i.e.,

$$x+1 \in N$$

and so $N$ is inductive, indeed.

Finally, by definition, $N$ is the common part of all such sets and hence contained in each. $\square$

For applications, Theorem 1 is usually expressed as follows.

Theorem $\PageIndex{1'}$

(first induction law). A proposition $P(n)$ involving a natural $n$ holds for all $n \in N$ in a field $F$ if

$$\begin{align} (i)& \text{ it holds for } n=1,\text{ i.e., } P(1) \text{ is true; and } \\ (ii)& \text{ whenever } P(n) \text{ holds for } n=m, \text{ it holds for } n=m+1, \text{ i.e., } \end{align}$$

$$P(m) \Longrightarrow P(m+1).$$

Proof

Let $S$ be the set of all those $n \in N$ for which $P(n)$ is true,

$$S=\{n \in N | P(n)\}$$

We have to show that actually each $n \in N$ is in $S,$ i.e., $N \subseteq S$

First, we show that $S$ is inductive.

Indeed, by assumption $(\mathrm{i}), P(1)$ is true; so 1$\in S$.

Next, let $x \in S .$ This means that $P(x)$ is true. By assumption (ii), however, this implies $P(x+1),$ i.e., $x+1 \in S .$ Thus

$$1 \in S \text{ and } (\forall x \in S) \hskip 4pt x+1 \in S$$

$S$ is inductive.

Then, by Theorem 1 (second clause), $N \subseteq S,$ and all is proved. $\square$

This theorem is used to prove various properties of $N$ "by induction."

Example $\PageIndex{1}$

(a) If $m, n \in N,$ then also $m+n \in N$ and $m n \in N$.

To prove the first property, fix any $m \in N .$ Let $P(n)$ mean

$$m+n \in N \quad(n \in N)$$

Then

(i) $P(1)$ is true, for as $m \in N,$ the definition of $N$ yields $m+1 \in N$, i.e., $P(1)$.

(ii) $P(k) \Rightarrow P(k+1)$ for $k \in N .$ Indeed,

$$\begin{align} P(k) \Rightarrow& m+k \in N \Rightarrow(m+k)+1 \in N\ \\ \Rightarrow& m+(k+1) \in N \Rightarrow P(k+1) \end{align}$$

Thus, by Theorem $1^{\prime}, P(n)$ holds for all $n ;$ i.e.,

$(\forall n \in N) \quad m+n \in N$

for any $m \in N$.

To prove the same for $m n,$ we let $P(n)$ mean

$m n \in N \quad(n \in N)$

and proceed similarly.

(b) If $n \in N,$ then $n-1=0$ or $n-1 \in N$.

For an inductive proof, let $P(n)$ mean

$$n-1=0 \text{ or } n-1 \in N \quad(n \in N)$$

Then proceed as in (a).

(c) In an ordered field, all naturals are $\geq 1$.

Indeed, let $P(n)$ mean that

$$n \geq 1 \quad(n \in N).$$

Then

(i) $P(1)$ holds since $1=1$
(ii) $P(m) \Rightarrow P(m+1)$ for $m \in N,$ since

$$P(m) \Rightarrow m \geq 1 \Rightarrow(m+1)>1 \Rightarrow P(m+1)$$

Thus Theorem $1^{\prime}$ yields the result.

(d) In an ordered field, $m, n \in N$ and $m>n$ implies $m-n \in N$
For an inductive proof, fix any $m \in N$ and let $P(n)$ mean

$$m-n \leq 0 \text{ or } m-n \in N \quad(n \in N).$$

Use (b).

(e) In an ordered field, $m, n \in N$ and $m<n+1$ implies $m \leq n$
For, by $(\mathrm{d}), m>n$ would imply $m-n \in N,$ hence $m-n \geq 1,$ or $m \geq n+1,$ contrary to $m<n+1$.

Our next theorem states the so-called well-ordering property of $N$.

Theorem $\PageIndex{2}$ (well-ordering of N)

In an ordered field, each nonvoid set $A \subseteq N$ has a least member (i.e., one that exceeds no other element of $A )$.

Proof

The following is just an outline of a proof:

Given $\emptyset \neq A \subseteq N,$ let $P(n)$ be the proposition "Any subset of $A$ containing elements $\leq n$ has a least member" $(n \in N) .$ Use Theorem $1^{\prime}$ and Example (e) . $\square$

This theorem yields a new form of the induction law.

Theorem $\PageIndex{2'}$ (second induction law)

A proposition $P(n)$ holds for all $n \in N$

(i') $P(1)$ holds and
(ii') whenever $P(n)$ holds for all naturals less than some $m \in N,$ then $P(n)$
also holds for $n=m$.

Proof

Assume $\left(\mathrm{i}^{\prime}\right)$ and $\left(\mathrm{ii}^{\prime}\right) .$ Seeking a contradiction, suppose there are some $n \in N($ call them "bad") for which $P(n)$ fails. Then these "bad" naturals form a nonvoid subset of $N,$ call it $A$.

By Theorem $2, A$ has a least member $m .$ Thus $m$ is the least natural for which $P(n)$ fails. It follows that all $n$ less than $m$ do satisfy $P(n) .$ But then, by our assumption (ii'), $P(n)$ also holds for $n=m,$ which is impossible for, by construction, $m$ is "bad" (it is in $A ) .$ This contradiction shows that there are no "bad" naturals. Thus all is proved. $\square$

Note 1: All the preceding arguments hold also if, in our definition of $N$ and all formulations, the unity 1 is replaced by 0 or by some $k( \pm k \in N)$. Then, however, the conclusions must be changed to say that $P(n)$ holds for all integers $n \geq k$ (instead of "n \geq 1 "). We then say that "induction starts with $k .$"

An analogous induction law also applies to definitions of concepts $C(n)$.

$A$ notion $C(n)$ involving a natural $n$ is regarded as defined for each $n \in N$ $\left(i n E^{1}\right)$ if

(i) $i t$ is defined for $n=1$ and

(ii) some rule is given that expresses $C(n+1)$ in terms of $C(1), \ldots, C(n)$.

(Note 1 applies here, too.)

$C(n)$ itself need not be a number; it may be of quite general nature.

We shall adopt this principle as a kind of logical axiom, without proof (though it can be proved in a similar manner as Theorems $1^{\prime}$ and $2^{\prime} ) .$ The underlying intuitive idea is a "step-by-step" process - first, we define $C(1) ;$ then, as $C(1)$ is known, we may use it to define $C(2) ;$ next, once both are known, we may use them to define $C(3) ;$ and so on, ad infinitum. Definitions based on that principle are called inductive or recursive. The following examples are important.

Example $\PageIndex{1}$ (continued)

(f) For any element $x$ of a field, we define its $n^{th}$ power $x^{n}$ and its $n$-multiple $n x$ by

(i) $x^{1}=1 x=x$
(ii) $x^{n+1}=x^{n} x$ (respectively, $(n+1) x=n x+x )$.

We may think of it as a step-by-step definition:

$$x^{1}=x, x^{2}=x^{1} x, x^{3}=x^{2} x, \text{ etc.}$$

(g) For each natural number $n,$ we define its factorial $n !$ by

$$1 !=1,(n+1) !=n !(n+1);$$

e.g. $, 2 !=1 !(2)=2,3 !=2 !(3)=6,$ etc. We also define $0 !=1$.

(h) The sum and product of n field elements $x_{1}, x_{2}, \dots, x_{n},$ denoted by

$$\sum_{k=1}^{n} x_{k} \text{ and } \prod_{k=1}^{n} x_{k}$$

or

$$x_{1}+x_{2}+\cdots+x_{n} \text{ and } x_{1} x_{2} \cdots x_{n}, \text{ respectively}$$

are defined recursively.

Sums are defined by

$$\begin{align} (i)& \hskip 4pt \sum_{k=1}^{1} x_{k}=x_{1} \\ (ii)& \hskip 4pt \sum_{k=1}^{n+1} x_{k}=\left(\sum_{k=1}^{n} x_{k}\right)+x_{n+1}, n=1,2, \ldots \end{align}$$

Thus

$$x_{1}+x_{2}+x_{3}=\left(x_{1}+x_{2}\right)+x_{3}$$

$$x_{1}+x_{2}+x_{3}+x_{4}=\left(x_{1}+x_{2}+x_{3}\right)+x_{4}, \text{ etc.}$$

Products are defined by

$$\begin{align}(i)& \hskip 4pt \prod_{k=1}^{1} x_{k}=x_{1} \\ (ii)& \hskip 4pt \prod_{k=1}^{n+1} x_{k}=\left(\prod_{k=1}^{n} x_{k}\right) \cdot x_{n+1} \end{align}$$

(i) Given any objects $x_{1}, x_{2}, \dots, x_{n}, \ldots,$ the ordered n-tuple

$$\left(x_{1}, x_{2}, \ldots, x_{n}\right)$$

is defined inductively by

(i) $\left(x_{1}\right)=x_{1}$ (i.e., the ordered "one-tuple" $\left(x_{1}\right)$ is $x_{1}$ itself $)$ and

(ii) $\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)=\left(\left(x_{1}, \ldots, x_{n}\right), x_{n+1}\right),$ i.e., the ordered $(n+1)-$ tuple is a pair $\left(y, x_{n+1}\right)$ in which the first term $y$ is itself an ordered $n$ -tuple, $\left(x_{1}, \ldots, x_{n}\right) ;$ for example,

$$\left(x_{1}, x_{2}, x_{3}\right)=\left(\left(x_{1}, x_{2}\right), x_{3}\right), \text{ etc.}$$