Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Schroeder-Bernstein Theorem"

(New page with proof)
 
(Undo revision 215873 by Marianasinta (talk))
(Tag: Undo)
 
(9 intermediate revisions by 5 users not shown)
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 if <math>f(a)</math> is the descendent of a lonely point, then <math>f(a)
+
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.
Line 23: Line 23:
  
 
We first prove that <math>h</math> is [[surjective]].  Indeed, if <math>b \in B</math> is the
 
We first prove that <math>h</math> is [[surjective]].  Indeed, if <math>b \in B</math> is the
−
descendent of a lonely point, then <math>h(g(b)) = g</math>; and if <math>b</math> is not
+
descendent of a lonely point, then <math>h(g(b)) = b</math>; and if <math>b</math> is not
 
the descendent of a lonely point, then <math>b</math> is not lonely, so there
 
the descendent of a lonely point, then <math>b</math> is not lonely, so there
 
is some <math>a \in A</math> such that <math>f(a) = b</math>; by our definition, then,
 
is some <math>a \in A</math> such that <math>f(a) = b</math>; by our definition, then,
Line 39: Line 39:
  
 
On the other hand, if <math>f(a_1)</math> is not a descendent of a lonely point,
 
On the other hand, if <math>f(a_1)</math> is not a descendent of a lonely point,
−
then neither is <math>f(a_2)</math>.  It follows that <math>f(a_1) = h(a_1) = h(a_2) = h(a_2)</math>.
+
then neither is <math>f(a_2)</math>.  It follows that <math>f(a_1) = h(a_1) = h(a_2) = f(a_2)</math>.
 
Since <math>f</math> is injective, <math>a_1 = a_2</math>.
 
Since <math>f</math> is injective, <math>a_1 = a_2</math>.
  
Line 45: Line 45:
 
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==
 
[[Category:Set theory]]
 
[[Category:Set theory]]
 +
[[Category:Theorems]]

Latest revision as of 12: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 $A$ and $B$ are sets, and there are injections $f: A \to B$ and $g : B \to A$, then there is a bijection $h : A \to B$.

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 $b$ of $B$ lonely if there is no element $a \in A$ such that $f(a) = b$. We say that an element $b_1$ of $B$ is a descendent of an element $b_0$ of $B$ if there is a natural number $n$ (possibly zero) such that $b_1 = (f \circ g)^n (b_0)$.

We define the function $h: A \to B$ 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}\] Note that $f(a)$ cannot be lonely itself. If $f(a)$ is the descendent of a lonely point, then $f(a) = f \circ g (b)$ for some $b$; since $g$ is injective, the element $g^{-1}(a)$ is well defined. Thus our function $h$ is well defined. We claim that it is a bijection from $A$ to $B$.

We first prove that $h$ is surjective. Indeed, if $b \in B$ is the descendent of a lonely point, then $h(g(b)) = b$; and if $b$ is not the descendent of a lonely point, then $b$ is not lonely, so there is some $a \in A$ such that $f(a) = b$; by our definition, then, $h(a) = b$. Thus $h$ is surjective.

Next, we prove that $h$ is injective. We first note that for any $a \in A$, the point $h(a)$ is a descendent of a lonely point if and only if $f(a)$ is a descendent of a lonely point. Now suppose that we have two elements $a_1, a_2 \in A$ such that $h(a_1) = h(a_2)$. We consider two cases.

If $f(a_1)$ is the descendent of a lonely point, then so is $f(a_2)$. Then $g^{-1}(a_1) = h(a_1) = h(a_2) = g^{-1}(a_2)$. Since $g$ is a well defined function, it follows that $a_1 = a_2$.

On the other hand, if $f(a_1)$ is not a descendent of a lonely point, then neither is $f(a_2)$. It follows that $f(a_1) = h(a_1) = h(a_2) = f(a_2)$. Since $f$ is injective, $a_1 = a_2$.

Thus $h$ is injective. Since $h$ is surjective and injective, it is bijective, as desired. $\blacksquare$


Problems

The Schroeder-Bernstein Theorem can be used to solve many cardinal arithmetic problems. For example, one may wish to show $|S|=\kappa$ for some cardinal $\kappa$. One strategy is to find sets $A,B$ such that $|A|=|B|=\kappa$ with injections from $A$ to $S$ and $S$ to $B$, thus concluding that $|A|=|S|=|B|=\kappa$. More generally, the Schroeder-Bernstein Theorem shows that the relation $|A|\leq|B|$ between cardinals $|A|$ and $|B|$ defined by "there is an injection $f:A\rightarrow B$" is a partial-order on the class of cardinals.

Introductory

Problem 1

Show that $\mathbb{Q}$ is countable.

Problem 2

Let $\kappa$ satisfy $\kappa\cdot\kappa=\kappa$. Show that $\kappa^{\kappa}=2^{\kappa}$.

Intermediate

Problem 1

We say a set of reals $O\subseteq\mathbb{R}$ is open if for all $r\in O$, there is an open interval $I$ satisfying $r\in I\subseteq O$. Show that the following sets are equal in cardinality:

  • $\mathbb{R}$
  • $2^{\aleph_{0}}$
  • $\{O\subset\mathbb{R}\mid O\text{ is open}\}$
  • $\{f:\mathbb{R}\rightarrow\mathbb{R}\mid f\text{ is continuous}\}$

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Schroeder-Bernstein_Theorem&oldid=215925"