Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I managed to prove that if $\phi(0)$ and $\forall n(n\in\mathbb{N},\phi(n)\rightarrow\phi(n+1))$ then $\forall n(n\in\mathbb{N}\rightarrow\phi(n))$. The proof is based on the fact that $\{m\in\mathbb{N}:\phi(m)\}$ is an inductive set. Now I'd like to show (but I can't) that if you take a $k\in\mathbb{N}$, if $\phi(k)$ and $\forall n(n\in\mathbb{N},k\leq n,\phi(n)\rightarrow\phi(n+1))$ then $\forall n(n\in\mathbb{N},k\leq n\rightarrow\phi(n))$. The problem is I cannot show that $\{m\in\mathbb{N}:k\leq m,\phi(m)\}$ is an inductive set, since it is obvious, for example, that it doesn't contain zero as an element (except if $k=0$). What can I do instead? Thanks.

share|cite|improve this question
up vote 3 down vote accepted

Prove instead that the set $\{m\in\mathbb{N}\colon m\lt k\}\cup\{m\in\mathbb{N}\colon\phi(m)\}$ is inductive, and thus equals $\mathbb{N}$. Then use this to deduce what you want. (That is, take every element for which $\phi(m)$ holds, and then "throw in for free" every number strictly less than $k$, since you do not care what happens to them, and show that this is the set of all natural numbers).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.