Past exam of the analytic topology and axiomatic set theory course of the University of Oxford / 2008 / B / 8

For a set $M$, let $\mathrm{Def}(M)$ consist of the subsets of $M$ definable over the structure $⟨M,\in ⟩$ by a first-order formula with finitely many parameters from $M$. It is a set contained in $\mathcal{P}(M)$: satisfaction for a set structure and the set of logical formula codes give a uniform set construction of these definable subsets. If $M$ is transitive, every $a\in M$ is one such subset, defined over $M$ by $z\in a$, so $M\subseteq \mathrm{Def}(M)$.

Define the constructible hierarchy by transfinite recursion:Gödel's constructible universe is the definable class in set theoryAt successor stages only subsets definable over the previous stage are admitted, in contrast to the full power-set construction of the cumulative hierarchy. The stages are transitive and increasing, as permitted in the question, and their union contains every ordinal. Finite parameters are essential in the definition of $\mathrm{Def}$.

Fix $a\in L$. In the ambient universe form the setby power set and separation, using definability of $L$. This is the collection which must serve as the power set of $a$ inside $L$; it need not be the entire ambient power set.

For each $y\in S$, let ${\alpha }_y$ be the least ordinal with $y\in L_{{\alpha }_y}$. Ambient replacement is used to collect the ordinals ${\alpha }_y$ into a set. Their supremum, enlarged if necessary to include a stage containing $a$, gives an ordinal $\beta$ such that $a\in L_{\beta }$ and every $y\in S$ belongs to $L_{\beta }$.

Because $L_{\beta }$ is transitive and $a\in L_{\beta }$, the bounded property $y\subseteq a$ for $y\in L_{\beta }$ has its actual meaning when evaluated in that structure: every element of $y$ already lies in $L_{\beta }$, and membership is unchanged. It follows thatThis is a definable subset of $L_{\beta }$ using the parameter $a$, so $S\in \mathrm{Def}(L_{\beta })=L_{\beta +1}\subseteq L$. Every member of $L$ which is a subset of $a$ is in $S$, and every member of $S$ is such a subset. Thereforewhich is exactly the power-set axiom in $⟨L,\in ⟩$. The replacement step is indispensable to this proof: definability over one stage requires first bounding all the constructible subsets by one common stage.

Every constructible set is well-orderable: the constructible hierarchy has a canonical well-order, obtained by ordering the stage of first appearance, logical formula codes and the already ordered finite parameter lists. Its restriction to any set belonging to $L$ is a well-order in $L$ and remains a well-order in the ambient universe. This does not imply that arbitrary ambient sets are well-orderable.

If $a\in L$ is finite, all its subsets are finite combinations of its elements and hence constructible. Moreover the finite set of all those subsets is constructible by the finite set operations available in $L$. Thus the full ambient power set $\mathcal{P}(a)$ belongs to $L$.

Conversely, suppose $a\in L$ is infinite and that its full ambient power set belonged to $L$. A well-order of $a$ supplies an injection $j:\omega \to a$ by taking its first countably many elements. The mapis injective. But $\mathcal{P}(a)\in L$ would make that set well-orderable in the ambient universe, and pulling its well-order back along this injection would well-order $\mathcal{P}(\omega )$. This contradicts the hypothesis. HenceThe superscript emphasizes that the source's final claim concerns the ambient power set. The internal power set ${\mathcal{P}}^L(a)$ exists in $L$ for every $a\in L$ by part (ii), including infinite ones.