Question

prove Principle of Mathematical Induction using Peano axioms

Answer 1

Conditions

prove Principle of Mathematical Induction using Peano axioms

Solution

The Peano axioms define the arithmetical properties of natural numbers, usually represented as a set $N$ or. The signature (a formal language's non-logical symbols) for the axioms includes a constant symbol 0 and a unary function symbol $S$.

The constant 0 is assumed to be a natural number:

0 is a natural number.

The next four axioms describe the equality relation.

For every natural number $x, x = x$. That is, equality is reflexive.

For all natural numbers $x$ and $y$, if $x = y$, then $y = x$. That is, equality is symmetric.

For all natural numbers $x, y$ and $z$, if $x = y$ and $y = z$, then $x = z$. That is, equality is transitive.

For all $a$ and $b$, if $a$ is a natural number and $a = b$, then $b$ is also a natural number. That is, the natural numbers are closed under equality.

The remaining axioms define the arithmetical properties of the natural numbers. The naturals are assumed to be closed under a single-valued "successor" function $S$.

For every natural number $n$, $S(n)$ is a natural number.

Peano's original formulation of the axioms used 1 instead of 0 as the "first" natural number. This choice is arbitrary, as axiom 1 does not endow the constant 0 with any additional properties. However, because 0 is the additive identity in arithmetic, most modern formulations of the Peano axioms start from 0. Axioms 1 and 6 define a unary representation of the natural numbers: the number 1 can be defined as $S(0)$, 2 as $S(S(0))$ (which is also $S(1)$), and, in general, any natural number $n$ as $S_n(0)$. The next two axioms define the properties of this representation.

For every natural number $n$, $S(n) = 0$ is false. That is, there is no natural number whose successor is 0.

For all natural numbers $m$ and $n$, if $S(m) = S(n)$, then $m = n$. That is, $S$ is an injection.

Axioms 1, 6, 7 and 8 imply that the set of natural numbers contains the distinct elements 0, S(0), S(S(0)), and furthermore that {0, S(0), S(S(0)), ...} ⊆ N. This shows that the set of natural numbers is infinite. However, to show that $N = \{0, S(0), S(S(0)), \ldots\}$, it must be shown that $N \subseteq \{0, S(0), S(S(0)), \ldots\}$; i.e., it must be shown that every natural number is included in {0, S(0), S(S(0)), ...}. To do this however requires an additional axiom, which is sometimes called the

axiom of induction. This axiom provides a method for reasoning about the set of all natural numbers.

If K is a set such that:

0 is in K, and

for every natural number n, if n is in K, then S(n) is in K,

then K contains every natural number.

The induction axiom is sometimes stated in the following form:

If $\phi$ is a unary predicate such that:

$\phi(0)$ is true, and

for every natural number n, if $\phi(n)$ is true, then $\phi(S(n))$ is true,

then $\phi(n)$ is true for every natural number n.

Now let's prove the principle of mathematical induction, using these axioms.

For instance, it can be proved if one assumes:

The set of natural numbers is well-ordered.

Every natural number is either zero, or $n + 1$ for some natural number $n$.

For any natural number $n$, $n + 1$ is greater than $n$.

To derive simple induction from these axioms, we must show that if $P(n)$ is some proposition predicated of $n$, and if:

P(0) holds and

whenever $P(k)$ is true then $P(k + 1)$ is also true

then $P(n)$ holds for all n.

Proof. Let $S$ be the set of all natural numbers for which $P(n)$ is false. Let us see what happens if we assert that $S$ is nonempty. Well-ordering tells us that $S$ has a least element, say $t$. Moreover, since $P(0)$ is true, $t$ is not 0. Since every natural number is either zero or some $n + 1$, there is some natural number $n$ such that $n + 1 = t$. Now $n$ is less than $t$, and $t$ is the least element of $S$. It follows that $n$ is not in $S$, and so $P(n)$ is true. This means that $P(n + 1)$ is true, and so $P(t)$ is true. This is a contradiction, since $t$ was in $S$. Therefore, $S$ is empty.

It can also be proved that induction, given the other axioms, implies well-ordering.