Axiom of regularity and constructible sets

Question

I am studying the book "Set Theory and the Continuum Hypothesis" by Paul J. Cohen and in the Chapter III he proves a theorem which says:

If $A$ is any axiom of $ZF$, then $A_L$ is provable in $ZF$.

(Explaining the notation: Here $L$ denote the "classe" of constructible sets, and $A_L$ is relativization the Axiom to $L$. The Axiom means intuitively that the constructible sets are a model for ZF.)

For that prove Cohen just showed that a constructible set satisfy each axiom of $ZF$, but the Axiom Regularity he left as exercise. How we can prove the Axiom of Regularity for constructible sets?

Answer 1

Regularity has the form "$\forall x\exists y\theta(x,y)$" for a particular formula $\theta$ (as do most of the ZF axioms). The easiest way to show that such a statement $\alpha$ which holds in a structure $M$ also holds in a substructure $N\subseteq M$ is to "push down to $N$" directly:

• Suppose $u\in N$; we want to find some $v\in N$ such that $N\models\theta(u,v)$.

• Since $u\in N$ and $N\subseteq M$, we know $u\in M$; since $M\models\forall x\exists y\theta(x,y)$ there is some $v\in M$ such that $M\models\theta(u,v)$.

• Now we'd be really happy if we could conclude two things:

  • $v$ is also in $N$ (a priori all we know right now is $v\in M$).

  • $N\models\theta(u,v)$ as well (a priori all we know right now is $M\models\theta(u,,v)$).

Neither of those last two sub-bulletpoints is true in general ... but in the specific case of regularity, they do hold (the key point for the first being that $L$ is transitive, and the key point for the second being that all the quantifiers inside $\theta$ are bounded).

---

A technical coda:

Incidentally, these ideas will come back with a vengeance when we start talking about absoluteness - under what general conditions can we "transfer" a property of $V$ to $L$ or between more general inner models (= transitive proper classes satisfying ZF)? For example:

• ZF proves "every well-ordering is isomorphic to an ordinal." This means that if $M$ is any inner model (say $M=L$) then $M$ is "correct about well-orderedness:" if $R$ is a linear order in $M$ and $M\models$ "$R$ is a well-ordering" then $R$ is in fact a well-ordering. This is Mostowski absoluteness.

• A special case of Mostowski absoluteness is the absoluteness between inner models of $\Pi^1_1$ statements. (This is important enough that it's also often called "Mostowski absoluteness.") We can surprisingly strengthen this special case through a clever application of (the general version of) Mostowski absoluteness: $\Pi^1_2$ sentences are absolute between inner models. This is Shoenfield absoluteness, and is unfortunately too complicated to prove here.

• It turns out that we can't push beyond $\Pi^1_2$ in ZF alone: the sentence "Every real is constructible" is $\Pi^1_3$ and not necessarily absolute since $ZF\not\vdash V=L$. However, additional set-theoretic axioms do yield this and further strengthenings by generalizing the proof of Shoenfield absoluteness.

Answer 2

$L$ is transitive and $\forall x,y \in L\,(x \cap y\in L).$ So $\forall x\in L\, \forall y\, (y\in x \iff (y\in L\land y\in x)\iff ((y\in L\land (y\in x)^L)\,))$ and also $\forall x,y \in L\, (x\cap y= (x\cap y)^L).$

For all $z\in L$ we have $z\ne \emptyset \iff (z\ne \emptyset)^L.$

If $L$ did not satisfy Regularity (a.k.a. Foundation) we would have $$(\exists x\,(x\ne \emptyset \land \forall y \,(y\in x \implies y\cap x\ne \emptyset)\,))^L\iff$$ $$ \iff \exists x\in L\,((x\ne \emptyset)^L \land \forall y\in L\,( (y\in x)^L\implies ((y\cap x\ne \emptyset)^L\,))) \iff$$ $$ \iff \exists x\in L\, (x\ne \emptyset \land \forall y\, (\,(y\in L\land y\in x)\implies (y\cap x \ne \emptyset)\,)) \iff$$ $$ \iff \exists x\in L\,(x\ne \emptyset \land \forall y\, (y\in x\implies y\cap x \ne \emptyset)\,) \implies$$ $$ \implies \exists x\, (x\ne \emptyset \land \forall y\, (y\in x\implies y\cap x\ne \emptyset))$$ which violates Regularity in $V$ (the universe).