Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
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
1  
@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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.