Definable power set ($\mathcal{D}(X)$)

The definable power set $\mathcal{D}(X)=\mathrm{Def}(X)$ consists of the subsets of $X$ definable over the first-order structure $(X,\in )$ by a first-order formula with parameters from $X$. Satisfaction for a set structure makes this a definable operation in ZF. Iterating it produces the constructible hierarchy and the relative constructible hierarchy; their unions are the constructible universe and the relative constructible universe.

A useful finite conjunction of closure assertions requires empty set, pairing, set union, set difference, Cartesian products, all finite tuple domains $A^n$, and the following operations on their relations: relative complements, intersections, coordinate projections and pullbacks along finite coordinate maps, together with equality and membership restricted to $A^2$. The arities and maps are quantified objects, so these requirements form finitely many first-order formulas, not an infinite schema. In a transitive set, individual finite tuples exist by pairing and union, making the tuple-domain assertions correct externally. Atomic truth relations, Boolean operations and projection then compute the truth table of each coded first-order formula correctly by finite induction. Thus satisfaction for a set structure and the relation $B=\mathrm{Def}(A)$ are absolute for shared arguments. Every nonzero limit level of the relative constructible hierarchy is closed under these operations, since each result can be defined at finitely many subsequent stages.

The constructible hierarchy is defined byfor limit ordinals $\lambda$. Its union is the constructible universe $L$.

The equality $L\cap V_{\alpha }=L_{\alpha }$ can fail even at $\alpha =\omega +1$. Inside the constructible universe, $L_{\omega }=V_{\omega }$ is countable, so its definable power set $L_{\omega +1}$ is countable. The constructible power set of $\omega$ is uncountable there by the Cantor theorem. A real outside $L_{\omega +1}$ remains a constructible subset of $\omega$, hence belongs to $V_{\omega +1}$. The cardinal comparison must be made inside $L$, since its reals can be externally countable.

For a transitive model $M$ of ZFC and $\alpha \in M\cap \mathrm{Ord}$, the internally computed constructible hierarchy agrees with the ambient level: $L_{\alpha }^M=L_{\alpha }$. Satisfaction for a fixed set structure is computed from the same finite formulas and the same domain in both universes. Transfinite recursion then proves agreement at successors and limits. If $\theta =M\cap \mathrm{Ord}$, it follows that $L_{\theta }\subseteq M$.

If $M$ is a transitive model of ZF, its internally computed $L_{\alpha }$ is the actual $L_{\alpha }$ for each ordinal $\alpha \in M$. At a successor stage use absoluteness of satisfaction for the same set structure, formula codes and parameters; at a limit stage take the union of the already identical earlier stages. Choice is not required.

The constructible universe is the inner model $L={\bigcup }_{\alpha \in \mathrm{Ord}}{L}_{\alpha }$ obtained by iterating the definable power set. It satisfies ZFC and the Generalized continuum hypothesis.

The obstruction to proving the consistency of nonconstructibility by a uniform inner model construction is that, inside a universe satisfying $V=L$, every transitive inner model containing all ordinals has $L$ as its own constructible universe and therefore is the entire ambient universe. The absoluteness of constructible levels proves this by induction over successor definability and limit unions. Thus a construction valid in every model of ZF cannot always produce such an inner model satisfying $V\ne L$, and in particular cannot always produce one violating axiom of choice.

Every set belongs to some level of the constructible hierarchy. The assertion is $\forall x\exists \alpha (x\in L_{\alpha })$, not that each set is definable without parameters. The constructible universe theorem supplies a relative-consistency model of this assertion from ZFC.

To separate a subset of a constructible set by a formula interpreted in the constructible universe, apply the reflection theorem for definable hierarchies to the formula and its subformulas. At a sufficiently large reflecting level containing the parameters, the desired subset is definable and belongs to the next constructible hierarchy level. The reflection proof uses least witness stages and ambient Axiom schema of replacement, so does not presuppose Axiom schema of separation within the constructible universe.

