Schröder Bernstein Theorem: Proof

Let $A$ and $B$ be two nonempty sets; and let there be, in addition, two one-one functions $f:A\rightarrowtail B$ and $g:B\rightarrowtail A$. We propose to show that $A$ and $B$ are equinumerous i.e., they are in one to one correspondence.

Consider the notation:

$g^{-1}(x),$if$x\in g(B)$

$f^{-1}(g^{-1}(x)),$if$g^{-1}(x)\in f(A)$

$g^{-1}(f^{-1}(g^{-1}(x))),$if$f^{-1}(g^{-1}(x))\in g(B)$

$\mathrm{\dots }..$

Define, for each $x\in A$, the order of it, denoted by $\circ (x)$, to be the number of such preimage(s) which exist. In a similer way, we’d be able to define the order of an element $y\in B$, i.e., by considering the sequence $f^{-1}(y),g^{-1}(f^{-1}(y)),\mathrm{\dots }$.

Now define, for each $x\in A$,

$\varphi (x):$$=$$f(x),\circ (x)=\mathrm{\infty }$

$=$$f(x),\circ (x)=2n,\text{ for some }n\in \omega$

$=$$b,\circ (x)=2n+1,i.e.,\exists b\in B:g(b)=x$

Notice that if the order is infinite, $\varphi (x)=f(x)$ is also infinite. Because, otherwise $x$ would have to have a finite order. On the other hand, if $y\in B$ and $\circ (y)$ is infinite, then $f^{-1}(y)$ exists and has an infinite order; call the latter one $x$. This means, $\varphi$ maps the infinite order elements of $A$ bijectively onto the infinite order elements of $B$.

Next, if $\circ (x)=2n$, then the order of $f(x)$ is sheer $2n+1$. Similer to the above para, if for $y\in B$, the order is $2n+1$, as the order is non-zero, $f^{-1}(y)$ exists and it must have order $2n$. To formally show it you need a tedious inductive reasoning!

Last, if $\circ (x)=2n+1$, then the order is $\ge 1$, and so, $g^{-1}(x)$ exists and the order of $g^{-1}(x)$ is sheer $2n$(looking upon $g^{-1}(x)$ as an element of $B$). Conversely, similer to above, if there is an element $y$ of order $2n$ in $B$, take $x=g(y)$ and the order of $x$ is indeed $2n+1$. All that you need to convince a sceptic is a long, tedious, involved induction!!

What we learn from what precedes is that the one-one function $\varphi$ maps the infinite order elements onto infinite order elements, odd order onto odd order, and even order onto even order; a simple set theory reveals that $\varphi$ is a one-one map from $A$ onto $B$. This completes the proof.