1
$\begingroup$

If $X$ is a finite set and $Y$ an infinite one, I'm trying to prove there is a injective function $f:X\to Y$.

My solution: Let $X=\{x_1,\ldots,x_n\}$, for each $x_i$ choose $y_1,\ldots,y_n$ such that $f(x_1)=y_1,\ldots,f(x_n)=y_n$.

I would like to know if I need theorem of choice to choose these $y_i$.

Thanks

$\endgroup$
  • $\begingroup$ You don't. There are only finitely many xi's. $\endgroup$ – user207710 Feb 4 '15 at 9:45
  • $\begingroup$ Your question isn't properly stated. It should be: for each xi, choose yi such that yi = f(xi). $\endgroup$ – user207710 Feb 4 '15 at 9:46
  • $\begingroup$ @AhmedHussein what's the difference? $\endgroup$ – user42912 Feb 4 '15 at 9:54
  • $\begingroup$ @user42912: Can't you see? Read your own answer again. It says, for each $x_i$ choose $y_1,...,y_n$... $\endgroup$ – TonyK Feb 4 '15 at 10:26
  • $\begingroup$ The difference is that "for each xi, choose y1, y2, ..., yn such that etc." Means that for x1, you are assigning y1 to x1, y2 to x2, ..., yn to xn; then for x2, you are assigning y1 to x1, y2 to x2, ..., yn to xn, and so forth. What you meant was: for each xi in {x1,x2,...,xn}, choose some element y = yi from Y such that yi = f(xi). Or, for x1,x2,...,xn, choose y1,y2,...,yn such that y1 = f(x1), y2 = f(x2), etc. $\endgroup$ – user207710 Feb 4 '15 at 10:30
1
$\begingroup$

No you don't. $Y$ being infinite it is non empty and therefore there is one element in $Y$ say $x_1$. $Y-\{x_1\}$ is not empty otherwise $Y$ would be finite so we can pick $x_2$ etc. You notice that this could work as well if $X$ was countable! So the axiom of choice is not needed either. As a rule of thumb in most cases we only need it for uncountable matters

$\endgroup$
  • $\begingroup$ I was worried about $Y$, because we have to choose elements of $Y$ and $Y$ is infinite. $\endgroup$ – user42912 Feb 4 '15 at 9:56
  • 1
    $\begingroup$ Whenever we talk about injection worry about the domain and when it is surjection worry about the image $\endgroup$ – marwalix Feb 4 '15 at 9:59
1
$\begingroup$

The axiom of choice is not needed.

You are using finite choice, which is provable in $\sf ZF$. The proof is by induction here, and each step requires choosing one element.

Note that the induction does not prove that there is a countably infinite subset. Just finite subsets of arbitrary size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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