# What am I missing in this induction proof?

Prove that if $g:\mathbb{N}\rightarrow \mathbb{N}$ and $\forall x,y\in \mathbb{N}, x<y\Rightarrow g(x)<g(y)$ then $n\leq g(n)\space\space\space \forall n\in \mathbb{N}$

My proof so far (induction): It's tru for 1 since 1 is less or equal any number in $\mathbb{N}$.

Let's suppose for $k$, $k\leq g(k)$, we got this:

$$k<k+1\Rightarrow g(k)<g(k+1)$$ so, $k\leq g(k)<g(k+1)$ And then I don't know what else to do. As far as I understand the operation "$-$" isn't defined yet for $\mathbb{N}$.

• I've been suggested to use this property (which im not sure it actually exists) "if $k<g(k+1)$ then $k+1\leq g(k+1)$" – José Osorio Jun 10 '16 at 5:59
• nope, it is strict. (why? do you think the problem is wrong? – José Osorio Jun 10 '16 at 6:04
• I can see why $g(x) < g(y)$ must be a strict inequality, but you need to have "then $n \leq g(n)$", since $g(n) = n$ fulfills the requirements. – Arthur Jun 10 '16 at 6:09
• if $n<g(n)$ , you need to suppose $k<g(k)$ and not $k\leq g(k)$ – user160823 Jun 10 '16 at 6:12

You're very close. Since $k < g(k+1)$, we must have $k+1 \leq g(k+1)$, since there are no numbers between $k$ and $k+1$. That finishes the induction step.
Together with my comment above that the problem needs to read "then $n \leq g(n)$" because of the function $g(n) = n$, the problem is now solved.