Natural Numbers. Induction

1.5 Natural Numbers. Induction

A precise approach of defining natural numbers is as follows:

Definition 1.5.1 (Natural Numbers).

A Subset $S$ of a field $F$ is called inductive iff:

(i): $1\in S$ ($S$ contains the unity element of $F$) and,
(ii): $(\forall x \in S)\;\; x+1\in S$

Define $N$ to be the intersection of all such subsets. We then obtain the following.

Theorem 2. The Set $N$ so defined is inductive itself. In fact, it is the “smallest” inductive set in $F$ (i.e. contained in any other such set).

Proof. We have to show that, with our new definition,

(i): $1 \in N$ and
(ii): $(\forall x \in N)\;\; x+1 \in N.$

Now, by definition, the unity $1$, is in each inductive set; Hence belongs to the intersection of such sets, i.e., to $N$. Thus, $1 \in N$, as claimed.
Next, we take any $x \in N$. Then, by our definition of $N$, $x$ is in every inductive set $S$. Hence, by the property (ii) of such sets, also $x+1$ is in every such set $S$; thus, $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, hence contained in each. □

For applications, this is usually expressed as:

Theorem 3 (First Inductive Law). A proposition $P(n)$ involving a natural $n$ holds for all $n \in N$ in a field $F$ if:

(i): It holds for $n=1\;\; [P(1)\; \text {is true } ]$; and
(ii): whenever $P(n)$ holds for $n=m$, it holds for $n=m+1$; $[P(m) \implies P(m+1)].$

Proof. Let $S$ be the set of all those $n \in N$ for which $P(n)$ is true; that is, $S =\{n \in N \;|\; P(n) \} $. We must show that actually each $n \in N$ is in $S$, i.e., $N \subseteq S$.
First, we show that $S$ is inductive. By our assumption (i), $P(1)$ is true. So, $1 \in S$.
Next, suppose $x \in S$. This means that $P(x)$ is true, but by assumption (ii), this implies $P(x+1)$, i.e., $x+1 \in S$. Thus, $1 \in S$ and $(\forall x \in S)\;\;x+1 \in S$; so, $S$ is inductive. By the new definition of Natural numbers, $N \subseteq S$. □

This theorem is widely used to prove general propositions on natural elements, as follows. In order to show that some formula or proposition $P(n)$ is true for every natural number $n$, we first verify $P(1)$, i.e., show that $P(n)$ holds for $n=1$. We then show that \begin {align*} (\forall m \in N)\;\;P(m) \implies P(m+1); \end {align*}

that is, if $P(n)$ holds for some $n=m$, then it also holds for $n=m+1$. Once, these two facts are established, The first inductive law ensures, that $P(n)$ holds for all natural $n$.

Examples

(A)

If $n$ and $m$ are natural numbers, so are $n+m$ and $nm$. To prove it, fix any $m \in \N $. Let $P(n)$ mean that $m+n \in \N $, we now verify the following:

(i): $P(1)$ is true; for $m \in \N $ is given. Hence, by the very definition of $\N $, $m+1 \in \N $. But this means exactly that $P(n)$ holds for $n=1$. i.e., $P(1)$ is true.
(ii): $P(k) \implies P(k+1)$. Suppose that $P(n)$ holds for some particular $n=k$. This means that $m+k \in \N $. Hence, by the definition of $\N $, $(m+k)+1 \in \N $; or, by associativity, $m+(k+1) \in \N $. But, this means exactly that $P(k+1)$ is true if $P(k)$ is true. Hence induction is complete, and this means that $n+m \in \N $.

For multiplication, similarly, fix $m \in \N $, and let $P(n)$ mean that $mn \in \N $.

(i): $P(1)$ is true; for $m \in \N $ is given, by Axiom IV, we have $m =m\cdot 1 \in \N $. Hence $P(1)$ is true.
(ii): $P(k) \implies P(k+1)$; Suppose that $P(n)$ holds for some $n=k$. This means that $mk \in \N $. for $n=k+1$, we have $mn=m\cdot (k+1)$, by the distributive property, we have $mn=mk+m$, by earlier, $mk \in \N $ and $m \in \N $, hence, $mk+m \in \N $. Thus, by induction, $mn \in N$.

(B)

If $n \in \N $, then $n-1=0$ or $n-1 \in \N $. Indeed let $P(n)$ mean that $n-1 =0$ or $n-1 \in \N $. We again verify the two steps:

(i)

$P(1)$ is true; for if $n=1$, then $n-1=1-1=0$, thus one of the desired alternatives, namely $n-1=0$ holds if $n=1$. Hence, $P(1)$ is true.

(ii)

$P(m) \implies P(m+1)$. Suppose $P(n)$ holds for some particular value $n=m$ (inductive hypothesis). This means that either $m-1=0$ or $m-1 \in \N $.

