3.1 Natural Numbers and Induction

3.1   Definition (Inductive set.) Let $F$ be a field. A subset $J$ of $F$ is inductive if it satisfies the two conditions:

i)

$0\in J$.

ii)

for all $x\in F$, $\left((x\in J)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(x+1)\in J\right)$.

3.2   Examples. $\mbox{{\bf Z}},\mbox{{\bf N}}$ and $\mbox{{\bf Q}}$ are inductive sets in $\mbox{{\bf Q}}$. Every field is an inductive subset of itself.

If $J$ is an inductive subset of $F$, then

$$\begin{eqnarray*} 1\in J &\mbox{ since }& 0\in J \mbox{ and } 1=0+1 \\ 2\in J &... ...d } 2=1+1 \\ 3\in J &\mbox{ since }& 2\in J \mbox{ and } 3=2+1, \end{eqnarray*}$$

etc. Hence every inductive set contains

$$\{0,1,2,3,4,5,\cdots\}.$$

If $J$ is an inductive subset of $\mbox{{\bf Z}}_5$, then

$$\mbox{{\bf Z}}_5=\{0,1,2,3,4\}\subset J\subset\mbox{{\bf Z}}_5$$

so the only inductive subset of $\mbox{{\bf Z}}_5$ is $\mbox{{\bf Z}}_5$ itself. The set

$$\left\{0,{2\over 2},{4\over 2},{5\over 2},{6\over 2},{7\over 2},{8\over 2},\cdots\right\}$$

is an inductive subset in $\mbox{{\bf Q}}$.

3.3   Exercise. Which of the following subsets of $\mbox{{\bf Q}}$ are inductive?

$$\begin{eqnarray*} A&=&\mbox{ The set of even numbers }=\{2n:n\in\mbox{{\bf Z}}\}... ... \\ D&=&\{x \in \mbox{{\bf Z}}: x\geq -3\} =\{-3,-2,-1,\cdots\} \end{eqnarray*}$$

3.4   Exercise.

a)

Find an inductive subset $J$ of $\mbox{{\bf Q}}$, such that $J\neq\mbox{{\bf Q}}$ and $${{3\over 4}\in J}$$.

b)

Find an inductive subset $K$ of $\mbox{{\bf Q}}$, such that $K\neq\mbox{{\bf Z}}$ and $${{3\over 4}\notin K}$$.

3.5   Definition (Natural numbers in $F$.) Let $F$ be a field, and let $n\in F$. Then $n$ is a natural number in $F$ if $n$ is in every inductive subset of $F$. The set of all natural numbers in $F$ will be denoted by $\mbox{{\bf N}}_F$.

3.6   Example. By the first example in 3.2, for every field $F$

$$0\in\mbox{{\bf N}}_F,1\in\mbox{{\bf N}}_F,2\in\mbox{{\bf N}}_F,3\in\mbox{{\bf N}}_F,\cdots.$$

If $F=\mbox{{\bf Z}}_5$, $\mbox{{\bf N}}_F=\mbox{{\bf Z}}_5$.

3.7   Remark. By the definition of $\mbox{{\bf N}}_F$, $\mbox{{\bf N}}_F$ is a subset of every inductive subset of $F$, i.e.,

$$\mbox{ If } n\in\mbox{{\bf N}}_F,\mbox{ and } J\mbox{ is inductive, then } n\in J.$$

3.8   Theorem. Let $F$ be a field. Then the set $\mbox{{\bf N}}_F$ of natural numbers in $F$ is an inductive set.

Proof: Since $0$ is in every inductive set, $0\in\mbox{{\bf N}}_F$. Let $J$ be an inductive subset of $F$. Then for all $n\in F$,

