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

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.