The Constructible Hierarchy and Inner Models: Examples and Counterexamples

For a finite set A every subset B is finite. If $B=\{b_1,\dots ,b_k\}$ is nonempty, the formula $x=b_1\vee \cdots \vee x=b_k$ defines it over A using those parameters. The formula $x\mathrm{\ne }x$ defines the empty subset when A is nonempty; the designated clause treats A empty. Hence $\mathrm{Def}(A)=\mathcal{P}(A)$ for finite A.

Starting with empty gives $L_1=\{\mathrm{\varnothing }\}$ and $L_2=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$. The four elements of $L_3$ are $\mathrm{\varnothing }$, $\{\mathrm{\varnothing }\}$, $\{\{\mathrm{\varnothing }\}\}$ and $\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$. Induction gives finiteness at each stage (a set with k elements has subsets encoded by k binary choices) and $L_{n+1}=\mathcal{P}(L_n)=\mathcal{P}(V_n)=V_{n+1}$. The zero stages coincide. Taking the unions over n yields $L_{\omega }=V_{\omega }$.

At L_1 the only element is empty, so it is first. The difference $L_2\setminus L_1$ is $\{\{\mathrm{\varnothing }\}\}$; its only element is placed after the old empty set. Thus the first two elements are exactly as asserted.

Subtracting the two old elements from the four-element L_3 of F2 leaves $u=\{\{\mathrm{\varnothing }\}\}$ and $v=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$. Over L_2, u is defined by $x=\{\mathrm{\varnothing }\}$ using that parameter, while v is defined by $x=x$ without parameters. Their least codes need not be these displayed witnesses. F1 puts u before v exactly when its least code precedes the least code of v, and puts both after the two old elements. The answer beyond the first two therefore retains the specified coding convention.

Encode pairs of naturals by $\pi (a,b)=(a+b)(a+b+1)\mathrm{/}2+b$. For a given s, the values with $a+b=s$ are the consecutive integers from $s(s+1)\mathrm{/}2$ to $s(s+1)\mathrm{/}2+s$, so these disjoint intervals cover omega and pi is a bijection. Number the membership-language symbols by naturals (the variables are $v_i$, and the remaining logical and punctuation symbols form a fixed finite list); encode a finite symbol string by pairing its length with its nested symbol code ending in 0. Restricting this partial decoding to well-formed formulas and pairing each with its finite allowed arity gives a natural-number formula/arity code. Encode a finite tuple of naturals by the same length-and-nested-pair construction, then pair it with the formula/arity code. For each natural k decode a valid formula/tuple pair if possible and output its defined subset; otherwise output empty. Replacement gives a sequence $E:\omega \to \mathrm{Def}(\omega )$, and F1 makes it surjective.

Given any sequence $S:\omega \to \mathcal{P}(\omega )$, Separation forms $D=\{n\in \omega :n\mathrm{\notin }S(n)\}$. For each k, membership of k in D is the opposite of its membership in S(k), so $D\mathrm{\ne }S(k)$. Thus S is not surjective. Applied to E from step 1.1, D is not in Def(omega), although it is a subset of omega. This uses a defining formula in V, not necessarily a definition over the structure $(\omega ,\in )$, so there is no contradiction with the definition of Def.