# prove that (f: ℕ-->ℕ is strictly increasing) ⇒ ∀(x ∈ ℕ)[ x <= f(x)]

My math prof used this result in a proof about sequences without justification. I tried to prove it myself (as an exercise), but my proof quickly got out of control. I ended up using set cardinality and the injectivity of strictly increasing functions. My (unfinished) proof also depends on the truth value of [|A| > |B|] ⇒ A ⊈ B, which I think will be even harder to prove (if it is not axiomatic). Is there a more obvious way to prove this result? I feel like there must be because my prof stated it without explaining.

Thank you.

• Did you try by induction? Aug 3, 2019 at 18:36

By induction: $$0 \leq f(0)$$ is ok.

Then if $$n\leq f(n) \Rightarrow n+1 \leq f(n)+1 \leq f(n+1)$$ because $$f$$ is strictly increasing.

The last "$$\leq$$" is because $$f(n) < f(n+1) \Rightarrow f(n)+1 \leq f(n+1)$$.

• Wow, yes! Thank you. I feel a bit dumb lol. Aug 3, 2019 at 18:41
• How do you know that $0\leq f(0)$? Couldn't the function be strictly increasing and be less than $0$ at $f(0)$? For example, $f(x)=x-3$ is strictly increasing and $f(0)=-3$. Aug 3, 2019 at 20:43
• @Axion004 It's given that $f:\Bbb N\to\Bbb N$. Aug 3, 2019 at 23:41

Proof by Mathematical induction is straight forward.

$$f(1)\ge 1$$ by the definition of $$f(n)\in \mathbb{N}$$

If $$f(n)\ge n$$ then $$f(n+1)>f(n)\ge n$$ thus $$f(n+1)\ge n+1$$

That proves the desired result.