Past exam of the logic and set theory course of the University of Oxford / 2009 / B / 5

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 a direct proof, avoiding any appeal to a fixed-point theorem. Let $A_0=A\setminus g(B)$, $A_{n+1}=g(f(A_n))$, and $C={\bigcup }_{n<\omega }{A}_n$. DefineThe second case is defined because $A\setminus C\subseteq g(B)$. On $C$, $f$ is a bijection onto $f(C)$. For $b\in B$, injectivity of $g$ and the construction of $C$ give $g(b)\in C$ if and only if $b\in f(C)$: $g(b)$ cannot be in $A_0$, so membership in $C$ means membership in some $g(f(A_n))$. Hence $g^{-1}$ bijects $A\setminus C$ onto $B\setminus f(C)$. The two pieces have disjoint domains and images and together cover $A,B$, proving $h$ bijective. This proof itself uses no choice.

Write $\mathfrak{c}=|\mathbb{R}|=2^{{\aleph }_0}$. We use the standard infinite-cardinal identities $\kappa \cdot {\aleph }_0=\kappa$, ${\kappa }^n=\kappa$ for positive finite $n$ and infinite $\kappa$, and $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \cdot \mu }$, under the permitted axiom of choice. The map $z\mapsto (\mathrm{Re}z,\mathrm{Im}z)$ bijects $\mathbb{C}$ with ${\mathbb{R}}^2$. Therefore

For an infinite cardinal $\kappa$, multiplication by a nonzero countable cardinal does not change it. Since $|\mathbb{R}|=\mathfrak{c}\ge {\aleph }_0$,There is also an immediate lower bound from $r\mapsto (r,0)$; the standard product identity supplies the matching upper bound. The discreteness of the second coordinate does not create a new cardinal beyond the continuum.

The notation ${}^{\mathbb{R}}\mathbb{R}$ means all functions from the real numbers to themselves, with no continuity restriction. Its cardinal isThe exponent law follows by viewing a function to a function set as one function on a Cartesian product. Cantor's theorem gives $2^{\mathfrak{c}}>\mathfrak{c}$, so this is strictly larger than the other continuum-sized examples here. Characteristic functions of subsets of $\mathbb{R}$ already supply the lower bound $2^{\mathfrak{c}}$.

Every finitely supported sequence vanishes from some index onward, since a finite subset of the natural numbers has a greatest element. Thus the set is a union over $n<\omega$ of sequences determined by their first $n$ real entries, with zeros afterwards. Each nontrivial piece has cardinal ${\mathfrak{c}}^n=\mathfrak{c}$, so the union has cardinal at most ${\aleph }_0\cdot \mathfrak{c}=\mathfrak{c}$.

Conversely $r\mapsto (r,0,0,\dots )$ is an injection from $\mathbb{R}$. Cantor-Schröder-Bernstein therefore givesNo choice of an arbitrary infinite support is involved; it is the finite support that makes a countable union of finite-dimensional parameter spaces enough.

The common amplitude $a>0$ is uniquely determined by any entry's absolute value. After choosing it, each entry independently has sign $+1$ or $-1$. Thus the correspondenceis a bijection from $(0,\infty )\times \{-1,1{\}}^{\mathbb{N}}$ onto the set. The positive reals have cardinal $\mathfrak{c}$, and binary sign sequences have cardinal $2^{{\aleph }_0}=\mathfrak{c}$. HenceHere “independently” refers to unconstrained deterministic choices of coordinates, not probabilistic independence; no probability distribution is being specified.

The complex plane has a countable basis of disks with positive rational radii and centres with rational real and imaginary coordinates. Each open set is the union of the basic disks it contains, so it is determined by a subset of this countable basis. Therefore the number of open sets is at most $2^{{\aleph }_0}=\mathfrak{c}$.

For the reverse inequality, the distinct disks $\{z:|z|<r\}$ for $r>0$ give $\mathfrak{c}$ different open sets. ThusThe countable-basis restriction is decisive: there are $2^{\mathfrak{c}}$ arbitrary subsets of the plane, but only continuum many open ones.

For the cardinality of total orders on a countably infinite set, a total order on $\mathbb{N}$ is a subset of $\mathbb{N}\times \mathbb{N}$, so there are at most $2^{{\aleph }_0}=\mathfrak{c}$ such orders. To obtain the lower bound, associate to every binary sequence $(b_n)$ an order by placing the two-element blocks $\{2n,2n+1\}$ in increasing order of $n$. Inside block $n$, use $2n<2n+1$ when $b_n=0$ and reverse them when $b_n=1$.

This is a total order for every sequence. Distinct sequences differ on the comparison of some adjacent pair and therefore produce distinct relations. Thus binary sequences inject into the order set, provingThe construction counts distinct orders on the labelled set, even though the resulting order types are all isomorphic to the usual natural-number order.