2
$\begingroup$

QUEST:

For any sets $X$ and $Y$, there exists an injective function $f:X\rightarrow Y$ if and only if there exists a surjective function $g:Y\rightarrow X$.


QUESTION$_1$:

How do you people approach this problem. I mean, what is running through your brain when you look at each of the above statements?


KNOWN:

$\dagger\hspace{.5cm}$If $f : X \rightarrow Y$ is injective, then there exists a function $g: Y \rightarrow X$ such that $g \circ f = 1_X$.

$\dagger\hspace{.5cm}$If $f:X \rightarrow Y$ is surjective, then there must exist a function $g:Y \rightarrow X$ such that $f \circ g = 1_Y$.


THOUGHTS:

http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theorem


ATTEMPT$_{Q1}$: $\leftarrow$ This attempt is wrong, just so you know...

Since $f$ is an injection it is a bijection onto its image, and so there exists an inverse $h:f(X)\rightarrow X$. Now, let $x$ be an arbitrary element in $X$, and define $g:Y\rightarrow X$ by $$g(y) = \begin{cases} h(y), & \text{if }y\in f(X) \\ x, & \text{otherwise } \end{cases},$$ so $g$ is a bijection and therefore a surjection.


QUESTION$_2$:

Let $\precsim$ be a relation defined by $$X\precsim Y~\iff~\exists~f:X\rightarrow Y~(1-1).$$

Let $\succsim$ be a relation defined by $$X\succsim Y~\iff~\exists~f:X\rightarrow Y~(\text{onto}).$$

How are $\precsim$ and $\succsim$ related in the context of QUEST's proof?


ATTEMPT$_{Q2}$: $\leftarrow$ Maybe somebody will check this...

By the Cantor–Bernstein–Schroeder theorem, if $X\precsim Y$ and $Y\succsim X$, then $X\cong Y$, so we can define a relation $\leq$ on cardinalities as follows: $$\lvert X \rvert \leq \lvert Y \rvert~~~\text{if}~~~X\precsim Y,$$ namely $\exists~f~\text{s.t.}~f:X\rightarrow Y~(1-1)$, which suggests that $\leq$ is anti-symmetric since $$\lvert X \rvert \leq \lvert Y \rvert~\text{and}~\lvert Y \rvert \leq \lvert X \rvert \iff X\precsim Y~\text{and}~Y\precsim X,$$ if and only if there exists injective maps $f:X\rightarrow Y$ and $g:Y\rightarrow X$, so there exists also an injective map $h:X\rightarrow Y$, by C-B-S, and so $X\cong Y\iff \lvert X \rvert = \lvert Y \rvert$, where $\lvert * \rvert$ denotes cardinality.

$\endgroup$
  • 1
    $\begingroup$ In my head I just think size. It has to be true. $\endgroup$ – Git Gud Jul 14 '13 at 21:43
  • $\begingroup$ The words left-inverse and right-inverse dance through my mind until they collide with $f$ and $g$. And then in the debris I'm reminded of the Axiom of Choice. Btw, what do you mean with "each of the above" statements when I count only one statement above? $\endgroup$ – Hagen von Eitzen Jul 14 '13 at 21:44
  • 3
    $\begingroup$ "Warning: Axiom of Choice may be necessary" (this is just what runs through my head looking at this problem, I don't know if it actually is or not) $\endgroup$ – Zev Chonoles Jul 14 '13 at 21:45
  • 7
    $\begingroup$ "if": choice function for $g^{-1}(\{x\})$, "only if" - well, $X = \varnothing \neq Y$ provides a counterexample. But if we exclude empty sets, choose any $x \in X$ and extend $f^{-1}$ to all of $Y$. $\endgroup$ – Daniel Fischer Jul 14 '13 at 21:46
  • $\begingroup$ Sort of a collection of cones with apexes the elements of $X$ and bases are subsets in $Y$ covering $Y$. $\endgroup$ – Stefan Hamcke Jul 14 '13 at 21:47
2
$\begingroup$

You already have all the ingredients in your question.

If there is an injective function $f\colon X\to Y$, then your fact 1 gives you a function $g\colon Y\to X$; is it what you're looking for?

If there is a surjective function $g\colon Y\to X$, then your fact 2 gives you a function $f\colon X\to Y$ such that $g\circ f=1_X$ (just reverse the role of $f$ and $g$ and of $X$ and $Y$); is it what you're looking for?


Complete solution. I accept your two facts as known, but stated in a slightly different way:

  1. Every injective function has a left inverse
  2. Every surjective function has a right inverse

Suppose there exists an injective function $f\colon X\to Y$. By fact 1, $f$ has a left inverse, that is, a function $g\colon Y\to X$ such that $g\circ f=1_X$. I claim that the function $g$ is surjective; indeed, if $x\in X$, we have $$ x = g\circ f(x) = g(f(x)) = g(y) $$ where $y=f(x)$.

Suppose conversely that there exists a surjective function $g\colon Y\to X$. By fact 2, $g$ has a right inverse, that is, a function $f\colon X\to Y$ such that $g\circ f=1_X$. I claim that the function $f$ is injective; indeed, if $f(x_1)=f(x_2)$, then $$ x_1=g\circ f(x_1) = g(f(x_1))=g(f(x_2))=g\circ f(x_2)=x_2. $$

$\endgroup$
  • $\begingroup$ What do you mean reverse the role? $\endgroup$ – Trancot Jul 14 '13 at 22:46
  • $\begingroup$ @BarisaBarukh You can write fact 2 as "if $g\colon Y\to X$ is surjective, then there exists $f\colon X\to Y$ such that $g\circ f=1_X$". Sorry, I had the wrong order in the answer. $\endgroup$ – egreg Jul 14 '13 at 22:49
  • $\begingroup$ I don't see how this all fits together. $\endgroup$ – Trancot Jul 14 '13 at 22:53
  • $\begingroup$ These relations are related by implication, right? (SEE EDIT) $\endgroup$ – Trancot Jul 14 '13 at 23:48
0
$\begingroup$

Am I the only one who sees a mistake here?

Quote: "By the Cantor–Bernstein–Schroeder theorem, if $X\precsim Y$ and $Y\succsim X$, then $X\cong Y$, so we can define a relation $\leq$ on cardinalities as follows:"

That's not the Cantor-Bernstein-Schroeder theorem. This is the CBS theorem: If $X\precsim Y$ and $Y\precsim X$, then $X\cong Y$ where the original poster defined $X\precsim Y$ as there exists an injective function from X to Y.

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