In the first case, we have $(m-1)+1 =0 +1 =1 \in \N $. But $(m-1)+1 = m +((-1)+1)= m+ (1+(-1))=(m+1)-1$, by associativity and commutativity. Thus, $(m+1) -1 \in \N $.

In the second case, $m-1 \in \N $, implies $(m-1)+1 \in \N $ by the definition of $\N $. Thus, in both cases, $(m+1)-1 \in \N $, and this shows that $P(m+1)$ is true if $P(m)$ is true.

(C)

In an ordered field, all naturals are $\geq 1$. Indeed, let $P(n)$, now mean that $n\geq 1$. As before, we again carry out the two inductive steps.

(i): $P(1)$ holds; for if $n=1$, then certainly $n\geq 1$; so $P(n)$ holds for $n=1$.
(ii): $P(m) \implies P(m+1)$. We make the inductive hypothesis that $P(m)$ holds for some particular $m$. This means that $m\geq 1$. Hence, by monotonicity of addition and transitivity (Axioms IX and Axiom VIII), we have $m+1\geq 1+1 >1$ (the latter follows by adding 1 on both sides of $1>0$). Thus $m+1\geq 1$, thus $P(m+1)$ holds if $P(m)$ holds. Induction is complete.

(D)

In an ordered field, $m, n \in \N $ and $m>n$ implies $m-n \in \N $. This is an extremely tricky problem to solve by induction because if we fix $m$ to be some particular value $\in \N $, then doing induction on $n$, eventually $n$ will be greater than $m$, hence $P(n)$ won’t hold for $n \geq m$. Instead, we have to carefully define the proposition while fixing an arbitrary $m \in \N $, let $P(n)$ mean “$m \leq n$ or $m-n \in \N $”. Then, we have the following:

(i)

$P(1)$ is true; for if $n=1$, then $m-n =m -1$, but by Example (B), $m-1=0$ or $m-1 \in \N $. This shows $P(n)$ holds for $n=1$.

(ii)

$P(k)\implies P(k+1);$ Suppose $P(k)$ holds for some particular $k\in \N $. This means that: \begin {align*} m \leq k \;\;\text {or}\;\; m-k \in \N . \end {align*}

For the first case, clearly, if $m\leq k$, because $k<k+1$, by the transitive property of an ordered field, we have $m\leq k+1$. For the second case, if $m-k\in \N $, by Example (B), we have either: \begin {align*} (m-k) -1=0\;\;\text {or}\;\; (m-k) -1 \in \N \end {align*}

In the first, case, $m-k =1$, hence $m\leq k+1$. For the latter case, using associativity and commutativity, we have $m - (k+1) \in \N $. Thus, $P(k) \implies P(k+1)$, and by induction we have : If, $n,m \in \N $ and $m>n$, then $m-n \in \N $.

Lemma 1. For no naturals $m,n$ in an ordered field is $m<n<m+1$. i.e., there is no natural between any arbitrary natural and its successor.

Proof. For, by Example (D), $n>m$, would imply that $n-m \in \N $. By Example (C), we have $n-m\geq 1$, or $n\geq m+1$. Then by the trichotomy of order, we exclude $n< m+1$. Thus, $m<n<m+1$ is impossible for natural numbers. □

Theorem 4 (Well Orderedness). In an ordered field, every nonempty subset of $\N $ (the naturals) has a least element, i.e., one not exceeding any other of its members.

Proof. Given some $A$ such that $\varnothing \neq A \subseteq \N $, we want to show that $A$ has a least element. To do this, let: \begin {align*} A_n = \{x\in A\;|\; x \leq a\}\;\; n=1,2, ... \end {align*}

That is, $A_n$ consists of those elements of $A$ that are $\leq n$ ($A_n$ might be empty). Now let $P(n)$ mean \begin {align*} \textit {``either $A_n = \varnothing $ or $A_n$ has a least element''} \end {align*}

We will show by induction that $P(n)$ holds for each $n \in \N $. We have the following:

(i): $P(1)$ is true; for, by construction, $A_1$ consists of all naturals from $A$ that are $\leq 1$ (if any). But, by Example (C), the only such natural is $1$. Thus, $A_1$, if not empty, consists of 1 alone, and so 1 is also its least member. We see that either $A_1 = \varnothing $ or $A_1$ has a least element; i.e., $P(1)$ is true.
(ii): $P(m) \implies P(m+1)$. Suppose $P(m)$ holds for some particular $m$. This means that $A_m = \varnothing $ or $A_m$ has a least element (call it $m_0$). In the latter case, $m_0$ is also the least element of $A_{m+1}$; for, by the lemma, $A_{m+1}$ differs from $A_n$ by $m+1$ at most, which is greater than all members of $A_m$.

If, however, $A_m = \varnothing $, then for the same reason, $A_{m+1}$ (if $\neq \varnothing $) consists of $m+1$ alone; so $m+1$ is also the least element.

