2

Assume some function $f\in \mathbb N^{\mathbb N}$ which is strictly increasing (i.e. $f(n+1)>f(n)$ for all $n\in \mathbb N$). Then for every natural number $N$ we can find some natural number $N_0$ such that $f(N_0)\ge N$.

I observed this to be true, and so I made an attempt for a proof. So I begun with a proof by contradiction, which is to assume that there exists some natural number $N$ so that we have the following: $f(n)<N$ for all $n\in \mathbb N$. Which means that the set $f(\mathbb N)=\{f(n)|n\in \mathbb N\}$ is bounded above $N$.

From this point on, I can see that this an immediate contradiction, since $f(\mathbb N)\subseteq \mathbb N$ and that every infinite subset of $\mathbb N$ is not bounded above. But, how would I go about proving this rigorously? Should I make use of the Supremum property?

Vaskara_GRek_O
  • 119

1 Answers1

1

Note that I have changed my answer completely.

Assume $f\in \mathbb N^{\mathbb N}$ is strictly increasing (i.e. $f(n+1)>f(n)$ for all $n\in \mathbb N$).

Let $N\in\mathbb{N}.$

Since $f:\mathbb{N}\to\mathbb{N},\ f(1) \geq 1.\ $ Since $f$ is strictly increasing, $f(2) > f(1) \geq 1,\ $ and so $f(2) \geq 2.$ With similar reasoning, $f(3) \geq 3.$ And furthermore, $f(k)\geq k\ $ for all $k.$ I guess to prove this formally you would use induction on $k.$

Thus $f(N)\geq N$ and so $N_0=N$ satisfies the statement, "There exists $N_0$ such that $f(N_0)\ge N$. "

Adam Rubinson
  • 20,052
  • 1
    How do you know that $N-f(1)$ is in fact a positive integer? – Vaskara_GRek_O Jul 09 '23 at 14:09
  • @Vaskara_GRek_O good point. And well done for challenging my answer rather than blindly accepting it, which is happening a lot recently on this site. I'll give it some thought. – Adam Rubinson Jul 09 '23 at 14:45
  • I have changed my answer completely. Let me know if the new answer is OK. – Adam Rubinson Jul 09 '23 at 14:53
  • That's great and the fact that $f(k)\ge k$ for all positive integers $k$ is actually what I should have gone with in the first place, since it's proof is trivial and it pretty much gives light to the key part of another proof I was working on. Also, I saw that Peter's hint indeed does help, by seeing that for some fixed positive integer $k_0$ we have that $sup(f(\mathbb N))\ge f(n+k_0)\ge f(n)+k_0$ or $f(n)\le supf((\mathbb N))-k_0$ for all naturals $n$, and so $supf(\mathbb N)-k_0$ is an upper bound of $f(\mathbb N)$, so $sup(f(\mathbb N))-k_0 \ge sup(f(\mathbb N))$, a contradiction. – Vaskara_GRek_O Jul 09 '23 at 18:34