The mathematical induction immediately leads us to the following theorem called the "minimum principle".

Proof.

Let A ≠ ∅, A ⊆ N and assume that A does not contain the smallest number (i.e. A does not include the first element). In particular it means that 0 ∉ A. Let  B be a set of natural numbers, such that number n belongs to B if and only if n and all numbers less than n do not belong to A. Formally speaking, B = {n : ( ∀ m ≤ n) m ∉ A}. We want to prove that, according to all established assumptions, B = N. Our proof is based on induction over n.

(1) Because 0 does not belong to A, it follows from the definition of set B that  0 ∈ B.

(2) For an arbitrary n, if  n ∈ B, then  n+1 belongs to the set B too.

Proof (2)

From the induction's assumption it follows that n as well as all numbers smaller than n do not belong to A. If (n+1) ∈ A, then (n+1) is the smallest number in the set A. Hence, we obtain a contradiction to our assumption about set A. Therefore, (n+1) ∉ A and in consequence (n+1) ∈ B. Because both (1) and (2) hold, then, according to the induction principle, all natural numbers belong to the set B.

Thus, we prove that N is equal to B and from this result we may conclude emptiness of the set A, in contrary to the previous assumption (i.e. A ≠ ∅). This contradiction proves that in every non-empty set of natural numbers there is the smallest element. As every set of natural numbers is linearly ordered, it follows that every non-empty subset of N has the first element. ♦

Example 8.2.1

We prove that {n ∈ N : 3|(n³-n)} = N. In the presented apagogic proof we will apply the minimum principle. Let A= {n ∈ N : 3|(n³-n)}. We assume that A ≠ N. Then, according to the minimum principle, there is the smallest element in the difference N\A. Because 3|0, thus 0 ∈ A, and 0 is not the smallest number in the set N\A. Let's assume that number k, k>0, is the smallest number in N\A. Hence  (k³-k) is not divisible by 3. Now consider a number (k-1). As k>0, k-1 ∈ N, and moreover we have

(k-1) ³ - (k-1) = k³-3k² + 3k -1 -k +1 = (k³-k) -3k(k-1) .

Because (k³-k) is not 3-divisible and 3k(k-1) is an arbitrary multiple of 3 therefore, the number (k-1) ³ -(k-1) is not divisible by 3. It follows that (k-1) ∈ N\A. This is a contradiction (since, by assumption, k is the smallest number in the set N\A). As a conclusion we obtain A = N. ♦

Question 8.2.1 Does for any natural number n>1, nⁿ > n!  hold?

« previous section

next section »