Difference between revisions of "Schroeder-Bernstein Theorem"
Hashtagmath (talk | contribs) (→Proof) |
Mathcounts46 (talk | contribs) m (Added clarification that $f(a)$ cannot be lonely; which is why f(a) = f(g(b)) for some b.) |
||
| Line 17: | Line 17: | ||
of a lonely point,} \\ | of a lonely point,} \\ | ||
f(a) &\text{otherwise.} \end{cases} </cmath> | f(a) &\text{otherwise.} \end{cases} </cmath> | ||
| − | Note that | + | Note that <math>f(a)</math> cannot be lonely itself. If <math>f(a)</math> is the descendent of a lonely point, then <math>f(a) |
= f \circ g (b)</math> for some <math>b</math>; since <math>g</math> is injective, the element | = f \circ g (b)</math> for some <math>b</math>; since <math>g</math> is injective, the element | ||
<math>g^{-1}(a)</math> is well defined. Thus our function <math>h</math> is well defined. | <math>g^{-1}(a)</math> is well defined. Thus our function <math>h</math> is well defined. | ||
Revision as of 10:51, 14 November 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:
![\[h(a) = \begin{cases} g^{-1}(a), &\text{if } f(a) \text{ is the descendent of a lonely point,} \\ f(a) &\text{otherwise.} \end{cases}\]](http://latex.artofproblemsolving.com/c/8/9/c897e479620b30b568cebbdb113017edefa3135e.png)
Note that 
cannot be lonely itself. 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. 
