7
$\begingroup$

I am trying to prove Schröder–Bernstein theorem myself but I am stuck. Here is my try.

Let $f:A \rightarrow B$ and $g:B \rightarrow A$ be injective functions for sets $A$ and $B$. Define $h: A \rightarrow B$ as follows:

$$ h\left(x\right) = \begin{cases} f(x) & \nexists b : g(b)=x \\ g^{-1}(x) & \text{otherwise} \end{cases} $$

$h$ is a well defined function because $g$ is injective and it is onto as well.

I am stuck at this point because $h$ can be surjective. However for each $x \in B$, there can be at most $2$ distinct elements of $A$ which map to $x$. I think this observation can be used to make use of an argument similar to Hilbert's paradox but I am not able to come up with it.

I don't need a complete solution, a hint in the right direction would be much appreciated.

$\endgroup$
3
  • 4
    $\begingroup$ Please explain the downvote so that I can improve the question. $\endgroup$ – John Dec 18 '17 at 20:13
  • $\begingroup$ The proof is slightly more complicated than that, I'm afraid. $\endgroup$ – Asaf Karagila Dec 18 '17 at 20:15
  • $\begingroup$ "Define $h:A\to B$ as follows: $g(x)=$" Is there a typo there? Is $g(x)$ supposed to be $h(x)$? $\endgroup$ – bof Dec 18 '17 at 22:36
3
$\begingroup$

Good try but it won't quite work. For $a\in A$ let $a\in E$ if the sequence $h^{-1}(a),\; g^{-1}h^{-1}(a),\; h^{-1}g^{-1}h^{-1}(a),$... is either endless or must stop after an even number of terms, and $a\in O$ if the sequence must stop after an odd number of terms (including possibly just one term).

Let $f(a)=h(a)$ if $a\in O$ and $f(a)=g^{-1}(a)$ if $a\in E.$ Observe that $a\in E$ iff $h(g(a))\in E.$ Use this to show that $f:A\to B$ is a bijection.

$\endgroup$
2
  • $\begingroup$ Hi @Daniel, please check my reasoning! Let $SE(a)$ be the sequence $(a,h^{-1}(a),g^{-1}h^{-1}(a),h^{-1}g^{-1}h^{-1}(a),...) \implies SE(h(g(a)))=(h(g(a)), g(a),a,...) \implies card(SE(h(g(a))))=card(SE(a))+2$. Thus $a\in E \iff h(g(a))\in E$. $\endgroup$ – LE Anh Dung Apr 19 '18 at 13:10
  • $\begingroup$ @DungLe. Yes. Correct. Use this to show that if $a\in E$ and $a'\in O $ then $f(a)\ne f(a').$ $\endgroup$ – DanielWainfleet Apr 19 '18 at 21:54
2
$\begingroup$

I think you have an excellent intuition that Hilbert's infinite hotel may help here.

Really you should try to repeatedly map $A$ into $B$ and back, using $f$ and $g$. What you get inside $A$ is the sequence of sets $A\supset g(B)\supset g(f(A)) \supset g(f(g(B)) \supset g(f(g(f(A))) \supset \cdots$. Now, look at the consecutive differences: $A\setminus g(B)$, $g(B)\setminus g(f(A))$, $g(f(A))\setminus g(f(g(B)))$ etc. If you could just map the 'odd' ones into the 'next odd' one, and leave the 'even' ones intact (and a potential intersection of all of the sets above intact), that would give you a bijection of $A$ with $g(B$) and hence a bijection of $A$ with $B$.

And this can be done by the mapping $g\circ f$.

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