Then, for every a ∈ A define
If a is not in C, then, in particular, a is not in C0. Hence a ∈ g[B] by the definition of C0. Since g is injective, its preimage g –1(a) is therefore well defined.
It remains to check the following properties of the map h : A → B to verify that it is the desired bijection:
Note that the above definition of h is nonconstructive, in the sense that there exists no general method to decide in a finite number of steps, for any given sets A and B and injections f and g, whether an element a of A does not lie in C. For special sets and maps this might, of course, be possible.
The definition of h can be visualized with the following diagram.
Displayed are parts of the (disjoint) sets A and B together with parts of the mappings f and g. If the set A ∪ B, together with the two maps, is interpreted as a directed graph, then this bipartite graph has several connected components.
These can be divided into four types: paths extending infinitely to both directions, finite cycles of even length, infinite paths starting in the set A, and infinite paths starting in the set B (the path passing through the element a in the diagram is infinite in both directions, so the diagram contains one path of every type). In general, it is not possible to decide in a finite number of steps which type of path a given element of A or B belongs to.
The set C defined above contains precisely the elements of A which are part of an infinite path starting in A. The map h is then defined in such a way that for every path it yields a bijection that maps each element of A in the path to an element of B directly before or after it in the path. For the path that is infinite in both directions, and for the finite cycles, we choose to map every element to its predecessor in the path.
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 alternatively in A and B, by repeatedly applying and to go right and and to go left (where defined).
For any particular a, this sequence may terminate to the left or not, at a point where or is not defined.
Call such a sequence (and all its elements) 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.
By the fact that and are injective functions, each a in A and b in B is in exactly one such sequence to within identity, (as if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by definition).
By the above observation, the sequences form a partition of the whole 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.
For an A-stopper, the function is a bijection between its elements in A and its elements in B.
For a B-stopper, the function is a bijection between its elements in B and its elements in A.
For a doubly infinite sequence or a cyclic sequence, either or will do.
An earlier proof by Cantor relied, in effect, on the axiom of choice by inferring the result as a corollary of the well-ordering theorem. The argument given above shows that the result can be proved without using the axiom of choice.
The theorem is also known as the Schroeder-Bernstein theorem, but the trend has been to add Cantor's name, thus crediting him for the original version. It is also called the Cantor-Bernstein theorem.