Untitled.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9d13b4f2-e80d-486b-8d38-c335e0453f2d",
   "metadata": {},
   "source": [
    "# Guided Study: The Condensation Lemma\n",
    "$$\n",
    "\\newcommand{\\Nat}{\\mathbb{N}}\n",
    "\\newcommand{\\Real}{\\mathbb{R}}\n",
    "\\newcommand{\\Integer}{\\mathbb{Z}}\n",
    "\\newcommand{\\Rat}{\\mathbb{Q}}\n",
    "\\newcommand{\\Baire}{\\Nat^{\\Nat}}\n",
    "\\newcommand{\\Cyl}[1]{N_{#1}}\n",
    "\\newcommand{\\Cant}{2^{\\Nat}}\n",
    "\\newcommand{\\Nstr}{\\Nat^{<\\Nat}}\n",
    "\\newcommand{\\Tup}[1]{\\langle #1 \\rangle}\n",
    "\\newcommand{\\Co}[1]{\\neg \\,#1}\n",
    "\\newcommand{\\Op}[1]{\\operatorname{#1}}\n",
    "\\newcommand{\\Rest}[1]{|_{#1}}\n",
    "\\newcommand{\\CH}{\\mathsf{CH}}\n",
    "\\newcommand{\\GCH}{\\mathsf{GCH}}\n",
    "\\newcommand{\\AC}{\\mathsf{AC}}\n",
    "\\newcommand{\\ZF}{\\mathsf{ZF}}\n",
    "\\newcommand{\\ZFC}{\\mathsf{ZFC}}\n",
    "\\newcommand{\\VL}{\\mathsf{V=L}}\n",
    "\\newcommand{\\GN}[1]{\\ulcorner #1 \\urcorner}\n",
    "\\newcommand{\\Const}[1]{\\underline{#1}}\n",
    "\\newcommand{\\V}{\\mathbf{V}}\n",
    "\\newcommand{\\Ord}{\\mathbf{Ord}}\n",
    "\\DeclareMathOperator{\\W}{W}\n",
    "\\DeclareMathOperator{\\WF}{WF}\n",
    "\\DeclareMathOperator{\\WOrd}{WOrd}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dcbf651-a90a-4f2f-9634-19d930ef2200",
   "metadata": {},
   "source": [
    "## The condensation lemma\n",
    "\n",
    "```{admonition} Condensation lemma\n",
    "\n",
    "There is a finite set $T$ of axioms of $\\ZF - \\text{Power Set}$ so that if $M$ is a transitive set with $M\\models T + \\VL$, then $M = L_\\lambda$ for some limit ordinal $\\lambda$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38eb41ee-ce1e-473a-959a-2400df37dde5",
   "metadata": {},
   "source": [
    "Define: $\\varphi_{\\VL} = $  conjunction of the axioms in $T$ and the axiom $\\VL$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2997ae33-d5c5-4fed-87bc-cb8793c3a830",
   "metadata": {},
   "source": [
    "## First application: $\\VL$ implies $\\GCH$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fef96ae8-500e-43bc-8da5-01131e318a89",
   "metadata": {},
   "source": [
    "```{admonition} Key Lemma \n",
    "\n",
    "Suppose $V=L$. If $\\kappa$ is a cardinal and $x \\subseteq \\kappa$, then $x \\in L_{\\kappa^+}$.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74c74337-61e1-4bd9-a3ce-38725eeedf7b",
   "metadata": {},
   "source": [
    "<!-- Basic idea of the proof:\n",
    "\n",
    "Since $\\VL$, $x$ has to enter $L$ at some stage, say $x \\in L_\\lambda$. We can assume  $L_\\lambda$ satisfies a \"suffiently large\" fragment of $\\ZF + \\VL$, in particular  -->"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f266ea9e-cbb4-47fd-ae8c-2b7aac3c12e5",
   "metadata": {},
   "source": [
    "Guide to proof: *Verify each of following steps.*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78633c3b-2393-42b6-9af7-33ece7149948",
   "metadata": {},
   "source": [
    "- There exists limit $\\lambda > \\kappa$ such that $x \\in L_\\lambda$ and such that $L_\\lambda \\models \\varphi_{\\VL}$\n",
    "\n",
    "- Let $X = \\kappa \\cup \\{x\\}$.  \n",
    "    *What do we know about $X$ at this stage?*\n",
    "    \n",
    "- There exists an **elementary substructure** $N \\preceq L_\\lambda$ such that\n",
    "\\begin{equation*} \\tag{$*$}\n",
    "    X \\subseteq N \\subseteq L_\\lambda \\quad \\text{ and } \\quad |N| = |X|.\n",
    "\\end{equation*}\n",
    "*Use a famous theorem from logic.*\n",
    "\n",
    "- Can we apply the condensation lemma to $N$?  \n",
    "*What are the possible obstacles?* \n",
    "\n",
    "- Apply a Mostowski collapse to $N$. This gives us a transitive $M$ isomorphic to $N$.  \n",
    "*Now we have a new problem. What is it? (Hint: where does $x$ go?)*\n",
    "\n",
    "- Argue that the Mostowski isomorphism fixes $x$.    \n",
    "*Hint: What does it do with ordinals?*\n",
    "\n",
    "- Now we can apply condensation. This yields $M = L_\\beta$ for some $\\beta$.  \n",
    "*Where does this put $x$ now?*\n",
    "\n",
    "- **Key argument**: $|\\beta| = \\kappa$.  \n",
    "*Hint: Proposition 53*\n",
    "\n",
    "- Finish: $x \\in L_{\\kappa^+}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0dee81a-107e-4a41-8937-dbadc178b487",
   "metadata": {},
   "source": [
    "```{admonition} $\\VL \\to \\GCH$\n",
    "\n",
    "If $\\VL$, then for all cardinals $\\kappa$, $2^\\kappa = \\kappa^+$.\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bf90bf2-0afd-4c8f-b737-20623e796d6c",
   "metadata": {},
   "source": [
    "```{admonition} Corollary \n",
    "\n",
    "If $\\ZF$ is consistent, so is $\\ZF + \\AC + \\mathsf{GCH}$.\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d22f4e42-0a2e-4aea-9c69-851d58a0d0b8",
   "metadata": {},
   "source": [
    "## Second application: the complexity of constructible reals"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ab42c74-dfcf-4ddd-8dbc-95cd272d9dc6",
   "metadata": {},
   "source": [
    "The set of all constructible reals is defined by a $\\Sigma_1$ formula over set theory:\n",
    "\n",
    "$$\n",
    "   \\varphi(x_0)\t\\; \\equiv \\; \\exists y \\; [y \\text{ is an ordinal }  \\; \\wedge \\; x_0 \\in L_y \\; \\wedge \\; x_0 \\text{ is a set of natural numbers }  ].\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0a07052-ad36-434c-98e7-98d36a2dece6",
   "metadata": {},
   "source": [
    "**Can we \"convert\" this into a formula of second order arithmetic?**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8b1f441-acee-4525-aa61-312dd8327b39",
   "metadata": {},
   "source": [
    "*How could the condensation lemma help with this?*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9baa2fc0-de8e-4076-bb97-4d0eed9e6956",
   "metadata": {},
   "source": [
    "**Key ideas**:\n",
    "    \n",
    "- every constructible real shows up at a countable stage of $L$.  \n",
    "*Why?*\n",
    "\n",
    "- Hence if $\\alpha \\in L \\cap \\Baire$, there exists a countable $\\xi$ such that $x \\in L_\\xi$. \n",
    "\n",
    "- Then $L_\\xi$ is countable, too.  \n",
    "*Why?*\n",
    "\n",
    "- Hence we can hope to replace $L_\\xi$ by something like \n",
    "> \"*there exists a real that codes a model that looks like $L_\\xi$*\"  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "856889fb-12bb-46a4-a24f-091d71b776ae",
   "metadata": {},
   "source": [
    "**Key ingredients**:\n",
    "\n",
    "- Condensation lemma and Mostowski collapse  \n",
    "*Can you think why these are important here?*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88a9bb40-eb43-48c8-9407-4bc346450c47",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{multline*} \\tag{$**$}\n",
    "\t\\alpha \\in L \\cap \\Baire \\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 ],\n",
    "\\end{multline*}\n",
    "$$\n",
    "where $\\pi_\\beta$ is the Isomorphism of the Mostowski collapse of $E_\\beta$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b7c62668-9da1-4f0e-9dc9-ff8d76f2ce66",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}