ZFC proves that the constructible universe is an inner model of ZFC and satisfies the Generalized continuum hypothesis. Relativizing to $L$ yields the corresponding relative-consistency implication.

The constructible universe satisfies the diamond principle. Together with antichain sealing by diamond, this supplies a Suslin tree in $L$.

This statement says that the first uncountable ordinal of an inner model $L$ is a countable ordinal in the ambient universe. It can hold together with the Generalized continuum hypothesis: start with constructibility and use a finite-function collapse to countable size on ${\omega }_1^L$. The GCH preservation by a finite-function collapse calculation gives the relative consistency result already from the consistency of ZFC.

Inside the constructible universe, every hereditarily countable set appears in a countable level of the constructible hierarchy. Take a countable elementary substructure of a sufficiently large $L_{\eta }$ containing its transitive closure pointwise. The condensation lemma for the constructible universe identifies the collapse with $L_{\beta }$ for countable $\beta$, and the collapse fixes the original set. Conversely, a countable-indexed level is countable inside the constructible universe.

For $A\in L$, its constructible power set isUnlike the single-stage definable power set $\mathcal{D}(A)$, it includes subsets of $A$ appearing arbitrarily late in the constructible hierarchy.

For a transitive set $X$, the relative constructible universe $L(X)$ is the union of the relative constructible hierarchy, starting at $L_0(X)=X$, applying the definable power set at successors and taking unions at limit ordinals. It is the smallest inner model of ZF containing $X$ and all its members. For an arbitrary set $A$, take the base $X$ to be the transitive closure of $\{A\}$, so that $A\in X$. Axiom of choice need not hold for an arbitrary base; the construction uses initial parameters rather than a predicate relativization.

An inner model $W$ of ZF containing all ambient subsets of $\omega$ computes the same countable ordinals as the ambient universe. Every ambient countably infinite ordinal has a well-order code coded by a subset of $\omega$, hence that code belongs to $W$; finite ordinals are already shared. The Mostowski collapse theorem inside $W$ recovers the actual ordinal and its countability witness. Conversely any countability witness in $W$ remains one outside. If $W$ also contains the full power set of $\omega$ as a set, its Continuum hypothesis would give an ambient bijection from ${\omega }_1$ onto that same power set. Thus an ambient failure of this well-orderable formulation of the Continuum hypothesis is preserved in such an inner model. No internal axiom of choice is required for this argument.

For a transitive set $X$, use $L_0(X)=X$, $L_{\alpha +1}(X)=\mathrm{Def}(L_{\alpha }(X))$ and unions at nonzero limit ordinals. The successor operation is the definable power set. Each level is transitive and the levels increase; moreover $X\in L_1(X)$. Their union is $L(X)$, an inner model of ZF. The initial-set convention differs from a hierarchy using a predicate, or one starting at $X\cup \{X\}$. Axiom of choice need not hold for an arbitrary base without an internally available well-order.

If $\alpha$ is a nonzero limit ordinal and $Y\prec L_{\alpha }(X)$ with $X\cup \{X\}\subseteq Y$, the Mostowski collapse theorem sends $Y$ to $L_{\beta }(X)$ for some nonzero limit $\beta \le \alpha$ and fixes $X$ pointwise. The base is fixed by transitivity and inclusion of all its members. Transfer the relative constructible level recognition formula first by elementarity and then through the collapse isomorphism to identify its image. If $\rho =X\cap \mathrm{Ord}$, ordinal heights are $\rho +\alpha$ and $\rho +\beta$, giving the bound. Having only $X\in Y$ does not guarantee this base-fixing version.

For transitive sets $M,X$ with $X\in M$, a single first-order formula $\Phi (X)$ recognises the nonzero limit levels $L_{\alpha }(X)$. Require finite relation closure for set-theoretic coding, transitivity of $X$, that every element belongs to a coded relative constructible stage, and that every represented stage index has a larger represented index. Correct history codes have downward-closed indices with no maximum, hence form a nonzero limit ordinal $\alpha$. The exhaustion assertion and transitivity then give $M={\bigcup }_{\xi <\alpha }{L}_{\xi }(X)$. Conversely every limit level has the required closure, correct histories cofinal in its index, and exhaustion. This formulation does not assume ZF for an arbitrary input $M$ and does not replace finite coding closure with an unjustified internal constructibility assertion.

