Past exam of the analytic topology and axiomatic set theory course of the University of Oxford / 2010 / B / 4

For a set $A$, its definable power set consists of the subsets of $A$ definable by a first-order formula over $(A,\in )$ using finitely many parameters from $A$. The quantifiers range over $A$; this is generally much smaller than its full power set.

The constructible universe is defined by transfinite recursion:The last union denotes a definable proper class, not a set-sized union over a set of all ordinals. At a successor stage, only definitions over the previously constructed stage are permitted.

Use transfinite induction. The assertion is immediate at stage zero, and at a limit stage it follows by taking the increasing union of the earlier stages.

Assume $L_{\alpha }\cap \mathrm{On}=\alpha$. Any ordinal $\gamma \in L_{\alpha +1}$ is a subset of $L_{\alpha }$, since members of the definable power set are such subsets. Every element of $\gamma$ is an ordinal, sowhich implies $\gamma \le \alpha$. This gives the upper bound on the ordinals appearing at the successor stage.

For the reverse inclusion, the smaller ordinals are already in $L_{\alpha }$ and hence in $L_{\alpha +1}$. The remaining ordinal $\alpha$ itself is the definable subset $L_{\alpha }\cap \mathrm{On}$. The fact used here is absoluteness of ordinalhood between a transitive set and the universe: ordinalhood has a bounded definition, and bounded formulas are absolute for transitive sets. Thus the formula asserting that a member is an ordinal, interpreted over $L_{\alpha }$, defines exactly $\alpha$. Therefore $\alpha \in \mathrm{Def}(L_{\alpha })=L_{\alpha +1}$.

This provesIn particular each ordinal $\alpha$ is a member of $L_{\alpha +1}$, so $\boxed{\mathrm{On}\subseteq L}$.

The axiom of infinity fails. First prove $L_n=V_n$ for every finite ordinal $n$. The base stage is empty in both hierarchies. If $L_n=V_n$, that stage is a finite set. Every one of its subsets is definable over it with finitely many parameters, by a disjunction of equalities to the selected elements; the empty subset is defined by a false formula. HenceInduction and the limit-stage definitions givethe set of all hereditarily finite sets. Every member of this set is finite externally.

If this transitive structure satisfied the axiom of infinity, it would contain an inductive set $I$: zero belongs to $I$, and whenever $x\in I$, its successor $x\cup \{x\}$ belongs to $I$. These operations are the actual empty set and actual set successor, since they are absolute for this transitive structure and all relevant finite-rank sets lie in it. External induction would then place every finite ordinal in $I$, contradicting the finiteness of $I$.

Every individual finite ordinal does belong to $L_{\omega }$, but the set $\omega$ of all finite ordinals does not. The distinction between containing each finite ordinal and containing one inductive set is precisely the issue.