Peano axioms

The arithmetic of the integers, like the geometry of the plane, can be made to dependent on a few axioms. As early as 1891 G. Peano showed that all the properties of natural numbers can be derived from five axioms, which now bear his name.

We take the natural numbers to be elements of any set ℕ, defined by the triple (ℕ, σ, 0) where ℕ is a set, σ an application from ℕ to ℕ and 0 an element of ℕ with the following properties known as Peano axioms or postulates:

• ℙ₁: σ is injective: Every number n has precisely one successor n'.

• ℙ₂: 0 ≠ Im σ

• ℙ₃: (Induction axiom): every subset U of ℕ such that

  1. 0 ∈ U

  2. k ∈ U ⇒ σ(k) ∈ U   ∀k

coincides with ℕ.

Given an element n ∈ ℕ, the element σ(n) is said successor of n. We thus have naturally defined in ℕ an order relation, ≤. The axiom ℙ₃ is known

principle of mathematical induction. We can prove that if (𝔸, σ,0) and (𝔸',σ',0') are two triples verifying Peano's axioms, then they are "substantially identical", that is there is a bijections φ between 𝔸 and 𝔸' such that σ'(φ(n)) = φ(σ(n)), i.e the successor of the image is the image of the successor. Thus we can say that Peano axioms characterize the natural numbers. What we have to postulate (accept without proof) is the existence of a set ℕ which verifies Peano's axioms. Thus the foundation of the mathematical apparatus is based on the existence of natural numbers. In the words of Knonecker:

Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk. (Kronecker)

From Peano's axioms is possible to deduce all well-known properties of natural numbers. We give first some preliminary definitions.

The Cartesian product of two sets or a finite collection of sets is of considerable importance through set theory. Here below, we introduce a few concepts arising from the Cartesian product that are essential for the rest of this book.

Definition 1.5.1. A binary operation on a set A is a function that maps each ordered pair in A x A to a unique element of a set containing A, that is a map f : A x A ⟶ B ⊂ A

The concept of a binary operation models a process by which any two objects in a set may be combined to produce a specific other element in the set. This concept is ubiquitous in mathematics. Some standard examples include +, −, and × on ℤ or ℝ.
The ordinary addition of integers is a binary operation definined as:

The result of the addition operation, that is the element a + b ∈ ℤ, is called sum of a and b.

Note that the division process ÷ is not a binary operator on ℝ because for example 3 ÷ 0 is not well-defined, while it is a binary operator on ℝ − {0}. Also ÷ is not a binary operator on ℤ − {0} because for example, 3 ÷ 2 is a rational number but not again an element of ℤ − {0}. As yet another nonexample, consider the dot product · of two vectors in ℝ³. This is not a binary operation because it is a function ℝ³ × ℝ³ → ℝ and the codomain is not again ℝ³.

Another example, is the union of subsets of a set X is a binary operation defined in 𝓟(X):

We talk of n-ary operations with n = 1,2,.... which are functions from S x S x ... x S into S. For n = 1 a 1-ary (unitary) operation defined on S is a function from S to S. If S = P(X), an example of 1-ary operation is the functions that associates to each subset of X its complement.

Definition 1.5.2. An algebraic structure is a set endowed with one or multiple n-ary operation satisfying given axioms.

From Peano's axioms all the well known properties of natural numbers can be derived. In particular the sum and product and their properties can be deduced by Peano's axioms.

Definition 1.5.3. The sum of two natural numbers n and m is defined as the natural number n + m where

from this definition it results naturally σ(n) = n + 1, where 1 = σ(0).

Definition 1.5.4. The product of two natural numbers n and m is defined as the natural number n ⋅ m where

Generally we are interested in binary operations, which we shall simply call operations without specifying they are binary.

The principle of mathematical induction

The third Peano axiom ℙ₃ is the assertion on which the principle of mathematical induction is based. It basically says that every subset U of ℕ which contains 0 and contains the successor of each of its elements contains all the natural numbers.
If we accept this axiom (We do not prove that mathematical induction is valid, but instead choose to accept the principles because is rooted in our intuitive understanding of the integers) we obtain a method for proving that a proposition P(n) concerning natural numbers n is valid for all natural numbers. Let's see its application. Suppose that for every integer n ≥ 0 we can formula a proposition P(n), which depends on n, for example: "If a finite set S has n elements, then l'the power set of S has 2ⁿ elements". Suppose we want to prove that the proposition P(n) is true for every n: we should prove infinite propositions! With the mathematical induction we can prove a proposition sin just two steps. We proceed as follows:

1. Basis step: prove that P(0) is true;

2. Induction step: Prove that for every k, from P(k) being true, follows that P(k + 1) is true, that is P(k) ⇒ P(k+1).

Then we can conclude to have proved that P(n) is true for every n. Indeed by letting U = {n ∈ ℕ | P(n) is true}, it results 0 ∈ U because it has been proved that P(0) is true. Further, k ∈ U, that is if P(k) is true, then P(k+1) is true, (inductive step) and thus k + 1 ∈ U, from which follows, by ℙ₃, U = ℕ, that is P(n) is true for every n.

Notice that if we want to prove a proposition P(n) not for all n, but only for those n ≥ n₀, it suffices to prove as basis step the proposition P(n₀) instead of P(0).

Prove that for any positive integer n the sum of the cubes of the first n even numbers is given by

Proof. We must prove:

1. Base of the induction: P(1) is true for n = 1 both members reduce to 2³.

2. Induction step: Supposing true P(n − 1), we prove P(n). The P(n − 1) (which we are supposing true) is:

   2³ + 4³ + 6³ + ... + (2n − 1)³ = 2n(n−1)²n²

   Adding (2n)³ to both sides of last equation, we have

   2³ + 4³ + 6³ + ... + (2n − 1)³ = 2n(n − 1)²n² + (2n)³ = 2n²[(n − 1)² + 4n] = 2n² (n + 1)²

   which is exactly P(n).□

We now give two equivalent alternative formulations 𝕊 and 𝕄, of the principle of mathematical induction ℙ₃ because in certain cases these formulation can be more useful.

1.5.5 𝕊: (Second Principle of Mathematical Induction: strong induction). Every subset A of ℕ such that

1. 0 ∈ A;

2. if k ∈ A for each k such that 0 ≤ k < n, then n ∈ A as well.

then A coincides with ℕ.

So to prove that a seuence of statements P(1), P(2), ..., P(n) is true, it suffices to prove two steps:

• Step 1 (Basis step). Prove that P(1) is true;

• Step 2 (Inductive step). Assuming that P(k) is true for a fixed integer k ≥ 1, prove that P(k + 1) is true.

Then P(n) is true for every positive integer n. In formulas

• P(1) and

• ∀k ∈ ℕ, (P(1) ∧ P(2) ∧ ... ∧ P(k)) ⇒ P(k + 1).

both hold, then P(n) is true for every prositive integer n.

The method of strong induction (or complete induction) assumes in step 2 that all P(1), P(2), ..., P(k) are true and we prove that P(k + 1) is true.
The difference between regular induction and the stron induction is in the inductive step. While regular induction only assumes the current step to be true, the strong induction assumes that all steps from the beginning to the current step to be true.

Example 1.5.6 For all n ≥ 1 we have 1 + 2 + ... + n = n(n + 1)/2.

Proof. We call P(n) the statement to be proved. For n = 1 the statemented becomes 1 = 1(1+1)/2, which is true.
Assume that for every k > 1, P(k) is true, i.e, 1 + ... + k = k(k + 1)/2. Then

hence P(k + 1) is also true.  □

1.5.7 𝕄: (The Well-Ordering principle) Every nonempty set T of ℕ contains a least element. That is, there is an element t ∈ T such that t ≤ x ∀x ∈ T.

A partially ordered set X is said Well-Ordered if every non-empty subset of X has a minimum element.

Proposition 1.5.8. The three principles ℙ₃, 𝕊 and 𝕄 are equivalent.

Proof. We assume true the strong mathematical principle and prove well-ordering. Suppose that S is a non-empty set of ℕ. Let T = ℕ \ S. Suppose by contradiction that S does not possess a minimum element. Then 1 ≠ S, otherwise it would be the minimum element of S since it is the minimum element of ℕ. Then 1 ∈ T. Suppose that for a k, we have 1 ≤ i ≤ k, i ∈ T. Consider k + 1. If k+1 were in S, it would be the minimum element in S because no i between 1 and k can be found in S. Since we are assuming that S has no minimum element, we must have k + 1 ∈ T. For the strong induction principle, T must contain all natural numbers, thus be equivalent to ℕ. It follows that S = ∅, a contradiction. We thus conclude that S has a minimum element.

We now assume true well-ordering and prove the strong mathematical induction. Let U a subset ℕ verifying the properties of 𝕊 and suppose by way of contradiction that U ≠ ℕ. Then given V = N \ U, it results V ≠ ∅. By 𝕄 there exists a least element m ∈ V, greater than zero, because 0 ∈ U. Since m is the least in V, every k such that 0 ≤ k < m is in U. But then by property (b) of 𝕊, m ∈ U, which is absurd. □

A practical example of these two proof methods can be given to prove the following proposition regarding division in ℕ.

1.5.9 Proposition. Let a,b ∈ ℕ, b ≠ 0. Then there exist two natural numbers q,r, such that

Proof. We use the Well-Ordering principle: let q + 1 the least integer b(q+1) > a (such a minimum integer exists for sure considering the non-empty set T = {x ∈ ℕ | bx > a})

We thus have

from which follows

Let r = a − bq, we have a = bq + r, 0 ≤ r < b. □

These principles of induction are often described using the image of a line of dominoes falling down. For weak induction, we prove that P(0) is true and that P(n) implies P(n + 1) for all n ≥ a. In the domino setting, this corresponds to knowing both that the first domino has fallen down and that when any domino falls down, the next domino in line must also fall down. These two observations about a line of dominoes leads to the conclusion that every domino in the line has fallen down. The principle of strong induction is similar except that we need to know that the first few dominos have fallen down, and that all the dominoes have fallen down up to some point in the line implies the next domino in line must also fall down. In some mathematical settings, the claim that a statement is true for a particular integer depends on knowing the statement is true for every preceding integer (rather than just the immediate predecessor).