Past exam of the logic and set theory course of the University of Oxford / 2011 / B / 4

An approximation is a function $s:n+1\to X$ with $s(0)=x_0$ and $s(k+1)=g(s(k))$ for $k<n$. By induction on $n$, there is such a function: start with $\{(0,x_0)\}$ and append the uniquely specified value $g(s(n))$.

Any two approximations agree on their common domain, by induction from their common initial value and the same transition function $g$. The collection $\mathcal{S}$ of all approximations is a set, being a definable subset of $\mathcal{P}(\omega \times X)$. Therefore $f=\bigcup \mathcal{S}$ is a function. Existence of approximations of every finite length gives $\mathrm{dom}(f)=\omega$. Each defining equation appears in a sufficiently long approximation, soThis proves the natural-number recursion theorem without the axiom of choice; no arbitrary sequence of choices was made.

Suppose $h:\omega \hookrightarrow X$ is an injection. Shift its image by definingThe two pieces have disjoint images, so $g$ is injective, but $h(0)$ is omitted. Thus $g$ is not surjective.

Conversely, let $g:X\to X$ be an injection which omits some $a\in X$. The natural-number recursion theorem defines $h(0)=a$, $h(n+1)=g(h(n))$. If $h(m)=h(n)$ with $m<n$, repeated injectivity cancels $m$ iterations and gives $a=g^{n-m}(a)$, putting $a$ in the image of $g$, a contradiction. Hence $h$ is injective. ThereforeChoosing one witness $a$ from a single known nonempty set uses no axiom of choice. This is the Dedekind-infinite characterization.

The Cantor-Schröder-Bernstein theorem states that injections $A\hookrightarrow B$ and $B\hookrightarrow A$ imply a bijection $A\cong B$.

Let $\mathfrak{c}=|\mathbb{R}|$ and $\mathcal{D}=\{S\subseteq \mathbb{R}:S\text{ is dense in }\mathbb{R}\}$. Clearly $|\mathcal{D}|\le 2^{\mathfrak{c}}$. For the reverse bound, let $C$ be the usual Cantor set, of cardinality $\mathfrak{c}$. It is closed with empty interior, so $D=\mathbb{R}\setminus C$ is dense. The mapis injective, because $A=(D\cup A)\cap C$. Applying the Cantor-Schröder-Bernstein theorem givesOne can see $|C|=\mathfrak{c}$ by coding binary sequences as ternary expansions using only digits zero and two, together with the usual $|\{0,1{\}}^{\omega }|=|\mathbb{R}|$. The same fixed $D$ works for all subsets. This is the cardinality of the family of dense subsets of the reals.