3
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Did you try by induction? $\endgroup$
    – dcolazin
    Aug 3, 2019 at 18:36

2 Answers 2

6
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Wow, yes! Thank you. I feel a bit dumb lol. $\endgroup$
    – push33n
    Aug 3, 2019 at 18:41
  • $\begingroup$ 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$. $\endgroup$
    – Axion004
    Aug 3, 2019 at 20:43
  • 2
    $\begingroup$ @Axion004 It's given that $f:\Bbb N\to\Bbb N$. $\endgroup$ Aug 3, 2019 at 23:41
0
$\begingroup$

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.

$\endgroup$

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.