2.2: Natural Numbers. Induction
- Page ID
- 19029
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\).
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.
(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."
(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\).
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.
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.
(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.}\]