Principle of Mathematical Induction

From ProofWiki
Jump to: navigation, search

Theorem

Let $\map P n$ be a propositional function depending on $n \in \Z$.

Let $n_0 \in \Z$ be given.


Suppose that:

$(1): \quad \map P {n_0}$ is true
$(2): \quad \forall k \in \Z: k \ge n_0 : \map P k \implies \map P {k + 1}$


Then:

$\map P n$ is true for all $n \in \Z$ such that $n \ge n_0$.


The principle of mathematical induction is usually stated and demonstrated for $n_0$ being either $0$ or $1$.

This is often dependent upon whether the analysis of the fundamentals of mathematical logic are zero-based or one-based.


Zero-Based

Let $\map P n$ be a propositional function depending on $n \in \N$.

Suppose that:

$(1): \quad \map P 0$ is true
$(2): \quad \forall k \in \N: k \ge 0 : \map P k \implies \map P {k + 1}$


Then:

$\map P n$ is true for all $n \in \N$.


One-Based

Let $\map P n$ be a propositional function depending on $n \in \N_{>0}$.

Suppose that:

$(1): \quad \map P 1$ is true
$(2): \quad \forall k \in \N_{>0}: k \ge 1 : \map P k \implies \map P {k + 1}$


Then:

$\map P n$ is true for all $n \in \N_{>0}$.


Proof

Let $\Z_{\ge n_0}$ denote the set:

$S = \set {n \in \Z: n \ge n_0}$

Let $S$ be the set of integers defined as:

$S = \set {n \in \Z_{\ge n_0}: \map P n}$

That is, the set of all integers for which $n \ge n_0$ and for which $\map P n$ holds.

From Subset of Set with Propositional Function we have that:

$S \subseteq \Z_{\ge n_0}$


From $(1)$ we have that $\map P {n_0}$.

Hence $n_0 \in S$.

Let $k \in S$.

Then $\map P k$ holds.

But by $(2)$, $\map P {k + 1}$ also holds.

This implies $k + 1 \in S$.

So as:

$S \subseteq \Z_{\ge n_0}$

and:

$S$ satisfies $(1)$ and $(2)$

it follows by the Principle of Finite Induction that $S = \Z_{\ge n_0}$.

Hence for all $n \ge n_0$, $\map P n$ holds.

$\blacksquare$


Contexts

The Principle of Mathematical Induction can be introduced in a formal development of abstract algebra or mathematical logic in various contexts, and proved from first principles in each.


Well-Ordered Set

Let $\struct {S, \preceq}$ be a well-ordered set.


Let $T \subseteq S$ be a subset of $S$ such that:

$\forall s \in S: \paren {\forall t \in S: t \prec s \implies t \in T} \implies s \in T$


Then $T = S$.


Well-Ordered Integral Domain

Let $\struct {D, +, \times, \le}$ be a well-ordered integral domain whose zero is $0_D$.

Let the unity of $D$ be $1_D$.


Let $S \subseteq D$ be such that:

$1_D \in S$
$a \in S \implies a + 1_D \in S$


Then:

$D_{> 0_D} \subseteq S$

where $D_{> 0_D}$ denotes all the elements $d \in D$ such that $\map P d$.

That is, $D_{> 0_D}$ is the set of all (strictly) positive elements of $D$.


Naturally Ordered Semigroup

Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.

Let $T \subseteq S$ such that $0 \in T$ and $n \in T \implies n \circ 1 \in T$.


Then $T = S$.


Peano Structure

Let $\struct {P, s, 0}$ be a Peano structure.

Let $\map Q n$ be a propositional function depending on $n \in P$.


Suppose that:

$(1): \quad \map Q 0$ is true
$(2): \quad \forall n \in P: \map Q n \implies \map Q {\map s n}$


Then:

$\forall n \in P: \map Q n$


Terminology

Basis for the Induction

The step that shows that the proposition $\map P {n_0}$ is true for the first value $n_0$ is called the basis for the induction.


Induction Hypothesis

The assumption made that $\map P k$ is true for some $k \in \Z$ is the induction hypothesis.


Induction Step

The step which shows that $\map P k \implies \map P {k + 1}$ is called the induction step.


Also defined as

This principle can often be found stated more informally, inasmuch as the propositional function $P$ is referred to as "a statement about integers".


Also known as

Some sources refer to the Principle of Mathematical Induction as the First Principle of (Mathematical) Induction, to distinguish it from the Second Principle of Mathematical Induction.

Some call it the induction principle.

The abbreviation PMI is often seen.


Some sources call it the Principle of Weak Induction.

Such sources may similarly refer to the Second Principle of Mathematical Induction as the Principle of Strong Induction.

These names are misleading, as both principles are equivalent, and so neither is weaker or stronger than the other.


The process of demonstrating a proof by means of the Principle of Mathematical Induction is often referred to as Proof by (Mathematical) Induction.


Also see

  • Results about Proofs by Induction can be found here.


Historical Note

The first European to use the Principle of Mathematical Induction rigorously in a proof appears to have been Francesco Maurolico, in Arithmeticorum Libri Duo ($1575$).

Further improvements were made by Pierre de Fermat, from which be derived his Method of Infinite Descent.

The Principle of Mathematical Induction appeared again in an adequately rigorous manner by Blaise Pascal in his Traité du Triangle Arithmétique ($1655$).

The phrase mathematical induction appears to have been coined by Augustus De Morgan.

Further discussion of the process can also be found in Induction and Analogy in Mathematics by George Pólya ($1954$).


Sources