$$\begin{eqnarray*} n\in\mbox{{\bf N}}_F&\mbox{$\Longrightarrow$}& n\in J \mbox{ (... ...grightarrow$}& n+1\in J \mbox{ (since } J\mbox{ is inductive) }. \end{eqnarray*}$$

Hence

$$\begin{eqnarray*} n\in\mbox{{\bf N}}_F&\mbox{$\Longrightarrow$}& (n+1\in J\mbox{... ...{ of } F) \\ &\mbox{$\Longrightarrow$}& n+1\in\mbox{{\bf N}}_F. \end{eqnarray*}$$

Hence $\mbox{{\bf N}}_F$ is inductive. $\mid\!\mid\!\mid$

3.9   Remark. We summarize the previous theorem and remark by saying ``$\mbox{{\bf N}}_F$ is the smallest inductive subset of $F$." $\mbox{{\bf N}}_F$ is an inductive set, and it's a subset of every other inductive set. You should expect that

$$\mathbf{N_F} = \{0,1,2,3,4,\cdots\}$$

(whatever ``$\cdots$" might mean).

3.10   Theorem (Induction theorem.) Let $F$ be a field, and let $P$ be a proposition form on $\mbox{{\bf N}}_F$. Suppose that

$$P(0) \mbox{ is true }.$$ (3.11)

$$\mbox{For all } n\in\mbox{{\bf N}}_F, \left(P(n)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)\right) \mbox{ is true }.$$ (3.12)

Then $P(n)$ is true for all $n\in\mbox{{\bf N}}_F$.

Proof: Let $P$ be a proposition form on $\mbox{{\bf N}}_F$ satisfying (3.11) and (3.12). Let

$$T=\{n\in\mbox{{\bf N}}_F \colon P(n)\mbox{ is true }\}.$$

I want to show that $T$ is inductive. Well, $0\in T$, by (3.11). Let $n$ be any element in $F$.

Case 1.

$n\in T:$

$$\begin{eqnarray*} % latex2html id marker 9469n\in T &\mbox{$\Longrightarrow$}&... ...ue (by \ref{induct2}) } \\ &\mbox{$\Longrightarrow$}& n+1\in T. \end{eqnarray*}$$

Case 2.

$n\notin T:$

If $n\notin T$, then $n\in T$ is false, so $(n\in T\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}n+1\in T)$ is true.

Thus for all $n\in F$,

$$n\in T\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}n+1\in T.$$

This shows that $T$ is inductive. Since every inductive set contains $\mbox{{\bf N}}_F$, $\mbox{{\bf N}}_F\subset T$; i.e., for all $n\in\mbox{{\bf N}}_F$, $P(n)$ is true. $\mid\!\mid\!\mid$

3.13   Theorem. Let $F$ be a field, and let $a,m$ be natural numbers in $F$. Then $a+m$ and $a\cdot m$ are in $\mbox{{\bf N}}_F$.

Proof: Let $P$ be the proposition form on $\mbox{{\bf N}}_F$ defined by

$$P(n)=``\mbox{for all }a\in\mbox{{\bf N}}_F( a+n\in\mbox{{\bf N}}_F)'' \mbox{ for all } n\in\mbox{{\bf N}}.$$

Then $P(0)$ says `` $\mbox{for all }a \in \mbox{{\bf N}}_F (a+0\in\mbox{{\bf N}}_F)$" which is true. For all $n\in\mbox{{\bf N}}_F$,

$$\begin{eqnarray*} P(n) &\mbox{$\Longrightarrow$}& \mbox{ for all }a \in \mbox{{\... ...(n+1)\in\mbox{{\bf N}}_F) \\ &\mbox{$\Longrightarrow$}& P(n+1). \end{eqnarray*}$$

By the induction theorem, $P(n)$ is true for all $n\in\mbox{{\bf N}}_F$; i.e.,

$$\mbox{ for all }n\in\mbox{{\bf N}}_F (\mbox{ for all }a\in\mbox{{\bf N}}_F(a+n \in \mbox{{\bf N}}_F)).$$

Now define a proposition form $Q$ on $\mbox{{\bf N}}_F$ by

$$Q(n)=``\mbox{for all }a \in\mbox{{\bf N}}_F( a\cdot n\in\mbox{{\bf N}}_F)'' \mbox{ for all } n\in\mbox{{\bf N}}.$$

Then $Q(0)$ says `` $\mbox{for all }a \in\mbox{{\bf N}}_F(a\cdot 0\in\mbox{{\bf N}}_F)$" which is true. For all $n\in\mbox{{\bf N}}_F$,

$$\begin{eqnarray*} Q(n) &\mbox{$\Longrightarrow$}& \mbox{ for all }a\in \mbox{{\b... ...(n+1)\in\mbox{{\bf N}}_F) \\ &\mbox{$\Longrightarrow$}& Q(n+1). \end{eqnarray*}$$

By the induction theorem, $Q(n)$ is true for all $n\in\mbox{{\bf N}}_F$; i.e.,

$$\mbox{ for all }n\in \mbox{{\bf N}}_F(\mbox{for all }a \in \m... ... N}}_F(a\cdot n\in\mbox{{\bf N}}_F)).\mbox{ $\mid\!\mid\!\mid$}$$

