One of the most important mathematical theories is the arithmetic of natural numbers. As you probably noticed, for the purpose of this lecture, we assume that natural numbers are 0, 1, 2, 3, etc., and their set is denoted by N. Elementary natural numbers arithmetic uses a simple language in which, aside from the constant 0, there also occurs the one-argument function suc (called successor's function) as well as the equality relation. Axioms for this theory were formulated by Peano. Peano arithmetic consists of all statements derived from these axioms.

Ax1. Zero is a natural number.

Ax2. For every natural number n there exists exactly one natural number suc(n) which is a successor of n.

Ax3. Zero is not a successor of any natural number.

Ax4. If k is a successor of n, k = suc(n), and k is a successor of m, k = suc(m), then n = m.

Ax5. Mathematical induction principle: If A is a subset of the set of natural numbers  N such that conditions (1), (2)  hold:

then A = N.

The first axiom claims that 0 ∈ N. The second axiom defines one-argument function suc (called successor's function), which domain is the set of natural numbers. The fourth axiom assures that suc is a one-to-one function i.e. different natural numbers are assigned to different successors. The third axiom excludes 0 from the set of all possible values of the successsor (0 does not belong to the range of suc). Finally, the fifth axiom shows a method of constructing the set of natural numbers, using just a start symbol 0 and successively iterating on it the successor function. Thus, every natural number n can be obtained with 0 and n-time iteration of function suc,

1=^df suc(0), 2 = ^df suc(suc(0)), 3 = ^df suc(suc(suc(0))), etc.

This fact is commonly but unconsciously used in proving that  the "while" program {x:= 0; while x < y do x := x+1 od } does not operate infinitely long for every natural number y.

In order to present how to use induction principle in proofs of mathematical theorems, we consider the following example (more cases are studied in the next subsection)

Example 8.1.1

Every natural number of type n⁵- n for n ∈ N is divisible by 5.

Proof.

Let A = {n ∈ N: (n⁵ - n) mod 5 = 0}. We show that A = N.

1. 0 ∈ A, because of 0⁵ - 0 = 0.
2. Let's take an arbitrary natural number n which belongs to set A. Then we know that for some natural number k, n⁵ - n = 5k. According to the transformation below, the number (n+1)⁵ - (n+1) is also divisible by 5:

(n+1)⁵-(n+1) = n⁵+5n⁴+10n³ +10n²+5n +1- n -1 = n⁵ - n + 5(n⁴ +2n³ +2n² +n) = 5(k+n⁴ +2n³ +2n² +n) .

Thus  n+1 ∈ A.

Because both assumptions of the principle of induction hold, thus we may conclude that A = N. It means that for any natural number n,   (n⁵ - n) mod 5 is equal to 0. ♦

Question 8.1.1  What is the last digit in the decimal extension of the number 37 ⁵⁰⁰ - 37 ¹⁰⁰ ?

« previous section

next section »