This shows that $P(m+1)$ is true if $P(m)$ is. Thus, the proposition holds for every $A_n$.

Now, by assumption, $A \neq \varnothing $; so we fix some $n \in A$. Then the set \begin {align*} A_n = \{ \ x \in A\;\; |\;\; x \leq n\ \} \end {align*}

contains $n$ and hence $A_n \neq \varnothing $. Thus, by the proposition, $A_n$ must have a least element $m_0$, $m_0 \leq n$. But $A$ differs from $A_n$ only by elements $> n$ (if any), which are all $> m_0$. Thus $m_0$ is the desired least element of $A$ as well. □

This theorem yields a new form of induction law for ordered fields: The Second Induction Law

Theorem 5 (Second Induction Law). A Proposition $P(n)$ holds for each natural number $n$ in an ordered field if

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

Proof. We shall use a so-called indirect proof or proof by contradiction. That is, instead of proving our assertion directly, we shall show that the opposite is false, and so, our theorem must be true.
Thus assume (i) and (ii) and seeking a contradiction, suppose $P(n)$ fails for some $n \in \N $ (call such $n$ as “bad”). Then these bad naturals from a non-empty subset of $\N $, call it $A$. By the well ordered property of $\N $, $A$ has a least member $m$. Thus, $m$ is the least natural for which $P(n)$ fails. If also follows that all $n$ less than $m$ do satisfy $P(n)$ (among them is 1 by (i)). But then, by our assumption (ii), $P(n)$ also holds for $n=m$, which is impossible since, m is bad by construction.
This construction shows that there cannot be any “bad” naturals. □

A similar induction law applies to definitions. It reads as follows:

Definition 1.5.2 (Recursive Definitions). A notion $C(n)$ is regarded as defined for every natural element of an ordered field $F$ if

(i): it has been defined for $n=1$, and
(ii): some rule or formula is given that expresses $C(n)$ in terms of $C(1),\ C(2),\ ...,\ C(n-1)$, i.e., in terms of all $C(k)$ with $k<n$, or some of them.

Such definitions are referred to as inductive or recursive. The admissibility can be proved rigorously ¹ .
We shall now illustrate this procedure by several important examples of inductive definitions to be used throughout our later work.

Definition 1.5.3 (Natural number Power). Given an element $x$ of a field $F$, we define the $n$-th power of $x$, denoted

(i) $x^1 =x$ and (ii) $x^n = x^{n-1}x$, $n =2,3, ...$.

By the inductive law expressed above $x^n$ is defined for every natural $n$. If $x \neq 0$, we also define $x^0=1$ and $x^{-n} =\frac {1}{x^n}$

Definition 1.5.4 (Factorial). For every natural number $n$, we define recursively the expression $n!$ as follows:

(i) $1! =1$; (ii) $n! = (n-1)! \cdot n, \;\; n=2,3,... $

We also define $0!=1$

Definition 1.5.5 (Sums and Products of $n$ elements). The sum and product of $n$ elements $x_1,\ \ldots ,\ x_n \in F$ of a field, denoted by \begin {align*} x_1+ x_2+ \cdots + x_n\;\; \text {and}\;\; x_1\cdot x_2 \cdots x_n \end {align*}

(or $\sum _{k=1}^{n} x_k$ and $\prod _{k=1}^nx_k$), respectively, are defined recursively as follows:

Sums: (i) $\sum _{k=1}^1 x_k = x_1$; (ii) $\sum _{k=1}^n x_k = \left (\sum _{k=1}^{n-1} x_k\right ) +x_n$, $n=2,3,\ldots $
Products: (i) $\prod _{k=1}^1 x_k = x_1$; (ii) $\prod _{k=1}^n x_k = \left (\prod _{k=1}^{n-1} x_k\right ) +x_n$, $n=2,3,\ldots $

Induction can be used to define the notion of an ordered n-tuple if the concept of an ordered pair is assumed to be known.

Definition 1.5.6 ($n$-tuple). For any objects $x_1,x_2, \ldots , x_n$, the ordered $n$-tuple $(x_1, \ldots , x_n)$ is defined by

(i): $(x_1) = x_1$ (i.e., an ordered “one-tuple” $(x_1)$ is $x_1$ itself);
(ii): $(x_1, \ldots , x_n) = ((x_1, \ldots , x_{n-1}), x_n) $ $n =2,3,\ldots $ .

Accordingly, we may now also define the Cartesian Product \begin {align*} A_1 \times A_2 \times \cdots \times A_n \end {align*}

of $n$ sets either as the set of all $n$-tuples $(x_1, \ldots , x_n)$ such that $x_k \in A_k$ $k=1,2, \ldots , n$, or directly by induction.

[next] [prev] [prev-tail] [front] [up]