3.14   Theorem. Let $F$ be an ordered field. Then for all $n\in\mbox{{\bf N}}_F$, we have

$$n=0 \mbox{ or } n\geq 1.$$

Proof: Define a proposition form $P$ on $\mbox{{\bf N}}_F$ by

$$P(n)=``n=0 \mbox{ or } n\geq 1'' \mbox{ for all } n\in\mbox{{\bf N}}_F.$$

Clearly $P(0)$ is true. let $n\in\mbox{{\bf N}}_F$. To show that $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$, I'll show that $n=0\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$} P(n+1)$ and that $n\geq 1\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$. Well

$$n=0\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}n+1=1\mbox... ...n+1\geq 1\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$$

and

$$n\geq 1\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}n+1\ge... ...+1\geq 1\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1).$$

Hence $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$, and by induction $P(n)$ is true for all $n\in\mbox{{\bf N}}_F$. $\mid\!\mid\!\mid$

3.15   Corollary. Let $F$ be an ordered field. Then there is no element $x\in\mbox{{\bf N}}_F$ such that

$$0<x<1.$$

3.16   Lemma. Let $F$ be an ordered field. Then

$$\mbox{ for all } n\in\mbox{{\bf N}}_F, (n-1\in\mbox{{\bf N}}_F \mbox{ or } n=0)$$ (3.17)

Proof: Define a proposition form $P$ on $\mbox{{\bf N}}_F$ by

$$P(n) = ``(n-1\in\mbox{{\bf N}}_F) \mbox{ or }(n=0) ''\mbox{ for all }n \in \mbox{{\bf N}}_F.$$ (3.18)

Then $P(0)$ is true. Let $n\in\mbox{{\bf N}}_F$. To show that $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$, I'll show that $(n-1 \in \mbox{{\bf N}}_F) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$ and that ( $n=0) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$. Well,

$$\Big( n-1 \in \mbox{{\bf N}}_F \Big) \mbox{$\hspace{1ex}\Long... ...F \Big) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1),$$

and

$$(n=0) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}\Big( (... ..._F\Big) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1).$$

Hence $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$, and by induction, $P(n)$ is true for all $n\in\mbox{{\bf N}}_F$. $\mid\!\mid\!\mid$

3.19   Theorem. Let $F$ be an ordered field and let $p,k\in\mbox{{\bf N}}_F$. Then

$$p-k\in\mbox{{\bf N}}_F \mbox{ or } p-k<0.$$

Proof: For each $p \in\mbox{{\bf N}}_F$ define a proposition form $P_p$ on $\mbox{{\bf N}}_F$ by

$$``p-n\in\mbox{{\bf N}}_F \mbox{ or } p-n<0'' \mbox{ for all } n\in\mbox{{\bf N}}_F.$$

I'll show that for each $p \in\mbox{{\bf N}}_F$, $P_p(n)$ is true for all $n\in\mbox{{\bf N}}_F$. Now $P_p(0)$ says ``$p \in\mbox{{\bf N}}_F$ or $p<0$" which is true, since $p \in\mbox{{\bf N}}_F$. Now let $n\in\mbox{{\bf N}}_F$. To show that $P_p(n)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P_p(n+1)$, I'll show that

$$p-n\in\mbox{{\bf N}}_F\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P_p(n+1)$$

and that

$$p-n<0\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P_p(n+1).$$

By the previous lemma

$$\begin{eqnarray*} p-n\in\mbox{{\bf N}}_F&\mbox{$\Longrightarrow$}& (p-n)-1\in\mb... ...F \mbox{ or } p-(n+1)<0 \\ &\mbox{$\Longrightarrow$}& P_p(n+1). \end{eqnarray*}$$

Also

$$\begin{eqnarray*} p-n<0 &\mbox{$\Longrightarrow$}& (p-n)-1<-1\mbox{$\hspace{1ex}... ...rightarrow$}& p-(n+1)<0 \\ &\mbox{$\Longrightarrow$}& P_p(n+1). \end{eqnarray*}$$

This completes the proof that $P_p(n)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P_p(n+1)$, so by induction $P_p(n)$ is true for all $n\in\mbox{{\bf N}}_F$. $\mid\!\mid\!\mid$

3.20   Corollary. Let $F$ be an ordered field, and let $p,k\in\mbox{{\bf N}}_F$. If $p\geq k$, then $p-k \in \mbox{{\bf N}}_F$.

