# Cardinality and onto function

I know that if card(X) $\leq$ card(Y) then there exists a one to one function $f:X\to Y$. However, does it mean that $|X|\leq|Y|$ can also happen if and only if there exists an onto function $g:Y\to X$?

-

## 1 Answer

Assuming the axiom of choice, the two statements are equivalent. In the absence of the axiom of choice, however, it is consistent with ZF to have sets $X$ and $Y$ and an onto function $g:Y\to X$ but no one-to-one function $f:X\to Y$. In fact, it’s consistent to have functions $f:X\to Y$ and and $g:Y\to X$ that are both onto, but no bijection between $X$ and $Y$.

Added: If there is a one-to-one map $f:X\to Y$, there is always a map $g$ from $Y$ onto $X$. Let $x_0$ be any element of $X$. For each $y\in Y$ let $g(y)=f^{-1}(y)$ if $y\in f[X]$, and otherwise let $g(y)=x_0$; you should have no trouble verifying that $g$ is well-defined and onto.

If $g:Y\to X$ is onto, you need the axiom of choice to ensure that there is a one-to-one $f:X\to Y$. For each $x\in Y$ let $C_y=\{y\in Y:g(y)=x\}$, and let $\mathscr{C}=\{C_x:x\in X\}$. Then $\mathscr{C}$ is a non-empty collection of non-empty sets, so there is a function $\varphi$ with domain $\mathscr{C}$ such that $\varphi(C_x)\in C_x$ for each $x\in X$. Now use $\varphi$ to define a one-to-one function $f:X\to Y$.

-
What doez ZF and axiom of choice mean? what approach should I take to prove that this is true? – Akaichan Jan 25 '13 at 17:48
@IvordesGreenleaf: ZF refers to the axioms of Zermelo-Fraenkel set theory; the axiom of choice says that if $\mathscr{C}$ is a non-empty family of non-empty sets, there is a function $f$ defined on $\mathscr{C}$ such that $f(C)\in C$ for each $C\in\mathscr{C}$: $f$ selects a member $f(C)$ of each set $C$ in the collection $\mathscr{C}$. Are you supposed to be proving the if and only if result in your question? – Brian M. Scott Jan 25 '13 at 17:58
Yes, I'm trying to do this in order to lead to another part but was stuck here – Akaichan Jan 25 '13 at 17:59
@IvordesGreenleaf: Okay; I’ve added a sketch of both halves of the argument, though I’ve left some work still for you to do. – Brian M. Scott Jan 25 '13 at 18:05