Principle of Induction

Theorem

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

Principle 1

Let $\On$ denote the class of all ordinals.

Let $A$ denote a class.

Suppose that:

For all elements $x$ of $\On$, if $x$ is a subset of $A$, then $x$ is an element of $A$.

Then $\On \subseteq A$.

Schema 1

Let $\map P x$ be a property

Suppose that:

If $\map P x$ holds for all ordinals $x$ less than $y$, then $\map P y$ also holds.

Then $\map P x$ holds for all ordinals $x$.

Principle 2

Let $A$ be a class satisfying the following conditions:

• $\O \in A$
• $\forall x \in A: x^+ \in A$
• If $y$ is a limit ordinal, then $\paren {\forall x < y: x \in A} \implies y \in A$

where $x^+$ denotes the successor of $x$.

Then $\On \subseteq A$.

Schema 2

Let $\map \phi x$ be a property satisfying the following conditions:

$(1): \quad \map \phi \O$ is true

$(2): \quad$ If $x$ is an ordinal, then $\map \phi x \implies \map \phi {x^+}$

$(3): \quad$ If $y$ is a limit ordinal, then $\paren {\forall x < y: \map \phi x} \implies \map \phi y$

where $x^+$ denotes the successor of $x$.

Then, $\map \phi x$ is true for all ordinals $x$.

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 Structural Induction

Let $\LL$ be a formal language.

Let the formal grammar of $\LL$ be a bottom-up grammar.

Let $\map P \phi$ be a statement (in the metalanguage of $\LL$) about well-formed formulas $\phi$ of $\LL$.

Then $P$ is true for all WFFs of $\LL$ if and only if both:

$\map P a$ is true for all letters $a$ of $\LL$,

and, for each rule of formation of $\LL$, if $\phi$ is a WFF resulting from WFFs $\phi_1, \ldots, \phi_n$ by applying that rule, then:

$\map P \phi$ is true only if $\map P {\phi_1}, \ldots, \map P {\phi_n}$ are all true.