# $h$ is an one-to-one correspondence and so $Y$ is countably infinite

I am working on this problem in set theory:

Let $X$ is a countable infinite set and $Y\subsetneq X$. Moreover let $g:X\to\mathbb N$ is a one-one and onto function and $h:Y\to\mathbb N$ with $$h(y)=\{1,2,3,...,g(y)\}\cap g(Y)$$ Prove that $h$ is an one-to-one correspondence and so $Y$ is countably infinite.

Honestly, I used my imagination to see what is going on in this problem. :-) I went via elementary method. In fact, I saw the function $h$ is well-defined and indeed if $h(x)=h(y), ~~x,y\in Y$ then by assuming for example $g(x)<g(y)$ the number $h(x)=\{1,2,3,...,g(x)\}\cap g(Y)$ can be lass than the number $h(y)$ and this is a pretty contradiction. So the first round was done safely.

I really ask to have a solution for proving that $h$ is onto. If you have another approach , please let me know. Thanks.

-
$+ \;\;\ddot\smile\;\;$ –  amWhy Apr 16 '13 at 16:19

You don’t have to prove that $h$ is onto; in fact in general you can’t, because $Y$ might be a finite subset of $X$. All you can prove is that $Y$ is countable, meaning finite or countably infinite, and you’ve done that as soon as you’ve proved that $h$ is one-to-one, because then it’s a bijection between $Y$ and a subset of $\Bbb N$.
I would slightly rephrase your proof that $h$ is one-to-one, but the idea is fine. If $g(x)<g(y)$, then by definition $g(y)\in h(y)\setminus h(x)$, so $h(y)\ne h(x)$.