Definition:Basis for the Induction

From ProofWiki
Jump to navigation Jump to search

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 step that establishes the truth of $Q$ for $w_0$ is called the basis for the induction.


Expressed in the various contexts of mathematical induction:


First Principle of Finite Induction

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


First Principle of Mathematical 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.


Second Principle of Finite Induction

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


Second Principle of Mathematical 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.


Principle of General Induction

The step that shows that the propositional function $P$ holds for $\O$ is called the basis for the induction.


Principle of General Induction for Minimally Closed Class

The step that shows that the propositional function $P$ holds for the distinguished $b \in M$ is called the basis for the induction.


Principle of Superinduction

The step that shows that the propositional function $P$ holds for $\O$ is called the basis for the induction.


Also known as

The basis for the induction is often informally referred to as the base case.


Also see


Sources