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

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.