So I understand two sets have the same cardinality if you can map a function between them that is one-to-one and onto, but does it have to be the same function? Would it worked if I mapped one function that is onto, and another one that is one-to-one? If not, why?
[Math] Showing two sets have the same cardinality
cardinalsfunctionsset-theory
Best Answer
The definition of when sets $X$ and $Y$ have the same cardinality is that there exists a function $f:X\to Y$ which is both one-to-one and onto. So according to the definition, you need a single function with both properties at once.
However, it turns out that if you have separate functions $X\to Y$ with just one of the properties each, this implies there exists a function with both at once. Specifically, suppose $g:X\to Y$ is one-to-one and $h:X\to Y$ is onto. Take a function $i:Y\to X$ which is a sort of "inverse" to $h$, in the sense that for each $y\in Y$, $i(y)$ is one of the points $x\in X$ such that $h(x)=y$ (we know that at least one such $x$ exists since $h$ is onto). That is, we have $h(i(y))=y$ for all $y\in Y$.
I claim now that $i:Y\to X$ is one-to-one. Indeed, suppose that $i(y)=i(y')$. Applying $h$ to both sides, we get $h(i(y))=h(i(y'))$. But $h(i(y))=y$ and $h(i(y'))=y'$, so this means $y=y'$. Thus $i$ is one-to-one.
We now have both a one-to-one function $g:X\to Y$ and a one-to-one function $i:Y\to X$. The Schröder-Bernstein Theorem now says there exists a function $f:X\to Y$ which is both one-to-one and onto. (We can define $f$ in terms of $g$ and $i$, but it is pretty complicated--see the link above for more details).
Thus if you have one function $X\to Y$ which is one-to-one and another function $X\to Y$ which is onto, this implies $X$ and $Y$ have the same cardinality.
[As a caveat, the existence of a function $i$ as described in the second paragraph above requires the axiom of choice: for each $y\in Y$, you must choose one $x\in X$ such that $h(x)=y$. In fact, without the axiom of choice, the final result may not be true. As bof commented, there exists a one-to-one map $\mathbb{R}\to\mathbb{R}\cup\omega_1$ and also an onto map $\mathbb{R}\to\mathbb{R}\cup\omega_1$, but it is impossible to prove $\mathbb{R}$ and $\mathbb{R}\cup\omega_1$ have the same cardinality without using the axiom of choice.]