Definition:Induction Hypothesis
Terminology of Mathematical Induction
Consider a proof by mathematical induction:
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$.
The assumption that $Q$ is true for $w_p$ is called the induction hypothesis.
Expressed in the various contexts of mathematical induction:
First Principle of Finite Induction
The assumption made that $n \in S$ for some $n \in \Z$ is the induction hypothesis.
First Principle of Mathematical Induction
The assumption made that $\map P k$ is true for some $k \in \Z$ is the induction hypothesis.
Second Principle of Finite Induction
The assumption that $\forall k: n_0 \le k \le n: k \in S$ for some $n \in \Z$ is the induction hypothesis.
Second Principle of Mathematical Induction
The assumption that $\forall j: n_0 \le j \le k: \map P j$ is true for some $k \in \Z$ is the induction hypothesis.
Principle of General Induction
The assumption made that $\map P x$ is true for some $x \in M$ is called the induction hypothesis.
Principle of General Induction for Minimally Closed Class
The assumption made that $\map P x$ is true for some $x \in M$ is called the induction hypothesis.
Principle of Superinduction
The assumption made that $\map P x$ is true for some $x \in M$ is called the induction hypothesis.
Also known as
The induction hypothesis can also be referred to as the inductive hypothesis.
Also see
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction