condensation.md

jupytext	kernelspec
formats text_representation ipynb,md:myst extension format_name format_version jupytext_version .md myst 0.13 1.11.5	display_name language name Python 3 (ipykernel) python python3

Guided Study: The Condensation Lemma

+++

The condensation lemma

There is a finite set $T$ of axioms of $\mathsf{ZF} - \text{Power Set}$ so that if $M$ is a transitive set with $M\models T + \mathsf{VL}$, then $M = L_\lambda$ for some limit ordinal $\lambda$.

+++

Define: $\varphi_{VL} = $ conjunction of the axioms in $T$ and the axiom $\mathsf{VL}$.

+++

First application: $\mathsf{VL}$ implies $\mathsf{GCH}$

+++

Suppose $V=L$. If $\kappa$ is a cardinal and $x \subseteq \kappa$, then $x \in L_{\kappa^+}$.

+++

Guide to proof: Verify each of following steps.

+++

• There exists limit $\lambda > \kappa$ such that $x \in L_\lambda$ and such that $L_\lambda \models \varphi_{VL}$

• Let $X = \kappa \cup {x}$.
  Quick check: What do we know about $X$ at this stage?

• There exists an elementary substructure $N \preceq L_\lambda$ such that $X \subseteq N \subseteq L_\lambda$ and $|N| = |X|$.
  Use a famous theorem from logic.

• Can we apply the condensation lemma to $N$?
  What are the possible obstacles?

• Apply a Mostowski collapse to $N$. This gives us a transitive $M$ isomorphic to $N$.
  Now we have a new problem. What is it? (Hint: where does $x$ go?)

• Argue that the Mostowski isomorphism fixes $x$.
  Hint: What does it do with ordinals?

• Now we can apply condensation. This yields $M = L_\beta$ for some $\beta$.
  Quick check: Where does this put $x$ now?

• Key argument: $|\beta| = \kappa$.
  Hint: Proposition 53

• Finish: $x \in L_{\kappa^+}$

+++

If $\mathsf{VL}$, then for all cardinals $\kappa$, $2^\kappa = \kappa^+$.

+++

If $\mathsf{ZF}$ is consistent, so is $\mathsf{ZF} + \mathsf{GCH}$.

+++

Second application: the complexity of constructible reals

+++

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 } ]. $$

+++

Can we "convert" this into a formula of second order arithmetic?

+++

How could the condensation lemma help with this?

+++

Key ideas:

• every constructible real shows up at a countable stage of $L$.
  Why?

• Hence if $\alpha \in L \cap \mathbb{N}^{\mathbb{N}}$, there exists a countable $\xi$ such that $x \in L_\xi$.

• Then $L_\xi$ is countable, too.
  Why?

• Hence we can hope to replace $L_\xi$ by something like

"there exists a real that codes a model that looks like $L_\xi$"

+++

Key ingredients:

• Condensation lemma and Mostowski collapse
  Can you think why these are important here?

+++

This is the formula:

\begin{align*} \tag{$**$} \alpha \in L \cap \mathbb{N}^{\mathbb{N}} \iff \exists \beta \exists & m : [E_\beta \text{ is extensional and well-founded} \ & : \wedge : (\omega,E_\beta) \models \phi_{VL} : \wedge : \pi_\beta(m) = \alpha ], \end{align*}

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

+++

• Why does this work?
• What do we still need to verfiy to make sure this is in second order arithmetic?

+++

Ingredient 1:

$\quad$ For any $n \in \Nat$, the following set is $\Sigma^0_n$: \begin{equation*} {(m,\sigma,\gamma) \in \Nat\times \Nstr\times \Baire \colon m = \GN{\phi} : \wedge : \phi \text{ is $\Sigma_n$} : \wedge : (\omega,E_\gamma) \models \phi[\sigma] } \end{equation*}

• You don't need to prove this fully. Just think about how you would prove it. In particular, how would you arithmetize the truth relation $(\omega, E_\beta)\models \psi$?

• Since we work with relations over $\mathbb{N}$ now instead of arbitrary sets, it is not that easy anymore to keep quantifiers bounded. Think of an example for this difficulty. Why can't we just convert a bounded quantifier $\exists x \in y$ to a bounded quantifier in arithmetic $\exists m < n$?

• But since we are only interested in the complexity of $\models$ for $\Sigma_1$-formulas, this helps us bound the overall complexity at $\Sigma^0_1$

+++

Ingredient 2:

If $\alpha \in \mathbb{N}^{\mathbb{N}}$ and $E_\alpha$ is well-founded and extensional, then the following set is arithmetic in $\alpha$: \begin{equation*} { (m,\gamma) \in \mathbb{N}\times \mathbb{N}^{\mathbb{N}} \colon \pi_\alpha(m) = \gamma} \end{equation*}

• Again, you do not need to fully prove this, just think about how you would do it. In particular, how would you arithmetize $\pi_\alpha$?

+++

Now put everything together and show

+++

The set $L \cap \mathbb{N}^{\mathbb{N}}$ is $\Sigma^1_2$.

+++

In a similar way we can show

The set $\{(\alpha,\beta) \in (L\cap\mathbb{N}^{\mathbb{N}})^2 \colon \alpha <_L \beta\}$ is $\Sigma^1_2$.

If $\mathsf{VL}$, then the set is actually $\Delta^1_2$, since then

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

+++

This has consequences for the existence of non-measurable sets. Find or recall the corresponding theorem and formulate a theorem under the hypothesis $\mathsf{VL}$.