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

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.

A transitive set $X$ is one for which every member is a subset: $\forall y\in X(y\subseteq X)$, equivalently $\bigcup X\subseteq X$. If $x\in y\in X$, the subset condition puts $x\in X$. Conversely, if this membership implication always holds, every element of each $y\in X$ belongs to $X$, so $y\subseteq X$. Thus

Let $a\in b\in \mathcal{P}(X)$. Since $b\subseteq X$, we have $a\in X$. Transitivity of $X$ gives $a\subseteq X$, so $a\in \mathcal{P}(X)$. This is exactly the membership criterion for a transitive set, proving the power set of a transitive set is transitive.

A well-order is a strict total order in which every nonempty subset has a least element. A Von Neumann ordinal is a transitive set well-ordered by membership. Thus its predecessors are precisely its members, and its ordering is the restriction of $\in$.

Put $\alpha =\bigcup X$. Every element of $\alpha$ belongs to some ordinal in $X$ and is itself an ordinal. If $u\in v\in \alpha$, choose $\beta \in X$ with $v\in \beta$; transitivity of $\beta$ gives $u\in \beta \subseteq \alpha$. Thus $\alpha$ is a transitive set of ordinals.

Any two ordinals are comparable by membership or equality, so membership strictly totally orders $\alpha$. Every nonempty subset $A\subseteq \alpha$ has an $\in$-minimal element by the Axiom of foundation, and totality makes it the least element. Hence $\bigcup X$ is an ordinal, including $\bigcup \varnothing =0$.

Use transfinite induction. For any $\beta <\alpha$, the induction hypothesis and strict increase give $\beta \le F(\beta )<F(\alpha )$. Thus every $\beta <\alpha$ belongs to $F(\alpha )$, so $\alpha \subseteq F(\alpha )$, i.e.This includes $\alpha =0$ and does not yet use continuity of the normal function on an ordinal.

By the natural-number recursion theorem, let ${\alpha }_0=0$ and ${\alpha }_{n+1}=F({\alpha }_n)$. These ordinals form a nondecreasing sequence by the preceding bound. If ${\alpha }_{n+1}={\alpha }_n$ for some $n$, it is already a fixed point.

Otherwise the sequence is strictly increasing. Its supremum $\lambda ={\bigcup }_{n<\omega }{\alpha }_n$ is a limit ordinal, and the sequence is cofinal in it. Continuity and monotonicity giveFor the middle equality, every $\beta <\lambda$ is below some ${\alpha }_n$, while every ${\alpha }_n<\lambda$. Therefore $F$ has a fixed point. The sequence is a set by Axiom schema of replacement, since $F$ is a definable set-theoretic class function.

Repeat the preceding construction starting at ${\alpha }_0=\gamma +1$, for any given ordinal $\gamma$. A stabilized value or the strictly increasing sequence's supremum is a fixed point at least $\gamma +1$. Thus fixed points occur above every ordinal.

If the fixed points formed a set $S$, their union would be an ordinal bounding them all. Applying the construction above that bound contradicts it. HenceThis is the unboundedness part of the fixed point of a normal ordinal function theorem.

The four principles are:

In the last assertion the upper bound belongs to the partially ordered set; it need not belong to the chain.

Assume the well-ordering theorem. Every set with a chosen well-order has an order isomorphism to a unique ordinal. Any two ordinals are comparable, and the smaller embeds into the larger as an initial segment. Transporting that embedding back to the original sets proves the cardinal comparability principle.

Conversely, assume the cardinal comparability principle and let $X$ be any set. The Hartogs theorem, provable in ZF, supplies an ordinal $h(X)$ for which no injection $h(X)\hookrightarrow X$ exists. Comparison forces an injection $X\hookrightarrow h(X)$. Pulling back the well-order on its image gives a well-order on $X$. ThereforeThe assumed ordinal facts are that every well-ordered set has an ordinal order type and that any two ordinals are comparable; the other assumed theorem is precisely the stated Hartogs theorem.

For the standard definition of algebraic independence, finite tuples are required to have distinct entries. Let $\mathcal{P}$ be the set of all subsets of $L$ with algebraic independence over $K$, ordered by inclusion. It is nonempty because $\varnothing \in \mathcal{P}$.

If $\mathcal{C}$ is a chain in $\mathcal{P}$, put $U=\bigcup \mathcal{C}$. A finite tuple of distinct elements of $U$ lies in one member of $\mathcal{C}$: choose a member containing each element and take the largest of those finitely many members. A polynomial relation on that tuple would then be a polynomial relation in that member, contradicting its algebraic independence. Thus $U\in \mathcal{P}$ and is an upper bound. For the empty chain, $\varnothing$ is an upper bound. The Zorn's lemma now gives a maximal member $B$, which is a transcendence basis by the specified maximality criterion. To also recover the usual field-theoretic definition, if $a\in L$ were transcendental over $K(B)$, clearing denominators in a polynomial relation would show that $B\cup \{a\}$ still has algebraic independence over $K$, contradicting maximality. Thus $L$ is algebraic over $K(B)$. Hence every field extension has a transcendence basis.

There is a literal issue in the printed definition: it does not require the tuple entries to be distinct. With that wording, any nonempty $X$ fails the test: for $a\in X$, the nonzero polynomial $X_1-X_2$ vanishes on $(a,a)$, in every characteristic. Thus under the literal printed test the family is exactly $\{\varnothing \}$, and $\varnothing$ is its maximal member. The same chain-and-Zorn's lemma argument still proves existence for that literal notion, but it is not the usual transcendence basis notion. The conventional result above uses distinct tuple entries.

Let $\mathcal{O}$ be the set of strict total orders on $\kappa$. Each is a subset of $\kappa \times \kappa$, so the square of an infinite cardinal givesFor the lower bound, use the set $\kappa \times \{0,1\}$ and order the two-element blocks by their first coordinates, using the well-order of $\kappa$. For every $A\subseteq \kappa$, put $(\alpha ,0)$ before $(\alpha ,1)$ exactly when $\alpha \in A$, reversing them otherwise. This defines a strict total order for each $A$, and different subsets give different orders. Transport these orders to $\kappa$ along a fixed bijection $\kappa \times \{0,1\}\cong \kappa$. Thus $2^{\kappa }\le |\mathcal{O}|$, and the Cantor-Schröder-Bernstein theorem givesIf using the customary axiom of choice development of infinite cardinal arithmetic, its use here is precisely to supply $\kappa \times \kappa \cong \kappa$ and $\kappa \times 2\cong \kappa$. The ordering construction makes no further choices. It proves the cardinality of the family of strict total orders. For $\kappa$ itself an initial ordinal, these particular product identities can also be proved in ZF by well-ordering pairs according to their maximum coordinate, so full axiom of choice is stronger than this instance intrinsically requires.