Help with proving Schröder Bernstein theorem

Question

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.

Answer 1

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.

Answer 2

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