# Principle of Finite Induction

## Contents

## Theorem

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: n \in S \implies n + 1 \in S$

Then:

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

That is:

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

The **principle of finite 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 $S \subseteq \N$ be a subset of the natural numbers.

Suppose that:

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

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

Then:

- $S = \N$

### One-Based

Let $S \subseteq \N_{>0}$ be a subset of the $1$-based natural numbers.

Suppose that:

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

- $(2): \quad \forall n \in \N_{>0} : n \in S \implies n + 1 \in S$

Then:

- $S = \N_{>0}$

## Proof 1

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

Aiming for a contradiction, suppose $S \ne \Z_{\ge n_0}$.

Let $S' = \Z_{\ge n_0} \setminus S$.

Because $S \ne \Z_{\ge n_0}$ and $S \subseteq \Z_{\ge n_0}$, we have that $S' \ne \O$.

By definition, $\Z_{\ge n_0}$ is bounded below by $n_0$.

From Set of Integers Bounded Below by Integer has Smallest Element, $S'$ has a minimal element.

Let $k$ be this minimal element of $S'$.

By $(1)$ we have that:

- $n_0 \in S$

and so:

- $n_0 \notin S'$

Hence:

- $k \ne n_0$

and so:

- $k > n_0$

It follows that:

- $k - 1 \le n_0$

Because $k$ is the minimal element of $S'$:

- $k - 1 \notin S'$

and so:

- $k - 1 \in S$

But by $(2)$:

- $\paren {k - 1} + 1 = k \in S$

So we have:

- $k \in S$

and:

- $k \notin S$

Hence by Proof by Contradiction $S = \Z_{\ge n_0}$.

$\blacksquare$

## Proof 2

Consider $\N$ defined as a naturally ordered semigroup.

The result follows directly from Principle of Mathematical Induction for Naturally Ordered Semigroup: General Result.

$\blacksquare$

## Contexts

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

### Peano Structure

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

Let $S \subseteq P$.

Suppose that:

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

- $(2): \quad \forall n: n \in S \implies \map s n \in S$

Then:

- $S = P$

## Terminology

### Basis for the Induction

The step that shows that the integer $n_0$ is an element of $S$ is called the **basis for the induction**.

### Induction Hypothesis

The assumption made that $n \in S$ for some $n \in \Z$ is the **induction hypothesis**.

### Induction Step

The step which shows that $n \in S \implies n + 1 \in S$ is called the **induction step**.

## Also known as

Some sources refer to the **Principle of Finite Induction** as the **Principle of Mathematical Induction**, and gloss over the differences between the two proof techniques if they discuss them both at all.

Hence the word **finite** may well not appear in the various published expositions of this technique.

Some sources refer to the **Principle of Finite Induction** as the ** First Principle of (Finite) Induction**, to distinguish it from the

**Second Principle of Finite Induction**.

Some call it the **induction principle**.

The abbreviation **PFI** is often seen.

Some sources call it the **Principle of Weak (Finite) Induction**.

Such sources may similarly refer to the **Second Principle of Finite Induction** as the **Principle of Strong (Finite) 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 Finite Induction** is often referred to as **Proof by (Finite) Induction**.

## Also see

## Sources

- 1972: A.G. Howson:
*A Handbook of Terms used in Algebra and Analysis*... (previous) ... (next): $\S 4$: Number systems $\text{I}$: Peano's Axioms - 2008: Paul Halmos and Steven Givant:
*Introduction to Boolean Algebras*... (previous) ... (next): Appendix $\text{A}$: Set Theory: Induction