3.21   Theorem. Let $F$ be an ordered field and let $p \in\mbox{{\bf N}}_F$. Then there is no natural number $k$ such that $p<k<p+1$. In other words,

$$\mbox{ for all }k,p \in \mbox{{\bf N}}_F ( k > p \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}k \geq p+1).$$

Proof: Suppose

$$p<k<p+1.$$ (3.22)

Then

$$0<k-p<1.$$

Since $k-p>0$, the previous theorem says $k-p\in\mbox{{\bf N}}_F$. This contradicts corollary 3.15, so (3.22) is false. $\mid\!\mid\!\mid$

3.23   Theorem (Least Element Principle.) Let $F$ be an ordered field. Then every non-empty subset $S$ of $\mbox{{\bf N}}_F$ contains a least element, i.e. if $S \neq \emptyset$, then there is some element $k \in S$ such that $k \leq n$ for all $n \in S$.

Proof: I will show that if $S$ is a subset of $\mbox{{\bf N}}_F$ having no least element, then $S = \emptyset$.

Let $S$ be a subset of $\mbox{{\bf N}}_F$ having no least element. For each $n\in\mbox{{\bf N}}_F$ define a proposition $P(n)$ by

$$P(n) = \mbox{``For all $k \in S, (k > n)$''}.$$

Now $0 \notin S$, since if $0$ were in $S$ it would be a least element for $S$. Hence all elements in $S$ are greater than $0$, and $P(0)$ is true. Now let $n$ be a generic element of $\mbox{{\bf N}}_F$. Then

$$\begin{eqnarray*} P(n) & \mbox{$\Longrightarrow$}& \mbox{ for all }k \in S, (k >... ...Longrightarrow\hspace{1ex}$}& \mbox{ for all }k \in S, (k > n+1) \end{eqnarray*}$$

since if $n+1$ were in $S$, it would be a least element for $S$. Thus

$$P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1),$$

and by induction, $P(n)$ is true for all $n\in\mbox{{\bf N}}_F$. It follows that $S = \emptyset$, since if $S$ contained an element $n$, then $P(n)$ would say that $n>n$. $\mid\!\mid\!\mid$

3.24   Exercise. A Let $F$ be an ordered field. Show that there is a non-empty subset $S$ of $F^+$ that has no smallest element, i.e. there is a set $S \subset F^+$ such that

$$\mbox{for every }a \in S \mbox{ there is some } b \in S \mbox{ with } b < a.$$

3.25   Example. Let $F$ be an ordered field. Let $P$ be the proposition form on $\mbox{{\bf N}}_F$ defined by

$$P(n)=``n^2>{1\over 2}(n^2+n).''$$ (3.26)

Then for all $n\in\mbox{{\bf N}}_F$

$$\begin{eqnarray*} P(n)&\mbox{$\Longrightarrow$}& n^2>{1\over 2}(n^2+n) \\ &\mbo... ...left((n+1)^2+(n+1)\right) \\ &\mbox{$\Longrightarrow$}& P(n+1). \end{eqnarray*}$$

Hence $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$ for all $n\in\mbox{{\bf N}}_F$. Now note:

$$\begin{eqnarray*} &&P(0)\mbox{ says } (0>0)\mbox{ so } P(0)\mbox{ is false! }\\ ... ... }\\ &&P(2)\mbox{ says } (4>3)\mbox{ so } P(2)\mbox{ is true. } \end{eqnarray*}$$

Since $P(0)$ is false, I cannot apply the induction theorem. Notice that when I prove $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$ I do not assume that $P(n)$ is true. (Although I might as well, since I know $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$ is true if $P(n)$ is false.)

3.27   Theorem (Induction theorem generalization.) Let $F$ be an ordered field. Let $k\in\mbox{{\bf N}}_F$ and let $P$ be a proposition form defined on
$\{n\in\mbox{{\bf N}}_F \colon n\geq k\}$. Suppose

$$P(k)\mbox{ is true. }$$ (3.28)

$$\mbox{For all } n\in\{n\in\mbox{{\bf N}}_F \colon n\geq k\}\qquad P(n)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1).$$ (3.29)

Then $P(n)$ is true for all $n\in\{n\in\mbox{{\bf N}}_F \colon n\geq k\}$.

Proof: Let $Q$ be the proposition form on $\mbox{{\bf N}}_F$ defined by

