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?


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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.