# Help with proving Schröder Bernstein theorem

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.

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

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.
• 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$. – LE Anh Dung Apr 19 '18 at 13:10
• @DungLe. Yes. Correct. Use this to show that if $a\in E$ and $a'\in O$ then $f(a)\ne f(a').$ – DanielWainfleet Apr 19 '18 at 21:54
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$.