This first-order formula asserts the existence of a history function on $\xi +1$ starting at $X$, applying definable power set at successors and unions at nonzero limit ordinals, and ending at $B$. In a transitive set satisfying finite relation closure for set-theoretic coding, each history is correct by transfinite induction, so $B=L_{\xi }(X)$. Relation operations produce restrictions to shorter histories. Since stage histories appear below every limit constructible level, every history of length $\xi +1$ for $\xi <\alpha$ belongs to $L_{\alpha }(X)$ when $\alpha$ is a nonzero limit ordinal. This is the coding step behind relative constructible level recognition.

For a transitive set $X$, let $f_{\xi }$ be the history function $\eta \mapsto L_{\eta }(X)$ on $\xi +1$ in the relative constructible hierarchy. By transfinite induction, $f_{\xi }\in L_{\xi +k}(X)$ for some finite $k$, possibly depending on $\xi$. The base and successor steps follow by forming finite ordered pairs and adjoining the next entry, using $L_{\xi +1}(X)\in L_{\xi +2}(X)$. These operations require finitely many subsequent definable power sets.

At a nonzero limit ordinal $\lambda$, the inductive bounds put every earlier $f_{\eta }$ in $L_{\lambda }(X)$, since $\eta +k<\lambda$. This level satisfies finite relation closure for set-theoretic coding, independently of the availability of history functions. Consequently its coded relative constructible stage predicate computes the endpoints correctly. Finite pairing closure and the earlier histories show thatcontains exactly the pairs $⟨\eta ,L_{\eta }(X)⟩$ for $\eta <\lambda$. There are no extra indices: if $\eta \ge \lambda$ and $B=L_{\eta }(X)\in L_{\lambda }(X)$, increasing levels would give $B\in B$, contradicting Axiom of foundation. Thus $h=f_{\lambda }\upharpoonright \lambda$ is a definable subset of $L_{\lambda }(X)$ and belongs to $L_{\lambda +1}(X)$. Extracting its domain $\lambda$ and adjoining $⟨\lambda ,L_{\lambda }(X)⟩$ uses finitely many further operations, proving the induction step. Every nonzero limit $\alpha$ therefore contains all $f_{\xi }$ with $\xi <\alpha$, as required by relative constructible level recognition.

Assume a transitive model $M$ satisfies $2^{{\aleph }_0}={\aleph }_2$. In $M$, encode a bijection $e:{\omega }_2\to \mathcal{P}(\omega )$ by one set $A\subseteq {\omega }_2$, using a fixed pairing of ${\omega }_2\times \omega$ with ${\omega }_2$. Then $L(A)$ decodes $e$ and contains every real of $M$. The two models consequently have the same ${\omega }_1$, and any bijection between ${\omega }_1$ and the real numbers in $L(A)$ would also be one in $M$. Thus $L(A)\models \neg \mathsf{CH}$.

A condensation sentence is a fixed first-order sentence $\sigma$ such that every transitive set satisfying $\sigma$ is $L_{\lambda }$ for a limit ordinal $\lambda$. It combines a sufficiently strong finite fragment of set theory, the assertion that every set is constructible, and the absence of a largest ordinal.

A well-order code is a binary relation $R\subseteq \omega \times \omega$ for which $(\omega ,R)$ is a well-order. Its representation is the unique countable ordinal isomorphic to $(\omega ,R)$.

A level $L_{\lambda }$ is a coding level when $\lambda$ is a limit ordinal, the representation of every well-order code in $L_{\lambda }$ is below $\lambda$, and every ordinal below $\lambda$ has a well-order code in $L_{\lambda }$.

If $X$ is an elementary substructure of a sufficiently large level $L_{\theta }$, then the transitive collapse of $X$ is a level $L_{\beta }$. In particular, a countable $X$ collapses to a level indexed by a countable ordinal.