Principle of mathematical induction states that if a subset $S$ of a successor set $\omega$ is also a successor set, then $S=\omega$. In primitive terms, it is formulated as:

if $S \subset \omega$, if $0 \in S$, and if $n^+ \in S$ whenever $n \in S$, then $S=\omega$.

Now, I wonder what if a statement that I want to prove holds for numbers starting from $b \in \omega$ for example. Would it be correct to introduce

  1. a set $L$ that contains all natural numbers that satisfy the statement

  2. a function $s: \omega \to \omega, s(n) = n^+$

  3. a function $r: \omega \to \omega, \begin{cases} r(0) = b\\ r(n^+) = s(r(n))\\ \end{cases}$

  4. a set $S$ that contains all natural numbers for which $r(n)\in L$

and show that $0$, $n$ and $n^+$ are in $S$? Because I can't just start proving inductively from $b$ and say that it holds for all numbers starting from $b$, as the principle of induction clearly states that $0$ has to be in $S$ too. So, I introduce a trick, i.e. mapping to perform induction.

Is it correct to do so? If not, then how to formally show that I can start from any number?


1 Answer 1


You can either generalize the principle of induction to:

"For all $b \in \omega$: if $S \subset \omega$, if $b \in S$, and if $n^+ \in S$ whenever $n \in S$, then $S=\{ n \in \omega | n \geq b \}$."

Or, you can use the principle as stated and prove the base and step for the property $P(n)$ defined as $n \geq b \to P'(n)$, where $P'(n)$ is the 'real' property you are interested in, i.e. the property you want to prove all numbers $n \geq b$ to have. This works, since $P(n)$ will be trivially true for all $n < b$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .