The following proof is attributed to
Julius König. Assume without loss of generality that
A and
B are
disjoint. For any
a in
A or
b in
B we can form a unique two-sided sequence of elements that are alternately in
A and
B, by repeatedly applying f and g^{-1} to go from
A to
B and g and f^{-1} to go from
B to
A (where defined; the inverses f^{-1} and g^{-1} are understood as
partial functions.) : \cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots For any particular
a, this sequence may terminate to the left or not, at a point where f^{-1} or g^{-1} is not defined. By the fact that f and g are injective functions, each
a in
A and
b in
B is in exactly one such sequence to within identity: if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by the definition of the sequences. Therefore, the sequences form a
partition of the (disjoint) union of
A and
B. Hence it suffices to produce a bijection between the elements of
A and
B in each of the sequences separately, as follows: Call a sequence an
A-stopper if it stops at an element of
A, or a
B-stopper if it stops at an element of
B. Otherwise, call it
doubly infinite if all the elements are distinct or
cyclic if it repeats. See the picture for examples. • For an
A-stopper, the function f is a bijection between its elements in
A and its elements in
B. • For a
B-stopper, the function g is a bijection between its elements in
B and its elements in
A. • For a
doubly infinite sequence or a
cyclic sequence, either f or g will do (g is used in the picture).
Corollary for surjective pair If we assume the axiom of choice, then a pair of surjective functions f and g also implies the existence of a bijection. We construct an injective function from f^{-1} by picking a single element from the inverse image of each point in B. The surjectivity of f guarantees the existence of at least one element in each such inverse image. We do the same to obtain an injective function from g^{-1}. The Schröder-Bernstein theorem then can be applied to the injections
h and
k.
Examples ; Bijective function from [0,1]\to[0,1): :
Note: [0,1) is the half open set from 0 to 1, including the boundary 0 and excluding the boundary 1. : Let f:[0,1]\to[0,1) with f(x)=x/2; and g:[0,1)\to[0,1] with g(x)=x; the two injective functions. : In line with that procedure C_0=\{1\}, \; C_k=\{2^{-k}\}, \; C = \bigcup_{k=0}^\infty C_k = \{1, \tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, ... \} : Then h(x) = \begin{cases} \frac{x}{2} , & \mathrm{for}\ x \in C \\x , & \mathrm{for}\ x \in [0, 1] \smallsetminus C\end{cases} is a bijective function from [0,1]\to[0,1). ; Bijective function from [0,2)\to[0,1)^2: : Let f:[0,2)\to[0,1)^2 with f(x)=(x/2;0); : Then for (x;y)\in[0,1)^2 one can use the expansions x= \sum_{k=1}^\infty a_k\cdot 10^{-k} and y= \sum_{k=1}^\infty b_k\cdot 10^{-k} with a_k, b_k \in \{0, 1, ..., 9\} : and now one can set g(x;y) = \sum_{k=1}^\infty (10\cdot a_k+ b_k)\cdot 10^{-2k} which defines an injective function [0,1)^2 \to [0,2). (Example: g(\tfrac{1}{3}; \tfrac{2}{3}) = 0.363636...= \tfrac{4}{11}) : And therefore a bijective function h can be constructed with the use of f(x) and g^{-1}(x). : In this case C_0=[1,2) is still easy but already C_1=g(f(C_0)) = g(\{ (x;0)|x\in [\tfrac{1}{2}, 1)\,\}) gets quite complicated. : Note: Of course there's a more simple way by using the (already bijective) function definition g_2(x;y) = 2\cdot \sum_{k=1}^\infty (10\cdot a_k+ b_k)\cdot 10^{-2k}. Then C would be the empty set and h(x)=g_2^{-1}(x) for all x. ==History==