A resource for profoundly gifted middle school students, their parents, and teachers

Cantor-Bernstein Theorem for surjective maps

Dual Cantor-Bernstein Theorem

The Cantor-Bernstein Theorem says: if for two sets A and B there are injective maps A ® B and B ® A, then there exists a bijection between and B. The dual of the theorem is this: if for two sets A and B there are surjective maps A ® B and B ® A, then there exists a bijection between and B.

Assume there exist surjective maps f: A ® B and g: B ® A. Since f is surjective, there exists a set Sb in A for each element b in B so that f maps Sb to b. Then A is a disjoint union of Sb, b Î B. By the Axiom of Choice, we can find a set T Ì A consisting of precisely one element sb from each Sb. Let f': B ® T, where f'(b)= sb. Then f' is an injection from B to A. Similarly, we can find an injection g' from A to B. By the Cantor-Bernstein Theorem, there exists a bijection between A and B. ð

Notice that we used the artifice called Axiom of Choice to prove the dual, whereas such an artifice was not necessary to prove the classical Cantor-Bernstein Theorem. The Axiom of Choice is equivalent to this assertion: Given two sets A and B, there is a surjection from one of the sets to the other. However, we don't know which way the surjection goes, whether from A to B or from B to A. For more on the Axiom of Choice, see Moore [1]. It is an open problem - as of this writing in 2005 - whether the Dual S-B Theorem implies the Axiom of Choice.

The proof given above only shows that a bijection exists but does not provide a way of constructing it unlike in our proof of the Cantor-Bernstein Theorem. The middle school student should note that the dual is trivially valid for finite sets.

[1] Moore, G.H. Zermelo's Axiom of Choice: Its Origins, Development, and Influence, Springer-Verlag, 1982




Send suggestions to webmaster@mathpath.org
Copyright © 2001-
Last updated - January 21, 2005