Past exam of the logic and set theory course of the University of Oxford / 2008 / B / 7

The Cantor-Schröder-Bernstein theorem states that injections $f:A\to B$ and $g:B\to A$ imply the existence of a bijection $A\to B$. Here is the injection-chain formal proof, so no fixed-point theorem is needed. Defineand setThe second branch is defined because $a\notin C$ implies $a\notin A_0$, hence $a\in g(B)$, and the inverse there is unique by injectivity of $g$. Each branch is injective. A collision between branches would have $f(c)=g^{-1}(a)$ with $c\in C$ and $a\notin C$, implying $a=g(f(c))\in C$, a contradiction. Thus $h$ is injective.

For surjectivity let $b\in B$. If $g(b)\notin C$, then $h(g(b))=b$. If $g(b)\in C$, it is not in $A_0$, so it belongs to some $A_{n+1}=g(f(A_n))$. There is $a\in A_n$ with $g(b)=g(f(a))$; injectivity of $g$ gives $b=f(a)=h(a)$. This proves that $h$ is a bijection and completes the theorem without the axiom of choice.

For the comparison of cardinalities take the power set of $\omega$ as the reference set. Its cardinality is by definitionThe remaining parts give explicit injections or bijections comparing each requested set with this one.

Map $S\subseteq \omega$ to its indicator function $1_S:\omega \to \{0,1\}$. Its inverse maps a binary sequence $u$ to $\{n\in \omega :u(n)=1\}$. These maps are mutually inverse, soHere the left superscript denotes the set of functions from $\omega$ into $2$. It is a space of binary sequences, not an ordinal square.

There is an injection from the power set of $\omega$ into the real numbers given byIf $S$ and $T$ first differ at $k$, the contribution at $k$ has magnitude $2/3^{k+1}$, while the entire later tail has magnitude at mostTheir real values are therefore different. This proves injectivity directly and avoids any ambiguity of numeral expansions.

Conversely, map a real number $x$ to the set $\{q\in \mathbb{Q}:q<x\}$. Distinct real numbers give distinct sets because the rational numbers are dense in the real line. Fixing a bijection between $\omega$ and the countable set $\mathbb{Q}$ turns this into an injection $\mathbb{R}\to \mathcal{P}(\omega )$. Cantor-Schröder-Bernstein theorem now gives

Constant sequences give an injection $\mathbb{R}\to {}^{\omega }\mathbb{R}$. For the opposite bound fix an enumeration $(q_m{)}_{m\in \omega }$ of the rational numbers and encode a sequence $(x_n)$ byDistinct sequences differ at some coordinate $n$; density of the rational numbers then makes their encoded sets differ at a pair $(n,m)$. Thus $E$ is injective. The Cartesian product $\omega \times \omega$ is countable; for example the Cantor pairing functionis a bijection with $\omega$. Consequently $\mathcal{P}(\omega \times \omega )$ is equinumerous with $\mathcal{P}(\omega )$, already equinumerous with $\mathbb{R}$. Apply Cantor-Schröder-Bernstein theorem to obtain

Write $C(\mathbb{R},\mathbb{R})$ for the set of continuous real-valued functions on the real line. Constant functions give an injection of $\mathbb{R}$ into this set. In the other direction, restriction to the rational numbers is injective. Indeed, if continuous functions $f,g$ agree at every rational and $x$ is real, choose rational numbers $q_n\to x$. Continuity givesThus restriction embeds $C(\mathbb{R},\mathbb{R})$ into ${\mathbb{R}}^{\mathbb{Q}}$, which has the same cardinality as the real-sequence space because $\mathbb{Q}$ is countable. The previous part gives the upper bound $2^{{\aleph }_0}$, while constant functions give the matching lower bound. HenceThis computes the cardinality of continuous real functions. All five sets consequently have the same cardinality. The continuity assumption is decisive for restriction to a dense subset to determine a function.