Difference between revisions of "Schroeder-Bernstein Theorem"
Mathcounts46 (talk | contribs) m (Added clarification that $f(a)$ cannot be lonely; which is why f(a) = f(g(b)) for some b.) |
(Undo revision 215873 by Marianasinta (talk)) (Tag: Undo) |
||
(5 intermediate revisions by 2 users not shown) | |||
Line 44: | Line 44: | ||
Thus <math>h</math> is injective. Since <math>h</math> is surjective and injective, it is | Thus <math>h</math> is injective. Since <math>h</math> is surjective and injective, it is | ||
bijective, as desired. <math>\blacksquare</math> | bijective, as desired. <math>\blacksquare</math> | ||
+ | |||
+ | |||
+ | ==Problems== | ||
+ | |||
+ | The Schroeder-Bernstein Theorem can be used to solve many cardinal arithmetic problems. For example, one may wish to show <math>|S|=\kappa</math> for some cardinal <math>\kappa</math>. One strategy is to find sets <math>A,B</math> such that <math>|A|=|B|=\kappa</math> with injections from <math>A</math> to <math>S</math> and <math>S</math> to <math>B</math>, thus concluding that <math>|A|=|S|=|B|=\kappa</math>. More generally, the Schroeder-Bernstein Theorem shows that the relation <math>|A|\leq|B|</math> between cardinals <math>|A|</math> and <math>|B|</math> defined by "there is an injection <math>f:A\rightarrow B</math>" is a partial-order on the class of cardinals. | ||
+ | |||
+ | ===Introductory=== | ||
+ | ====Problem 1==== | ||
+ | Show that <math>\mathbb{Q}</math> is countable. | ||
+ | |||
+ | ====Problem 2==== | ||
+ | Let <math>\kappa</math> satisfy <math>\kappa\cdot\kappa=\kappa</math>. Show that <math>\kappa^{\kappa}=2^{\kappa}</math>. | ||
+ | |||
+ | ===Intermediate=== | ||
+ | ====Problem 1==== | ||
+ | We say a set of reals <math>O\subseteq\mathbb{R}</math> is open if for all <math>r\in O</math>, there is an open interval <math>I</math> satisfying <math>r\in I\subseteq O</math>. Show that the following sets are equal in cardinality: | ||
+ | |||
+ | *<math>\mathbb{R}</math> | ||
+ | *<math>2^{\aleph_{0}}</math> | ||
+ | *<math>\{O\subset\mathbb{R}\mid O\text{ is open}\}</math> | ||
+ | *<math>\{f:\mathbb{R}\rightarrow\mathbb{R}\mid f\text{ is continuous}\}</math> | ||
==See Also== | ==See Also== | ||
[[Category:Set theory]] | [[Category:Set theory]] | ||
[[Category:Theorems]] | [[Category:Theorems]] |
Latest revision as of 13:09, 20 February 2024
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.
Contents
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
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.
Problems
The Schroeder-Bernstein Theorem can be used to solve many cardinal arithmetic problems. For example, one may wish to show for some cardinal
. One strategy is to find sets
such that
with injections from
to
and
to
, thus concluding that
. More generally, the Schroeder-Bernstein Theorem shows that the relation
between cardinals
and
defined by "there is an injection
" is a partial-order on the class of cardinals.
Introductory
Problem 1
Show that is countable.
Problem 2
Let satisfy
. Show that
.
Intermediate
Problem 1
We say a set of reals is open if for all
, there is an open interval
satisfying
. Show that the following sets are equal in cardinality: