Let $f,g:\mathbb{N}\to\mathbb{N}$ be functions such that $f$ is onto and g is one-one. If $f(n)\ge g(n)$ for all $n\in\mathbb{N}$, show that $f=g$.
Asked
Active
Viewed 74 times
2
-
8What have you tried so far? – user3482749 Jan 21 '20 at 15:36
-
3Hint: there is a number $x_0 \in \mathbb{N}$ such that $f(x_0) = 0$. Try to prove that it's unique. Then think about $x_1$. – Ashwin Iyengar Jan 21 '20 at 15:38
-
I am assuming that $\exists n\in\mathbb{N}$, such that $f(n)>g(n)$ and then trying to reach to a contradiction. – Eduline Jan 21 '20 at 16:21
-
@AshwinIyengar, but we cannot conclude the same as $0$ does not belong to $\mathbb{N}$, right? – Eduline Jan 21 '20 at 16:25
-
1@SanketBiswas That's a matter of convention. If that's not your convention, then start with $x_1$ such that $f(x_1) = 1$ instead, and do the exact same argument that Ashwin is hinting towards. – Arthur Jan 21 '20 at 16:27
-
Thanks @AshwinIyengar, your hint was really of immense help! – Eduline Jan 21 '20 at 18:17
-
Glad it helped! Yeah sorry I always assume 0 is a natural number, doesn't matter though. – Ashwin Iyengar Jan 21 '20 at 18:38
1 Answers
2
Okay, here goes the solution. Since, it is given that $f$ is onto, we can conclude that $\exists x_1\in\mathbb{N}$, such that $f(x_1)=1$. Now, we also have $f(x_1)\ge g(x_1)\implies g(x_1)\le 1\implies g(x_1)=1.$ Therefore, $f(x_1)=g(x_1)$. Now let $\exists x_1'\in \mathbb{N}$, such that $x_1'\neq x_1$ and $f(x_1')=f(x_1)=1$. Arguing similarly as above we will have $f(x_1')=g(x_1')=1\implies g(x_1)=g(x_1')=1$, which is false, since g is one-one. Therefore, $x_1$ is unique.
Again, we can say that $\exists x_2\in\mathbb{N}$, such that $f(x_2)=2$. Again by $f(x_2)\ge g(x_2)$, we have $g(x_2)\le 2$. This implies that either $g(x_2)=1$ or $g(x_2)=2$. But, since $g$ is one-one, and $g(x_1)=1$, therefore $g(x_2)=2$. Therefore, $f(x_2)=g(x_2)$. Again, arguing similarly as above, $x_2$ is unique.
Let us assume that for each $1\le n\le k$, we have shown that there exists unique $x_n\in \mathbb{N}$, such that $f(x_n)=g(x_n)=n$.
Now for $n=k+1$, we can again say that $\exists x_{k+1}\in\mathbb{N}$ such that $f(x_{k+1})=k+1.$ Now, by $f(x_{k+1})\ge g(x_{k+1})$, we are forced to have by our induction hypothesis $g(x_{k+1})=k+1$. Now let $\exists x_{k+1}'\in \mathbb{N}$, such that $x_{k+1}'\neq x_{k+1}$ and $f(x_{k+1}')=f(x_{k+1})=k+1$. Arguing similarly as above we will have $f(x_{k+1}')=g(x_{k+1}')=k+1\implies g(x_{k+1})=g(x_{k+1}')=k+1$, which is false, since g is one-one. Therefore, $x_{k+1}$ is unique.
Therefore, by the principle of mathematical induction, we can conclude that there exists unique $x_n\in\mathbb{N}$, such that $f(x_n)=g(x_n)=n,$ $\forall n\in\mathbb{N}.$
Therefore, we can conclude that $f(n)=g(n)$, $\forall n\in\mathbb{N}$.
Eduline
- 437
- 2
- 6