$$Q(n)=P(n+k)\mbox{ for all } n\in\mbox{{\bf N}}_F$$

(observe that $n\in\mbox{{\bf N}}_F\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}n+k\in\{n\in\mbox{{\bf N}}_F\colon n\geq k\}$ so $Q(n)$ is defined). Then $Q(0)=P(k)$, so $Q(0)$ is true by (3.28). For all $n\in\mbox{{\bf N}}_F$,

$$\begin{eqnarray*} Q(n)&\mbox{$\Longleftrightarrow$}& P(n+k)\mbox{$\hspace{1ex}\L... ...((n+1)+k\right)\hspace{1ex}\Longleftrightarrow\hspace{1ex}Q(n+1) \end{eqnarray*}$$

so

$$Q(n)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q(n+1).$$

By the induction theorem, $Q(n)$ is true for all $n\in\mbox{{\bf N}}_F$; i.e., $P(n+k)$ is true for all $n\in\mbox{{\bf N}}_F$. To complete the proof, I need to show that

$$\{n+k\colon n\in\mbox{{\bf N}}_F\}=\{n\in\mbox{{\bf N}}_F\colon n\geq k\}.$$

It is clear that

$$\{n+k\colon n\in\mbox{{\bf N}}_F\}\subset \{n\in\mbox{{\bf N}}_F\colon n\geq k\}.$$

To show the opposite inclusion, observe that if $n\in\mbox{{\bf N}}_F$ and $n\geq k$, then $n=(n-k)+k$, and by theorem 3.19, $n-k\in\mbox{{\bf N}}_F$. $\mid\!\mid\!\mid$

3.30   Example. Let $F$ be an ordered field, and let $P$ be the proposition form on $\mbox{{\bf N}}_F$ defined by

$$P(n)=``n^2>{1\over 2}(n^2+n).''$$

In example 3.25, we showed that $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$ for all $n\in\mbox{{\bf N}}_F$ and that $P(2)$ is true. Hence, by our generalized induction theorem we can conclude that $P(n)$ is true for all $n\in\mbox{{\bf N}}_F$ with $n\geq 2$.

3.31   Exercise. Let $F$ be a field and let $x\in\mbox{{\bf N}}_F$. We say $x$ is even if $x=2\cdot y$ for some $y\in\mbox{{\bf N}}_F$, and we say $x$ is odd if $x=2\cdot z+1$ for some $z\in\mbox{{\bf N}}_F$.

a)

What are the even numbers in $\mbox{{\bf Z}}_5$?

b)

What are the odd numbers in $\mbox{{\bf Z}}_5$?

3.32   Exercise. A

a)

Let $F$ be a field. Prove that every element in $\mbox{{\bf N}}_F$ is either even or odd. HINT: Let $P(n)=``n$ is even or $n$ is odd".

b)

Let $F$ be an ordered field. Prove that no element of $\mbox{{\bf N}}_F$ is both even and odd. Why doesn't this contradict the result of exercise 3.31?

3.33   Note. The question of whether to consider $0$ to be a natural number is not settled. Some authors start the natural numbers at $0$, other authors start them at $1$. It is interesting to note that Aristotle did not consider $1$ to be a number.

$\dots$ for ``one" signifies a measure of some plurality, and `` a number" signifies a measured plurality or a plurality of measures. Therefore, it is also with good reason that unity is not a number; for neither is a measure measures, but a measure is a principle, and so is unity $\dots$. [5, page 237, N, 1, 1088a5]

Zero was first recognized to be a number around the ninth century. According to [31, page 185] Mahavira (ninth century) noted that any number multiplied by zero produces zero, and any number divided by zero remains unchanged! Bhaskara (1114-1185) said that a number divided by $0$ is called an infinite quantity.

Although arguments that are essentially arguments by induction appear in Euclid, the first clear statement of the induction principle is usually credited to Blaise Pascal. (1623-1662) who used induction to prove properties of Pascal's Triangle.[36, page 73]

I believe that the idea of defining the natural numbers to be things that are in every inductive set should be credited to Giuseppe Peano [37, page 94, Axiom 9]. In. 1889, Peano gave a set of axioms for natural numbers $\mbox{{\bf N}}$ (starting with $1$), one of which can be paraphrased as: If $K$ is any set, such that $1\in K$ and for all $x\in\mbox{{\bf N}}$, $(x\in K\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}x+1\in K)$, then $\mbox{{\bf N}}\subset K$.