Sets having the same cardinality

Question

I am asked to think of an example of cardinality being the same between two sets X and Y such that the function from X to Y is one to one but it is not onto. I am so confused about this one because I thought there has to be a one-to-one correspondence between X and Y for their cardinality to be the same. How is it possible for there to just be a one-to-one relationship? Can anyone please explain? Thank you!

Answer 1

Saying that two sets $X, Y$ have the same cardinality says that there exists some function $f: X \longrightarrow Y$ which is one to one and onto. It says nothing about what other functions can exist. For instance, if $X = Y = \mathbb R$ we can consider $g: \mathbb R \longrightarrow \mathbb R$ such that $g(x) = 0$. Even though $\mathbb R$ and $\mathbb R$ obviously have the same cardinality, this does not preclude this function from existing.

Now, there is a legitimate obstruction to your question. Suppose that $X$ and $Y$ had the same cardinality and that there did exist some function $f: X \longrightarrow Y$ that was one to one but not onto. Then $f$ will yield a one to one correspondence $X \longrightarrow f[X]$ onto the image of $f$. Thus, we will have $|X| = |f[X]|$, but we already had $|Y| = |X|$. Hence, $|Y| = |f[X]|$. Because $f$ was not onto, $f[X]$ is therefore a proper subset of $Y$ with the same cardinality as $Y$. This would be impossible if $|Y|$ was finite, but for infinite sets strange things like this can happen.

Anyways, here's your example: take $X = Y = \mathbb N$ and let $f: \mathbb N \longrightarrow \mathbb N$ via $f(x) = 2x$. This is one to one, as if $2x = 2y$ we can divide by $2$ to get $x = y$. It is not onto, a for instance $1$ is not in the image. Hence, $f$ is one to one and not onto.