Constructible Reals

In this lecture we transfer the results about $L$ to the projective hierarchy. The main idea is to relate sets of reals that are defined by set theoretic formulas to sets defined in second order arithmetic.

The set of constructible reals¶

What is the complexity of the set $\Baire \cap L$ ? In particular, is it in the projective hierarchy? The set of all constructible reals is defined by a $\Sigma_1$ formula over set theory:

\varphi(x_0) \; \equiv \; \exists y \; [y \text{ is an ordinal } \; \wedge \; x_0 \in L_y \; \wedge \; x_0 \text{ is a set of natural numbers } ]

(1)

We would like to replace this formula by an “equivalent” one in the language of second order arithmetic. In particular, we would like to replace the quantifier $\exists y$ by a quantifier over the reals.

The key for doing this is a lemma of the previous section, which implies that every constructible real shows up at a countable level of $L$ . Hence if $\alpha \in L \cap \Baire$ , there exists a countable ${}\xi$ such that $x \in L_\xi$ . Since $|\xi| = |L_\xi|$ , $L_\xi$ is countable, too. Hence we can hope to replace $L_\xi$ by something like “there exists a real that codes a model that looks like $L_\xi$ ”.

The Condensation lemma with the sentence $\varphi_{\VL}$ allows us to do this.

Recall that any real $\alpha \in \Baire$ codes a set theoretic structure

(\omega, E_\alpha) \qquad \text{ where } E_\alpha = \{ \Tup{m,n} \colon \alpha(\Tup{m,n}) = 0 \}.

Unfortunately, the condensation lemma only holds for transitive sets (and $(\omega, E_\alpha)$ may look very different from a transitive set model), so simply requiring $(\omega,E_\beta) \models \varphi_{\VL}$ is not enough. But we know from Theorem 1 (Mostowski collapse) that if $E_\beta$ is well-founded and extensional, we can map it isomorphically to a transitive set $S$ on which we interpret $E_\beta$ as $\in$ . By the condensation lemma, this $S$ must then be an $L_\xi$ .

So, for reals, we can formulate membership in $L$ now as follows:

\begin{align} \alpha \in L \cap \Baire \iff \exists \beta \exists m \: & [E_\beta \text{ is extensional and well-founded} \\ & \; \; \; \wedge \: (\omega,E_\beta) \models \varphi_{\VL} \: \wedge \: \pi_\beta(m) = \alpha ] \end{align}

(2)

where $\pi_\beta$ is the Isomorphism of the Mostowski collapse of $E_\beta$ .

It remains to show that the notions occurring inside the square brackets are definable in second order arithmetic.

Proof (Sketch)

(a) can be established similar to showing that $\Op{Sat}$ -predicate of Theorem 1 is $\Delta_1$ -definable. One does this first for $\Sigma_1$ formulas and then uses induction. Using Gödelization, one carefully defines all syntactical notions using arithmetic formulas. Then, one uses the recursive definition of truth to establish the definability of the satisfaction relation.

Since we work with relations over $\Nat$ now instead of arbitrary sets, it is not that easy anymore to keep quantifiers bounded. But since we are only interested in the complexity of $\models$ for $\Sigma_n$ -formulas, this helps us bound the overall complexity at $\Sigma^0_n$

(b) By analyzing the recursive definition and using the definition of $\Nat$ in $\ZF$ , one first shows that the set

\{ (m,p) \in \Nat\times \Nat \colon \pi_\beta(m) = p \}

(3)

is arithmetic in ${}\beta$ .

Let $\psi(v_0, v_1, v_2)$ be the formula $\Tup{v_0, v_1} \in v_2$ . Then

\begin{align*} & \pi_\beta(m) = \gamma \iff \\ & \qquad \forall p, q \: \left (\gamma(p) = q \: \leftrightarrow \: \exists i,j \: (\pi_\beta(i) = p \wedge \pi_\beta(j)=q \wedge (\omega,E_\beta) \models \psi[i,j,m]) \right ) \end{align*}

(4)

Now apply the previous observation and (a).

Finally, note that

