$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 2.2: Natural Numbers. Induction

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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.}$