\documentclass{article}
\usepackage{amsmath,amstext,amsfonts,amsthm,latexsym}
\usepackage{enumerate}
\renewcommand\baselinestretch{0.95}
\topmargin -0.65in
\oddsidemargin -0.25in
\evensidemargin -0.25in
\textwidth 7.0in
\textheight 9.3in
%%% my math definitions
\def\lnot{\neg}
\def\land{\;\wedge\;}
\def\lor{\;\vee\;}
\def\lthen{\;\rightarrow\;}
\def\liff{\;\leftrightarrow\;}
\def\peq{\Leftrightarrow}
\def\cross{\;\times\;}
% some set theoretic definitions
\newcommand{\powerset}{\mathcal{P}}
\newcommand{\es}{\emptyset}
% Vn zermelo hierarchy of sets, V0 - V3
\newcommand{\VO}{\es}
\newcommand{\VI}{\{\VO\}}
\newcommand{\VII}{\{\VO, \VI\}}
\newcommand{\VIII}{\{\VO, \VI, \{\VI\}, \VII\}}
%%% my environments
\theoremstyle{definition}\newtheorem{exercise}{Exercise}[subsection]
\theoremstyle{remark}\newtheorem*{answer}{Answer}
\theoremstyle{plain}\newtheorem*{axiom}{}
\newtheorem{thm}{Theorem}[subsection]
\newtheorem{corollary}{Corollary}[subsection]
%%% my numbering alterations
\numberwithin{equation}{subsection}
%%% professor's macros follow...
\def\spo{\hspace{1ex}}
\def\eqd{\mathord{\spo\spo=_{\mbox{\footnotesize\it def}}\spo\spo}}
\def\Mthen{\mathord{\spo\spo\Rightarrow\spo\spo}}
\def\Miff{\mathord{\spo\spo\Leftrightarrow\spo\spo}}
\def\A{\mathord{{\mathfrak A}}}
\def\sA{\mathord{^{\A}}}
\def\Cn{\mathord{\mbox{Cn}}}
\def\B{\mathord{{\mathfrak B}}}
\def\G{\mathord{{\cal G}}}
\def\N{\mathord{{\mathfrak N}}}
\def\M{\mathord{{\mathfrak N}}}
\def\Nat{\mathord{{\mathbb N}}}
\newcommand\R{{\mathbb R}}
\newcommand\Z{{\mathbb Z}}
\newcommand\Lang{{\cal L}}
\newcommand\E{\mbox{\em Exp}}
\newcommand\Mod{\mbox{\hspace{1pt}Mod\hspace{1pt}}}
\newcommand\Th{\mbox{\hspace{1pt}Th\hspace{1pt}}}
\newcommand\Con{\mbox{\hspace{1pt}Con\hspace{1pt}}}
\def\AS{\mathord{{\mathbb A}_S}}
\def\AL{\mathord{{\mathbb A}_L}}
\def\AE{\mathord{{\mathbb A}_E}}
\def\sN{\mathord{^{\N}}}
\def\sA{\mathord{^{\A}}}
\def\sB{\mathord{^{\B}}}
\def\NS{\mathord{\N_S}}
\def\NL{\mathord{\N_L}}
\def\NA{\mathord{\N_A}}
\def\NM{\mathord{\N_M}}
\def\NE{\mathord{\N_E}}
\newcommand\PAE{{\mathbb P}{\mathbb A}_E}
\def\St{\mathord{{\cal S}t}}
\def\un{\underline}
\def\a{\mathord{\vec{a}}}
\def\app{\mathord{a^{\prime\prime}}}
\def\b{\mathord{\vec{b}}}
\def\c{\mathord{\vec{c}}}
\def\n{\mathord{\vec{n}}}
\def\p{\mathord{\vec{p}}}
\def\q{\mathord{\vec{q}}}
\def\Th{\mathord{Th}}
\def\v{\mathord{\vec{v}}}
\def\w{\mathord{\vec{w}}}
\def\x{\mathord{\vec{x}}}
\def\y{\mathord{\vec{y}}}
\def\z{\mathord{\vec{z}}}
\def\tp{\mathord{t^\prime}}
\def\tpp{\mathord{t^{\prime\prime}}}
\def\sp{\mathord{s^\prime}}
\def\bp{\mathord{b^\prime}}
\def\<{\mathord{\langle}}
\def\>{\mathord{\rangle}}
\def\Prime{\mathord{\mbox{prime}}}
\def\lh{\mathord{\mbox{lh}}}
\def\tf{\mathord{\tilde{f}}}
\def\seqno{\mathord{\mbox{seq$\_$no}}}
\def\restrict{\mathord{|\hspace{-4pt}\stackrel{\backslash}{\hspace{2pt}}}}
\def\twotree{\mathord{\mbox{2-Tree}}}
\def\form{\mathord{\mbox{formula}}}
\def\sent{\mathord{\mbox{sentence}}}
\def\branch{\mathord{\mbox{branch}}}
\def\leaf{\mathord{\mbox{leaf}}}
\def\tail{\mathord{\mbox{tail}}}
\def\appendleaf{\mathord{\mbox{append@leaf}}}
\begin{document}
\centerline{\LARGE\bf Mathematical Logic III}
\centerline{\Large\bf The Joy of Sets}
\centerline{\Large\bf Chapter 5}
\centerline{\large\bf Ryan Flannery}
%%%
%%% chapter 5 - the constructible hierarchy
%%%
\setcounter{section}{4}
\section{The Axiom of Constructibility}
In Chapter 2, we defined the $V$ hierarchy of sets making use of what we
called the {\em unrestricted power set operation}. The power set axiom
allowed us to keep our notions of {\em set} and {\em subset} vague.
In this chapter, we cover an {\em extension} to $ZF$ set theory that attempts
to remove this vagueness.
%%%
%%% section 5.1 - constructible sets
%%%
\subsection{Constructible Sets}
Let a set be any {\em describable} collection. How do we ``describe'' a set?
By the only means we have: LAST. Thus, any collection that can be described
by a formula of LAST is a set. Using this new definition, we can redefine
the set-theoretic hierarchy.
In the $V$ hierarchy, we made use of the {\em unrestricted power set}
operation. In the new hierarchy, we introduce the {\em describable power
set} operation.
\begin{description}
\item[Unrestricted Power Set] The unrestricted power set of $X$ is the set
of {\em all} subsets of $X$.
\item[Describable Power Set] The describable power set of $X$ is the set of
all {\em describable} (by means of LAST) subsets of $X$.
\end{description}
Precise Definition:
$X \in L_{\alpha + 1}$ if and only if there is a formula $\phi(v_n)$ of LAST,
with the single free variable $v_n$, and sets $a_1,\ldots,a_m$ in $L_\alpha$,
which interpret the names involved in $\phi$, such that $X$ is the collection
of all $x \in L_\alpha$ for which $\phi(x)$ is true. Any quantifiers in
$\phi$ are interpreted over $L_\alpha$ since the only sets we can describe
(at stage $\alpha$) exist in $L_\alpha$.
The describable power set is the set of all such $X$.
Just as we did in the $V$ hierarchy, we begin the hierarchy with the empty
set and at limit levels we take the union of all previous levels.
\begin{eqnarray}
L_0 & = & \es \\
L_\lambda & = & \bigcup_{\alpha < \lambda} L_\alpha \\
L_{\alpha + 1} & = & \text{The describably power set of $L_\alpha$}
\end{eqnarray}
With that, our constructible universe is:
\begin{equation} L = \bigcup_\alpha L_\alpha \end{equation}
%%%
%%% section 5.2 - the constructible hierarchy
%%%
\subsection{The Constructible Hierarchy}
The following properties of the $V$ hierarchy are also shared with the
constructible hierarchy:
\begin{itemize}
\item $L_\alpha \subseteq L_\beta$ for $\alpha \leq \beta$
\item each $L_\alpha$ is transitive ($x \in L_\alpha \lthen x
\subseteq L_\alpha$)
\item $L_\alpha \cap On = \{\beta \mid \beta < \alpha\} = \alpha$
\end{itemize}
This is, however, where the similarities end. The following are some of the
key differences between the $L$ hierarchy and the $V$ hierarchy.
\begin{itemize}
\item $\vert L_\alpha \vert = \vert \alpha \vert$ for every infinite
ordinal $\alpha$. This is a direct consequence of LAST being countable.
\item With that, $\vert L_{\omega + 1} \vert = \aleph_0$. Trivial, since
$\aleph_0 = \vert \omega + 1 \vert$.
\item However, since $\powerset(\omega) \subseteq V_{\omega + 1}$, we have
that $\vert V_{\omega + 1} \vert > \aleph_0$.
\item So, $L_{\omega + 1} \not= V_{\omega + 1}$! This is where the $L$
hierarchy begins to separate from the $V$ hierarchy. The $L$ hierarchy
grows {\em much} more slowly than the $V$ hierarchy.
\item {\em Hold on!} From what we stated above, $L_{\omega + 1}$ is
countable. We proved earlier, however, that $\powerset(\omega)$ is
uncountable. How is this possible if $\powerset(\omega) \subseteq
L_{\omega + 1}$? Simple: not all of $\powerset(\omega)$ will be
contained in $L_{\omega + 1}$. Remember, we only include those subsets
of $\omega$ that are describable by LAST, and $\powerset(\omega)$
contains {\em all} subsets (describably or not) of $\omega$.
\end{itemize}
%%%
%%% section 5.3 - the axiom of constructibility
%%%
\subsection{The Axiom of Constructibility}
Now, just as we did in \S2.2, we look at the $L$ hierarchy and isolate all
those assumptions we made that were necessary in constructing $L$. These
assumptions will be our axioms for this constructible set theory. As it
turns out, the assumptions we made were a subset of those assumptions we
made when constructing the $V$ hierarchy. As such, the $ZF$ axioms suffice
for building the constructible hierarchy!
We want to go a step further, however, and show that {\em the} universe is
constructible. That is, that $V = L$. This requires an additional axiom
that is called the {\em Axiom of Constructibility}.
So we can summarize constructible set theory as:
\begin{enumerate}
\item The $ZF$ axioms
\item $V = L = \bigcup_\alpha L_\alpha$ - The Axiom of Constructibility
\end{enumerate}
So, constructible set theory is an {\em extension} of $ZF$ set theory, and is
typically denoted as $ZF + (V = L)$
Key consequence of $ZF + (V = L)$: $AC$ is provable!
\begin{thm}
In $ZF + (V = L)$, every set can be well-ordered.
\end{thm}
\begin{proof}
As Devlin states, the proof of this theorem (done by G\" odel) is
beyond the scope of this book. Page 126 of the text provides a brief
(very brief) overview of the proof.
\end{proof}
\vspace{3mm}
{\em So, the axiom of constructibility is equivalent to fixing a precise
definition of what a set is!}
\vspace{3mm}
{\em Notation Considerations} From now own, we always take the $ZF$ axioms to
be basic. If any theorem requires $AC$, it should explicitly state it.
Similarly, if any theorem requires $V = L$, it should explicitly state it.
%%%
%%% section 5.4 - the consistency of V = L
%%%
\subsection{The Consistency of $V = L$}
$ZF + (V = L)$ seems nice, but is it consistent? We learned last quarter
that within any system, the consistency of the system can not be proven.
And since we are adding an additional axiom to $ZF$ (one that isn't intuitive),
$ZF + (V = L)$ may seem more susceptible to inconsistency. Fortunately,
G\" odel showed otherwise.
\begin{thm}
If $ZF$ is consistent, so to is $ZF + (V = L)$.
\end{thm}
\begin{proof}
Once again, Devlin states that the proof of this theorem is beyond the
scope of this book. The basic approach of the proof is this: G\" odel
shows that {\em any} model for $ZF$ is also a model for $ZF + (V = L)$.
\end{proof}
Since $ZF + (V = L)$ proves $AC$, we have the following corollary:
\begin{corollary}
If $ZF$ is consistent, so too is $ZFC$.
\end{corollary}
%%%
%%% section 5.5 - uses of the axiom of constructibility
%%%
\subsection{Uses of the Axiom of Constructibility}
Here, we look at some of the things that the axiom of constructibility
affords us.
\begin{itemize}
\item Assuming $V = L$, $AC$ is provable (as we saw in \S5.3.)
\item Assuming $V = L$, $GCH$ holds.
\begin{proof}
Alas! Yet again Devlin informs us that this proof is beyond the
scope of this book.
\end{proof}
\item Assuming $V = L$, the combinatorial consequence known as $\Diamond$
holds.
\begin{quote}
There is a sequence $\langle S_\alpha \mid \alpha < \omega_1 \rangle$
such that for each $\alpha < \omega_1$, $S_\alpha \subseteq \alpha$,
and whenever $X \subseteq \omega_1$, then for some infinite ordinal
$\alpha \in \omega_1$, $X \cap \alpha = S_\alpha$.
\end{quote}
How $V = L$ implies $\Diamond$ is, you guessed it, beyond the scope
of this book. However, $\Diamond$ implies $CH$.
\end{itemize}
In general, although $V = L$ is not intuitive the way most of the other $ZF$
axioms are, assuming it affords us proofs for $CH$/$GCH$, $AC$, $\Diamond$,
and the Souslin Problem (briefly mentioned at the beginning of \S5.1).
Further, as G\" odel proved, if $ZF$ is consistent (which we have no way of
knowing) then so is $ZF + (V = L)$. So $V = L$ is a ``safe'' extension of
$ZF$.
\end{document}