\text{$E_\beta$ is extensional} \iff \forall m,n \: [\forall k (k E_\beta m \; \leftrightarrow \; k E_\beta n) \; \to \; m=n ].

(5)

Hence this is arithmetical. And we have already seen that coding a well-founded relation over $\Nat$ is $\Pi^1_1$ .

Now we know the complexity of all parts of (2) and can put everything together.

In a similar way we can show that the relation $\alpha <_L \beta$ over $(L\cap\Baire)^2$ is $\Sigma^1_2$ (using that $<_L$ is $\Delta_1$ -definable).

If $\VL$ , then the set is actually $\Delta^1_2$ , since in this case

\alpha <_L \beta \iff \alpha \neq \beta \: \wedge \: \neg(\beta <_L \alpha).

(7)

Finally, since $\VL$ implies $\AC$ , we can use Proposition 3 to show the existence of non-measurable sets under $\VL$ .

An uncountable $\Pi^1_1$ set without a perfect subset¶

We now show that under the assumption $\VL$ , the perfect set property fails at level $\Pi^1_1$ .

We start with constructing an example at the $\Sigma^1_2$ level.

Recall that if $\alpha \in \Baire$ codes a well-ordering on $\Nat$ , then

\Norm{\alpha} = \text{ order type of well-ordering coded by ${}\alpha$}.

Proof

Let $A \subseteq \Baire$ be given by

x \in A \iff x \in \WOrd \, \wedge \, \forall y <_L x \, ( \parallel y \parallel \ne \parallel x \parallel).

In other words, $A$ collects the $<_L$ -least code for every ordinal $< \omega_1$ .

Clearly $A$ is uncountable, since it has a representative for every countable ordinal and hence is of cardinality $\omega_1$ .

Moreover, $A$ is $\Sigma^1_2$ : Let $R$ be the $\Sigma^1_2$ -relation of the exercise above. Then

x \in A \iff x \in \WOrd \, \wedge \, \exists z \;(R(z,x) \, \wedge \; \forall n \, ( \Norm {(z)_n} \neq \Norm{x}).

The relation $\Norm{(z)_n} \neq \Norm{x}$ $\Pi^1_1$ , hence $A$ is $\Sigma^1_2$ .

Finally, we see that $A$ does not have an uncountable $\bSigma^1_1$ subset (hence, since all perfect sets are closed, no perfect subset): By $\bSigma^1_1$ -boundedness (Theorem 2), for any $\bSigma^1_1$ subset $X \subseteq A$ the set $\{ \Norm{x} \colon x \in X\}$ is bounded by an ordinal $\gamma < \omega_1$ , hence countable.

It is possible to get this example down to $\Pi^1_1$ using the powerful technique of uniformization.

Proof

Let $A$ be the $\Sigma^1_2$ set from the proof of Proposition 2. $A \subseteq \Baire$ is the projection of a $\Pi^1_1$ set $B \subseteq \Baire \times \Baire$ . If we apply uniformization to $B$ , we obtain a uniformizing set $B^*$ whose projection is still $A$ .

$B^*$ is uncountable, but does not contain a perfect subset: If $P \subset B^*$ were such a subset, then $P$ would be closed, the graph of a function, and uncountable. Therefore, the projection $\exists^{\Baire} \; P$ would be an uncountable $\bSigma^1_1$ subset of $A$ , contradiction.

We finish this section by stating (without proof) the following fact complementing the results above.

Via the contrapositive, this result tells us that if a $\Sigma^1_2$ set of reals has a non-constructible element, it must have a perfect subset. For a proof see Mansfield & Weitkamp (1985). It uses a powerful tree representation of $\PS{2}$ , which we will learn about in the next section.

References¶

Mansfield, R., & Weitkamp, G. (1985). Recursive aspects of descriptive set theory. Oxford University Press.

Constructibility

The Axiom of Constructibility

Constructibility

Shoenfield Absoluteness

The set of constructible reals¶

An uncountable Π11\Pi^1_1Π11​ set without a perfect subset¶

An uncountable $\Pi^1_1$ set without a perfect subset¶