# Definition:Mathematical Induction

## Proof Technique

**Mathematical induction** is a proof technique which works in two steps as follows:

- $(1): \quad$ A statement $Q$ is established as being true for some distinguished element $w_0$ of a well-ordered set $W$.

- $(2): \quad$ A proof is generated demonstrating that if $Q$ is true for an arbitrary element $w_p$ of $W$, then it is also true for its immediate successor $w_{p^+}$.

The conclusion is drawn that $Q$ is true for all elements of $W$ which are successors of $w_0$.

It is established in a number of contexts, according to how it is to be used.

### Principle of Finite Induction

Let $n_0 \in \Z$ be given.

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

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

Let $S \subseteq \Z_{\ge n_0}$ be a subset of $\Z_{\ge n_0}$.

Suppose that:

- $(1): \quad n_0 \in S$

- $(2): \quad \forall n \ge n_0: n \in S \implies n + 1 \in S$

Then:

- $\forall n \ge n_0: n \in S$

That is:

- $S = \Z_{\ge n_0}$

### Principle of General Induction

Let $M$ be a class.

Let $g: M \to M$ be a mapping on $M$.

Let $M$ be minimally inductive under $g$.

Let $P: M \to \set {\T, \F}$ be a propositional function on $M$.

Suppose that:

\((1)\) | $:$ | \(\ds \map P \O \) | \(\ds = \) | \(\ds \T \) | |||||

\((2)\) | $:$ | \(\ds \forall x \in M:\) | \(\ds \map P x \) | \(\ds = \) | \(\ds \T \implies \map P {\map g x} = \T \) |

Then:

- $\forall x \in M: \map P x = \T$

### Principle of Mathematical Induction

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$.

### Second Principle of Finite Induction

Let $S \subseteq \Z$ be a subset of the integers.

Let $n_0 \in \Z$ be given.

Suppose that:

- $(1): \quad n_0 \in S$

- $(2): \quad \forall n \ge n_0: \paren {\forall k: n_0 \le k \le n \implies k \in S} \implies n + 1 \in S$

Then:

- $\forall n \ge n_0: n \in S$

### Second Principle of Mathematical Induction

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 {n_0} \land \map P {n_0 + 1} \land \ldots \land \map P {k - 1} \land \map P k \implies \map P {k + 1}$

Then:

- $\map P n$ is true for all $n \ge n_0$.

This process is called **proof by (mathematical) induction**.

## Terminology

### Basis for the Induction

The step that establishes the truth of $Q$ for $w_0$ is called the **basis for the induction**.

### Induction Hypothesis

The assumption that $Q$ is true for $w_p$ is called the **induction hypothesis**.

### Induction Step

The proof that the truth of $Q$ for $w_p$ implies the truth of $Q$ for $w_{p^+}$is called the **induction step**.

## Also see

- Do not confuse with Definition:Inductive Argument.

- Results about
**Proofs by Induction**can be found**here**.