# Difference between revisions of "Schroeder-Bernstein Theorem"

BakedPotatoe (talk | contribs) m |
Hashtagmath (talk | contribs) (→Proof) |
||

Line 45: | Line 45: | ||

bijective, as desired. <math>\blacksquare</math> | bijective, as desired. <math>\blacksquare</math> | ||

+ | ==See Also== | ||

[[Category:Set theory]] | [[Category:Set theory]] | ||

+ | [[Category:Theorems]] |

## Revision as of 12:21, 30 May 2019

The **Schroeder-Bernstein Theorem** (sometimes called the **Cantor-Schroeder-Bernstein Theorem**) is a result from set theory, named for Ernst Schröder and Felix Bernstein. Informally, it implies that if two cardinalities are both less than or equal to each other, then they are equal.

More specifically, the theorem states that if and are sets, and there are injections and , then there is a bijection .

The proof of the theorem does not depend on the axiom of choice, but only on the classical Zermelo-Fraenkel axioms.

## Proof

We call an element of *lonely* if there is no element
such that . We say that an element of is a *descendent*
of an element of if there is a natural number (possibly zero)
such that .

We define the function as follows: Note that if is the descendent of a lonely point, then for some ; since is injective, the element is well defined. Thus our function is well defined. We claim that it is a bijection from to .

We first prove that is surjective. Indeed, if is the descendent of a lonely point, then ; and if is not the descendent of a lonely point, then is not lonely, so there is some such that ; by our definition, then, . Thus is surjective.

Next, we prove that is injective. We first note that for any , the point is a descendent of a lonely point if and only if is a descendent of a lonely point. Now suppose that we have two elements such that . We consider two cases.

If is the descendent of a lonely point, then so is . Then . Since is a well defined function, it follows that .

On the other hand, if is not a descendent of a lonely point, then neither is . It follows that . Since is injective, .

Thus is injective. Since is surjective and injective, it is bijective, as desired.