Natural numbers and mathematical induction

Page 1

Natural numbers and mathematical induction

Calculus takes its origin in the properties of natural numbers,

The formal definition of natural numbers

is based on

Peano axioms.

A set A of elements is called natural numbers if it possesses the following properties.

i.

Every element

has an element that is called successor and denoted by

ii.

Elements

and

have different successors,

iii.There is an element in A that is not a successor of any element from A. This special element is denoted by "0"

iv.

If a logical statement

is trues for

and

implies that

then

Notice that the last Piano axiom justifies the widely known principle of

Mathematical Induction.

i. (Basis) The statementis true for

ii. (Inductive step) If (induction hypothesis )

then

If it is possible for a statement

to prove items (i.) and (ii.) then

for any

Let us illustrate the principle of mathematical induction by the following example.

Example .Our goal is to use mathematical induction in order to prove that

The statement

is

We need to show that

In order to conduct our proof by means of mathematical induction we need to show first that

for

Basis. One can see that

means

and it is a valid statement. That means we have shown that

Inductive step. Suppose (induction hypothesis ) that

which means

(1)

is valid.

Our goal is to show that

as well. That means we need to prove that

is true.

After adding

to the left and right hand sides of (1) we obtain

(2)

Since

the statement (1) implies (2) and in accordance with mathematical induction we have proved that

is valid for all

Definition 1

(Prime number) A natural number

is called prime if it is devisable without remainder only by

and itself, p.

Prime numbers occupy a special prominent place among all natural numbers. Any natural number can be build in certain unique way out of prime numbers. In more precise terms, the following theorem holds.

Theorem 1.1 For any natural number

such that

there exist a finite set of prime numbers

such that

(3)

where

are integers. Moreover, the representation (3) is unique.