# How to prove the mathematical induction is true?

I have no idea about the underlying theory from which the mathematical induction was derived.

How to prove the mathematical induction is true?

-
good question... – anonymous Feb 27 '11 at 10:28
That should be "mathematical induction" not "mathematics induction" – Arjang Feb 27 '11 at 11:11
How complex an answer are you looking for? – barrycarter Feb 27 '11 at 16:26
I think a good interpretation to this question is "Is there a more obvious set of principles upon which all of the induction propositions are based?" It's a bit disingenuous to make something as not-obvious as induction into an axiom. – DanielV Mar 20 '14 at 1:27

A "proof" in mathematics always means a proof in some system/theory. You have to specify the system/theory that you want a proof for the induction axiom. (You should also formally specify what you mean by the induction axiom since there are various axioms that are called induction axiom.)

The induction axiom in an arithmetical theory (like Peano arithmetic) is an axiom, i.e. it is one of the axioms of the theory, and therefore the proof is just a single line stating the axiom.

In a set theory like $ZFC$ we can prove the induction axiom for the set of natural numbers using the fact that the set of natural numbers is defined as the smallest inductive set that contains zero, and the proof is almost trivial. (An inductive set means a set that contains the successor of $x$ whenever it contains $x$).

In high school or undergraduate courses, when one is asked to prove induction axiom, they are usually asked to derive the induction axiom from some other axioms like the least number principle for natural numbers.

Another possible question is what are the justifications for believing that the induction axiom is true (or for accepting it as an axiom), which is a question in philosophy of mathematics and might be more suitable for MathOverflow.

-

The principle of induction (on the natural numbers) is equivalent to the axiom of well-foundedness of the natural numbers. Wikipedia gives (half of) a proof here.

-

The induction axiom in Peano Arithmetic says that for any predicate (statement about numbers) $\phi$, if you can prove $\phi(0)$ is true and you can also prove that for any number $n$, $\phi(n) \implies \phi(n+1)$ then $\phi(n)$ is true for all $n$. So you have proven $\phi(0)$ and $\phi(0) \implies \phi(1)$ and $\dots$ $\phi(10) \implies \phi(11)$ and $\dots$. Intuitively, if there is an $m$ such that $\phi(m)$ is not true, the base case of $\phi(0)$ or one of these implications must have broken down.

The usual structure of an inductive proof is designed to take advantage of this, so following one carefully may help. Arturo Magidin gave an excellent discussion in his answer to this post

-

If you are having difficulties accepting mathematical induction and other of Peano's Axioms, I find it helps to visualize the natural numbers as directed graph (a network of nodes connected by one-way arrows) as follows:

There is a node (call it 0) that has no arrows going into it (Axioms 1 and 3, below). Every node has an arrow leaving it (Axiom 2, below). Every node has at most one arrow going into it (Axiom 4). You can get to any node by starting at 0 and following the arrows; that is, there are no isolated portions of the graph (Axiom 5). You may also require that every node have at most one arrow leaving it (not explicitly covered in the axioms as presented below).

(Peano's Axioms from from Wolfram MathWorld http://mathworld.wolfram.com/PeanosAxioms.html)

1. Zero is a number.

2. If x is a number, the successor of x is a number.

3. Zero is not the successor of a number.

4. Two numbers of which the successors are equal are themselves equal.

5. If a set of numbers contains zero and also the successor of every number in , then every number is in .

The following is a better presentation of Peano's axioms (from http://www.ms.uky.edu/~lee/ma502/notes2/node7.html) It uses 1 instead of 0 as the first natural number. Unlike the above presentation, the fact that, graphically, there would be at most one arrow leaving each node is made explicit in Axiom 2, below.

Axiom 1: 1 is a natural number. That is, our set is not empty; it contains an object called 1 (read "one").

Axiom 2: For each x there exists exactly one natural number, called the successor of x, which will be denoted by x'.

Axiom 3: We always have ~x'=1. That is, there exists no number whose successor is 1. That is, there exists no number whose successor is 1.

Axiom 4: If x'=y' then x=y. That is, for any given number there exists either no number or exactly one number whose successor is the given number.

Axiom 5 (Axiom of Induction): Let there be given a set M of natural numbers, with the following properties: I. 1 belongs to M. II. If x belongs to M then so does x'. Then M contains all the natural numbers.

-

Well, in principles induction is, having something holding for $0$, denoted as $h(0)$, and if $h(n)$ implies $h(n')$, where $n'$ is a successor of $n$, i.e. $n+1$, we have $h(n)$ for any natural number of $n$.

On the other hand, natural numbers are defined as the smallest set that contains 0 and closed to successor operation (i.e. if $n$ is natural so is $n'$).

The correctness of induction follows strictly from the fact the natural numbers are the the smallest set satisfying the same condition as induction.

-