\documentclass{amsart}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mathabx}
\usepackage{stmaryrd}
\usepackage{mathbbol}


\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}



\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exer}{Exercise}
\newtheorem{exam}{Example}


\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{fact}[thm]{Fact}
\newtheorem{hyp}[thm]{Hypothesis}

\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bone}{\mathbb{1}}
\newcommand{\res}{\restriction}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\cof}{\operatorname{cof}}
\newcommand{\ot}{\text{o.t.}}
\newcommand{\on}{\text{ON}}
\newcommand{\card}{\text{CARD}}
\newcommand{\ac}{\text{AC}}
\newcommand{\zf}{\text{ZF}}
\newcommand{\zfc}{\text{ZFC}}
\newcommand{\sP}{\mathcal{P}}
\newcommand{\sL}{\mathcal{L}}
\newcommand{\sA}{\mathcal{A}}
\newcommand{\sF}{\mathcal{F}}
\newcommand{\ch}{\text{CH}}
\newcommand{\gch}{\text{GCH}}
\newcommand{\sh}{\text{SH}}
\newcommand{\vb}{\text{var}}
\newcommand{\pa}{\text{PA}}
\newcommand{\fa}{\text{F}}
\newcommand{\con}{\text{CON}}


\newcommand{\bz}{\boldsymbol{0}}
\newcommand{\lD}{{\Delta}}
\newcommand{\lS}{{\Sigma}}
\newcommand{\lP}{{\Pi}}
%\newcommand{\models}{\vDash}
\newcommand{\proves}{\vdash}
\newcommand{\sg}{\text{sg}}
\newcommand{\seq}{\text{Seq}}
\newcommand{\lh}{\text{lh}}
\newcommand{\pred}{\text{pred}}
\newcommand{\hod}{\text{HOD}}
\newcommand{\od}{\text{OD}}
\newcommand{\trcl}{\text{tr\,cl}}
\newcommand{\cl}{\text{cl}}
\newcommand{\rank}[1]{|#1|}
\newcommand{\llex}{<_{\text{lex}}}
\newcommand{\comp}{\parallel}
\newcommand{\forces}{\Vdash}
\newcommand{\fn}{\text{FN}}
\newcommand{\ccc}{\text{c.c.c.}}
\newcommand{\cc}{\text{c.c.}}
\newcommand{\sat}{\text{sat}}
\newcommand{\coll}{\text{coll}}
\newcommand{\cub}{\text{c.u.b.}}
\newcommand{\conc}{{}^\smallfrown}




\begin{document}




\begin{center}
\bf More Forcing Constructions
\end{center}
\bigskip



We use forcing to establish the consistency of some combinatorial
principles which are of use in many constructions. 
First we introduce Jensen's diamond principle.


\begin{defn}
$\Diamond$ is the statement: there are $A_\alpha \subseteq \alpha$ for 
$\alpha < \omega_1$ such that for all $A \subseteq \omega_1$, 
$\{ \alpha < \omega_1 \colon A \cap \alpha = A_\alpha \}$ is 
stationary. 
\end{defn}


Clearly $\Diamond$ implies $\ch$ as every subset of $\omega$ must
appear among the $A_\alpha$. This already shows that $\Diamond$
is not provable in $\zfc$. In fact it is known that $\gch$
does not imply $\Diamond$ (Jensen). 
$\Diamond$ is thus a powerful strengthening of $\ch$, and is 
useful in places where $\ch$ alone is not sufficient. 
First we show that we may force to make $\Diamond$ true. 



\begin{lem} \label{diamond}
Let $M$ be a transitive model of $\zfc$. Then there is a generic
extension $M[G]$ in which $\Diamond$ holds. 
\end{lem}



\begin{proof}
Let $\bP$ consist of all countable sequences $p= 
\{ A_\beta \}_{\beta < \alpha}$ where $\alpha < \omega_1$ and 
$A_\beta \subseteq \beta$. We order $\bP$ by extension, 
so $p \leq q$ iff $\dom(p) \geq \dom(q)$ and $p \res \dom(q) =q$. 
Let $G$ be $M$ generic for $\bP$. 
Clearly $\bP$ is countably closed,  
so $\omega_1^{M[G]}=\omega_1^M$.  The generic can be identified 
with a sequence $\{ A_\beta \}_{\beta < \omega_1}$. We show that this 
sequence witnesses $\Diamond$ in $M[G]$. Fix $A \subseteq \omega_1$, 
$A \in M[G]$, and a $C \subseteq \omega_1$, $C \in M[G]$ with 
$(C$ is \cub $)^{M[G]}$. Let $A= \tau_G$, $C=\sigma_G$. 
Let $p_0 \in G$, $p_0 \forces (\sigma \text{ is \cub })$. 
Let $\dot{G}$ be the canonical name for the generic. 
We claim that 
$p_0 \forces \exists \alpha ((\alpha \in \sigma) \wedge 
(\tau \cap \alpha = \dot{G}(\alpha)) )$. Suppose not, and let 
$p_1 \leq p_0$, $p_1 \in G$ with 
$p_1 \forces \forall \alpha\ \neg ((\alpha \in \sigma) \wedge 
(\tau \cap \alpha = \dot{G}(\alpha)) )$. 
Working in $M$, we construct a sequence of 
conditions $q_0=p_1 \geq q_1 \geq \dots$ as
follows. Assume $q_n$ has been defined. Let $q_{n+1} \leq q_n$
be such that 
\begin{enumerate}
\item
$\dom(q_{n+1}) > \dom(q_n)$ and there is a $\beta_n \in 
(\dom(q_n), \dom(q_{n+1}))$ such that $q_{n+1} \forces 
\check{\beta_n} \in \sigma$. 
\item
For every $\alpha < \dom(q_n)$, either $q_{n+1} \forces 
\check{\alpha} \in \tau$ or $q_{n+1} \forces 
\check{\alpha} \notin \tau$. 
\end{enumerate}
There is no problem getting $q_{n+1}$ as $p_0 \forces 
(\sigma$ is unbounded $)$ and $\bP$ is countably closed. 
Let $q= \bigcup_n q_n$. Let $\alpha= \dom(q)=\bigcup_n \dom(q_n)$. 
From (1) and the fact that $p_0 \forces (\sigma$ is closed$)$ 
it follows that $q \forces \check{\alpha} \in \sigma$. 
From (2), there is a $B \subseteq \alpha$, $B \in M$, with 
$q \forces \tau \cap \alpha = B$. Let $q'=q \cup \{ \langle 
\alpha, B \rangle \}$. Then $q' \forces ((\check{\alpha} \in \sigma) \wedge
(\tau \cap \check{\alpha} = \dot{G}(\check{\alpha}))$. This contradicts
the definition of $p_1$.
\end{proof}


The forcing used in lemma~\ref{diamond} is isomorphic to a dense
subset of $\fn(\omega_1,2,\omega_1)$ ($\fn(\omega_1,2,\omega_1)$
is isomorphic to $\bP=\fn(A,2, \omega_1)$, where $A=\{ (\beta, \alpha) \colon
\beta < \alpha< \omega_1 \}$. 
The forcing used in the lemma is a dense subset of $\bP$.)
Thus we get:

\begin{cor}
Let $M$ be a transitive model of $\zfc$ and $G$ be $M$-generic for 
$\fn(\omega_1,2,\omega_1)^M$. Then $\Diamond$ holds in $M[G]$.
\end{cor}

\begin{exer}
Show that if $M$ is a transitive model of $\zfc$ and $G$ is 
$M$-generic for $\coll(\omega_1, \kappa)$, for some $\kappa \geq \omega_1$,
then $\Diamond$ holds in $M[G]$. [hint: First identify $\coll(\omega_1,\kappa)=
\fn(\omega_1,\kappa,\omega_1)$ with $\bP=\fn(A, \kappa, \omega_1)$ where 
$A=\{ (\alpha,\beta) \colon \alpha < \beta < \omega_1\}$. A generic
$G$ for $\bP$ induces a $G' \colon 
\omega_1^2 \to 2$ by $G'(\alpha,\beta)=0 $ iff 
$G(\alpha, \beta)$
is even. Show that $G'$ gives a $\Diamond$ sequence in $M[G]$.]
\end{exer}




We can generalize $\Diamond$ to higher cardinals.


\begin{defn}
Let $\kappa$ be a regular cardinal. Then $\Diamond_\kappa$ is the statement
that there is a sequence $A_{\alpha} \subseteq \alpha$, $\alpha < \kappa$,
such that for all $A \subseteq \kappa$, $\{ \alpha < \kappa \colon 
A \cap \alpha = A_\alpha \}$ is stationary. 
\end{defn}



The proof of lemma~\ref{diamond} generalizes to give:


\begin{lem} \label{gendiamond}
Let $M$ be a transitive model of $\zfc$ and $\kappa$ a regular
cardinal of $M$. Then there is a generic
extension $M[G]$ which preserves all cardinals and cofinalities $\leq \kappa$
in which $\Diamond_\kappa$ holds. 
\end{lem}


\begin{proof}
Let $\bP$ consist of all functions $p$ with $\dom(p)$ an ordinal 
less than $\kappa$, and with $p(\alpha) \subseteq \alpha$ for all 
$\alpha \in \dom(p)$. 
Clearly $\bP$ is $< \kappa$ closed (since $\kappa$ is regular), 
and so $\bP$ preserves all 
cardinalities and cofinalities $\leq \kappa$. Let $G$ be $M$ generic for $\bP$.
The proof that $\Diamond_\kappa$ holds in $M[G]$ is essentially
identical to the proof of lemma~\ref{diamond}. 
Fix $A =\tau_G \subseteq \kappa$, 
and $C = \sigma_G \subseteq \omega_1$ with 
$(C$ is \cub $)^{M[G]}$. 
Let $p_0 \in G$, $p_0 \forces (\sigma \text{ is \cub })$. 
Suppose $p_1 \leq p_0$ with 
$p_1 \forces \forall \alpha\ \neg ((\alpha \in \sigma) \wedge 
(\tau \cap \alpha = \dot{G}(\alpha)) )$. 
We construct the sequence $q_0=p_1 \geq q_1 \geq q_2 \geq \dots$
as before. We use now $\bP$ being $< \kappa$ closed to get (2). 
As before, let $q= \bigcup_{n} q_n$ and let $q'= q \cup \{ \langle
B, \alpha \rangle \}$ where $\alpha =\dom(q)= \bigcup_n \dom(q_n)$
and $B \in M$, $q \forces \tau \cap \check{\alpha}= \check{B}$. 
This is a contradiction exactly as above.
\end{proof}


The forcing of lemma~\ref{gendiamond} is again 
equivalent to $\fn(\kappa,2, \kappa)$, thus we have:

\begin{cor} \label{gendiamondc}
Let $M$ be a transitive model of $\zfc$ and $\kappa$ a regular
cardinal of $M$. 
Let $G$ be $M$-generic for $\fn(\kappa,2,\kappa)^M$. Then $\Diamond_\kappa$
holds in $M[G]$.
\end{cor}





There are two natural weakenings of $\Diamond$ which turn out to be
equivalent to $\Diamond$ by a theorem of Kunen. One weakening is to 
replace ``stationary'' in the definition of $\Diamond$ with 
``non-empty.'' The second is to allow countably many sets at each 
stage $\alpha < \omega_1$ to do the guessing. the following theorem
gives the equivalence.




\begin{thm} (Kunen) \label{diamondreform}
The following are equivalent in $\zfc$.
\begin{enumerate}
\item
$\Diamond$
\item
There is a sequence $\{ \sA_\alpha \}_{\alpha < \omega_1}$, where
each $\sA_\alpha$ is a countable collection of subsets of $\alpha$, 
such that for every $A \subseteq \omega_1$ the set 
$\{ \alpha < \omega_1 \colon A \cap \alpha \in \sA_\alpha \}$ is 
stationary. 
\item
There is a sequence $\{ \sA_\alpha \}_{\alpha < \omega_1}$, where
each $\sA_\alpha$ is a countable collection of subsets of $\alpha$, 
such that for every $A \subseteq \omega_1$ the set 
$\{ \alpha < \omega_1 \colon A \cap \alpha \in \sA_\alpha \}$ is 
non-empty. 
\end{enumerate}
\end{thm}


\begin{proof}
First we show that (2) implies (1). Let $\pi \colon \omega \times 
\omega_1 \to \omega_1$ be a bijection. Let $D \subseteq \omega_1$
be \cub{} such that for $\alpha \in D$, $\pi \res \omega \times \alpha$ 
is a bijection between $\omega \times \alpha$ and $\alpha$. 
Let $\{ \sA_\alpha \}_{\alpha< \omega_1}= 
\{ A_{\alpha}^n \}_{\alpha < \omega_1, n < \omega}$
witness (2). Let $B_\alpha^{n,m}= \{ \beta < \alpha \colon 
\pi(m,\beta) \in A_\alpha^n \}$. We show that for some $n \in \omega$
that $\{ B_\alpha^{n,n} \}_{\alpha < \omega_1}$ is a $\Diamond$ sequence. 
If not, then for each $n$ let $E_n \subseteq \omega_1$, and $C_n$ be 
\cub{} witnessing the failure of $B_{\alpha}^{n,n}$ to be a $\Diamond$
sequence. Define $E$ to code the $E_n$ by: $\alpha \in E$ 
iff $\pi^{-1}(\alpha)=(k,\beta)$ and $\beta \in E_k$. By (2), 
let $\alpha \in D \cap \bigcap_n C_n$ such that 
$E \cap \alpha \in \sA_\alpha$. Say $E \cap \alpha = A_\alpha^n$. 
But then $B_\alpha^{n,n}=\{ \beta < \alpha \colon \pi(n,\beta) 
\in A_\alpha^n \}= \{ \beta < \alpha \colon \pi(n,\beta) 
\in E\cap \alpha \}=E_n\cap \alpha$, 
a contradiction to the definition of $E_n$
and $\alpha \in C_n$. 


We next show (3) implies (2). Let $\{ \sA_\alpha \}_{\alpha < \omega_1}$
be as in (3). Without loss of generality we may assume the $\sA_\alpha$
are increasing. 
We define a new sequence $\{ \sA'_\alpha\}_{\alpha < \omega_1}$
as follows. 
We view subsets of $\omega$ as coding bounded subsets of $\omega_1$
in some manner (e.g., take a bijection 
between $2^\omega$ and $\omega_1^{< \omega}$).
For successor ordinals let $\sA'_\alpha= \sA_\alpha$. 
For $\alpha$ limit let $\sA'_\alpha\supseteq  \sA_\alpha$
be such that:

(i) For all $n \in \omega$ and all $A \in \sA_{\alpha+n}$, 
$\{ \beta < \alpha \colon 2 \cdot \beta \in A \} \in \sA'_\alpha$.



(ii) Suppose $A \in \sA_{\alpha}$, $\beta < \alpha$ is a limit, 
and $x= \{ n \in \omega \colon \beta + 2n+1 \in A \}$ 
codes a subset $A_\beta$ of $\alpha$. Then $A_\beta \in \sA'_\alpha$.


To see this works, fix $A \subseteq \omega_1$ and a \cub{} 
$C \subseteq \omega_1$. We may assume $C$ consists of limit ordinals.
We must show that for some $\alpha \in C$ that 
$A \cap \alpha \in \sA'_\alpha$. Define $B \subseteq 
\omega_1$ as follows. For each limit $\beta$ let $x_\beta \subseteq \omega$ 
code $A \cap N_C(\beta)$, where $N_C(\beta)$ is the least element
of $C$ greater than $\beta$. Let $B= \{ 2 \cdot \gamma \colon 
\gamma \in A \} \cup \{ \beta + 2n +1 \colon \beta \text{ is limit } 
\wedge n \in x_\beta \}$. 

By (3), fix now $\alpha < \omega_1$ such that 
$B \cap \alpha \in \sA_\alpha$. If $\alpha \in C$ 
then $A \cap \alpha \in \sA'_\alpha$ by (i) (with $n=0$).
Let $\gamma$ be the largest element 
of $C$ less than $\alpha$. If $\alpha < \gamma + \omega$, then by (i)
we still have $A \cap \gamma  \in \sA'_\gamma$. If $\alpha \geq 
\gamma + \omega$, then from (ii) we have that $A \cap \delta 
\in \sA'_\delta$, where $\delta =N_C(\gamma)$. 

Thus, in all cases we have an $\alpha \in C$ with $A \cap \alpha \in 
\sA'_\alpha$. 
\end{proof}





Another generalization of $\Diamond$ is the following.



\begin{defn}
Let $\kappa$ be a regular cardinal and $S \subseteq \kappa$
stationary. Then $\Diamond_\kappa^S$ is the statement that there
is a sequence $\{ A_\alpha \}_{\alpha \in S}$ with $A_\alpha \subseteq \alpha$,
such that for all $A \subseteq \kappa$, the set 
$\{ \alpha \in S  \colon A \cap \alpha = S_\alpha \}$ is stationary.
\end{defn}


\begin{lem}
Let $M$ be a transitive model of $\zfc$, and $\kappa$ a regular
cardinal of $M$. Let $\lambda > (2^{< \kappa})^M$ be a 
cardinal of $M$.  Let $G$ be $M$-generic for
$\fn(\lambda,2,\kappa)$. Then in $M[G]$ we have that for every
stationary $S \subseteq \kappa$, $\Diamond_\kappa^S$ holds.
\end{lem}


\begin{proof}
The forcing $\bP=\fn(\lambda,2,\kappa)$ is $< \kappa$ closed in $M$,
so all cardinalities and cofinalities $\leq \kappa$ are preserved.
Also, $\bP$ is $(2^{< \kappa})^+$ c.c.\ in $M$. 


First we show that for every $S \in M$ which is stationary
in $M[G]$ that $\Diamond_\kappa^S$ holds in $M[G]$. 
Fix such an $S \in M$. Since $\lambda \cong \kappa^2 \oplus \lambda$, 
$\fn(\lambda,2,\kappa) \cong \fn( \kappa^2,2, \kappa) \times 
\fn(\lambda, 2, \kappa)$. Let $\bP$ be the forcing of
lemma~\ref{gendiamond}, that is, conditions $p$ are functions
with $\dom(p) < \kappa$ and for all $\alpha \in \dom(p)$, 
$p(\alpha) \subseteq \alpha$. Since 
$\bP \times \fn(\lambda,2,\kappa)$ is dense in 
$ \fn( \kappa^2,2, \kappa) \times 
\fn(\lambda, 2, \kappa)$, we may view $G$ as a product 
$G=G_1 \times G_2$ where $G_1 \subseteq \bP$, 
$G_2 \subseteq \fn(\lambda,2,\kappa)$ (more precisely, 
$M[G]=M[G_1][G_2]$ where $(G_1,G_2)$ is generic for the product).


Replacing $M$ by $M[G_2]$, it is enough to show that if
$M$ is a transitive model of $\zfc$, $\kappa$ is regular in $M$, 
$G$ is $M$-generic for $\bP$, and $S \in M$ is stationary in 
$M[G]$, then $M[G]$ satisfies $\Diamond_\kappa^S$. To see this, 
let $A= \tau_G \subseteq \kappa$ and $C= \sigma_G$ be \cub{}
in $M[G]$. Suppose $p \forces \neg \exists \alpha \ (\alpha \in 
\sigma \cap \check{S} \wedge \dot{G}(\alpha)= \tau \cap \alpha)$. 
In $M[G]$ define 
\begin{equation*}
\begin{split}
D=& \{ \alpha < \kappa \colon 
\forall \beta < \alpha\ \exists \gamma, \delta < \alpha\ (
\gamma > \beta \wedge G \res \delta \forces (\check{\gamma} \in 
\sigma) 
\\ & 
\wedge (G\res \delta \forces \check{\beta} \in \tau
\vee G\res \delta \forces \check{\beta} \notin \tau)
) \}.
\end{split}
\end{equation*}
Easily $M[G]$ satisfies that $D$ is a \cub{} subset
of $\kappa$ (recall $\kappa$ is regular in $M[G]$). Since
$S$ is stationary in $M[G]$, let $\alpha \in S \cap D$, with 
$\alpha > \dom(p)$. Let $q= G \res \alpha$. Thus, $q \leq p$. 
From $\alpha \in D$ we get that $q \forces (\check{\alpha} \in \sigma)$. 
Also, there is a $B \in M$ such that $q \forces \tau \cap \alpha
=\check{B}$. Let $q'=q \cup \{ \langle \alpha, B \rangle \}$. 
Then $q' \leq p$ and $q' \forces (\check{\alpha} \in (\check{S} \cap \sigma) 
\wedge \dot{G}(\check{\alpha})= \tau \cap \check{\alpha})$, a 
contradiction. 


Returning to the proof of the theorem, suppose now $S \in M[G]$
is stationary in $M[G]$, where $G$ denotes our $\fn(\lambda,2,\kappa)$
generic. Assume for convenience that $\lambda$ is regular in $M$. 
For any $\rho < \lambda$, we may write 
$\fn(\lambda,2,\kappa) \cong \fn(\rho,2,\lambda) \times 
\fn(\lambda-\rho,2,\kappa)$, and view $G$ as a product 
$G_\rho^- \times G_\rho^+$ accordingly. It suffices to show that for some
$\rho < \lambda$ that $S \in M[G_\rho^-]$. For then we may apply the
previous paragraph (using $M[G_\rho^-]$ as our ground model) to
conclude that $\Diamond_\kappa^S$ holds in $M[G]$. 
In fact, we show that any $S \subseteq \kappa$, $S \in M[G]$ 
lies in some $M[G_\rho^-]$. Since $\bP=\fn(\lambda,2,\kappa)$ is 
$\lambda$ c.c., there is a nice name for $S$ in $M$ of size 
$< \lambda$ (using $\lambda$ regular in $M$). Let $\tau$ be such a nice name,
that is, $| \tau |^M < \lambda$. Clearly then, $S= \tau_G= \tau_{G_\rho^-}$
for large enough $\rho$ (i.e., $\rho$ greater than the domains of all 
conditions in $\cup^3(\tau)$). Thus, $S \in M[G_\rho^-]$. 

If $\lambda$
is not regular in $M$, the argument of the previous paragraph still goes 
through writing instead $\fn(\lambda,2,\kappa)= 
\fn(T,2, \kappa) \times \fn(\lambda-T ,2,\kappa)$ for some 
$T \subseteq \lambda $ of size $\leq 2^{< \kappa} < \lambda$ (but $T$ may
now be cofinal in $\lambda$).
\end{proof}





\section{Suslin's Hypothesis}



We say a linear order $(X,<)$ is {\em dense} if whenever $x<y$ then
there is a $z \in X$ with $x < z < y$. We say $(x,<)$ is without
endpoints if there is no least or maximal element of $X$. 
We say $(X,<)$ is separable if there is a countable
set $D \subseteq X$ such that every non-empty interval
$(x,y)$ contains a point of $D$. We say $(X,<)$ is 
\ccc{} if there is no uncountable family of pairwise disjoint
open sets (equivalently, intervals). The linear order is 
separable or \ccc{} iff $X$ viewed as a topological space (with 
the order topology) is separable or \ccc{} We say $(X,<)$ is
{\em complete} if every non-empty bounded set in $X$ has a 
least upper bound and a greatest lower bound. 

Recall that for topological spaces in general, 
$2^{\text{nd}}$ countable $\Rightarrow$ separable $\Rightarrow$ \ccc{}
A countable product of $2^{\text{nd}}$ countable spaces is second
countable, but an $\omega_1$ product of $\R_{std}$ is not 
$2^{\text{nd}}$ countable (or even first countable). A 
$\leq 2^\omega$ length product of separable spaces is separable, 
but a $(2^\omega)^+$ product of $\R_{std}$ is not separable. 
Finally, an arbitrary product of second countable spaces is \ccc{}
(we'll discuss products of \ccc{} more later). 


The following lemma is an important but elementary fact from
analysis. It is just asserting that $\R$ is the unique 
completion of $\Q$. The proof is left to the exercises.


\begin{lem} \label{rq}
$(\R,<_{std})$ is the unique, up to isomorphism of linear 
orders, linear order $(X,<)$ satisfying:
\begin{enumerate}
\item
$(X,<)$ is dense and without endpoints. 
\item
$(X,<)$ is complete.
\item
$(X,<)$ is separable.
\end{enumerate}
\end{lem}



\begin{exer} (Cantor) \label{exerdiamond1}
Show that any two countable dense linear orders without endpoints are
isomorphic. [hint: Use a ``back and forth'' argument. Construct $f=
\bigcup_n f_n$ in $\omega$ stages, where each $f_n$ will be an
isomorphism from a subset of the first order of size $n$ to a subset
of the second order. At even stages $n=2m$, arrange that the $
m^{\text{th}}$ element of the first order is in the domain of $f_n$.
At odd stages $n=2m+1$, arrange that the $m^{\text{th}}$ element of
the second order is in the range of $f_n$.] 
\end{exer}




\begin{exer}
Prove lemma~\ref{rq}. [hint: Start with exercise~\ref{exerdiamond1}. 
Then extend the $f$ of that exercise to the completions of the 
countable dense sets, using the fact that both are complete.]
\end{exer}


Note that the requirement that $(X,<)$ not have endpoints is
rather trivial: if it has them then we can simply remove 
them without effecting the other properties of lemma~\ref{rq}.



A natural question, raised by Suslin, is whether the characterization
of the real line, lemma~\ref{rq}, continues to hold if we weaken
the requirement of separability to that of being \ccc{} The statement
that it does is called Suslin's hypothesis, $\sh$. 


\begin{defn}
Suslin's hypothesis, $\sh$ is the statement that $(\R, <_{std})$ is the
unique, up to isomorphism of linear orders, linear order 
$(X,<)$ which is dense, without endpoints, complete, and \ccc{}
\end{defn}


A counterexample to $\sh$ is called a {\em Suslin line}. 
That is, a Suslin line is a linear order $(X,<)$ which is 
dense, without endpoints, complete, and \ccc{}, but 
not separable. Thus, 
$\sh$ is the statement that there are no Suslin lines. 



The following lemma says that the existence of a Suslin line
is equivalent to the existence of a linear order $(X,<)$
which is \ccc{} but not separable, as the other properties can be
easily arranged.



\begin{lem} \label{lemsusequiv}
If there is a linear order $(X,<)$ which is \ccc{} but not 
separable, then there is a Suslin line. 
\end{lem}


\begin{proof}
Let $(X,<)$ be a \ccc{} but not separable linear order. 
Define an equivalence relation on $X$ by $x \sim y$ iff $(x,y)$
is separable. Each equivalence class $[x]$ is an interval of $X$. 
Distinct equivalence classes correspond to disjoint intervals. 
The classes then inherit an order from $X$, namely $[x] < [y]$
iff $x < y$ (equivalently, all the points of $[x]$ are less than 
any point of $[y]$). Let $\tilde{X}$ be the set of equivalence
classes with this induced order. We claim that $\tilde{X}$
is dense in itself, and \ccc{} but not separable. 
Granting this, we can then finish
by removing the endpoints of $\tilde{X}$, if any, then 
taking the completion. It is easy to check that the completion is
still \ccc{} and not separable (see the following exercise).
First note that every equivalence class $I=[x]$ is 
separable. To see this, let $(x_n,y_n)$ be a maximal family 
of parirwise disjoint intervals contained in $I$ (which must be countable 
as $X$ is \ccc). Let $D_n$ be dense in $(x_n,y_n)$, and 
let $D= \bigcup_n D_n$. Then $D$ together with the first and last elements of 
$I$ (if any) is dense in $I$. 

To see $\tilde{X}$ is dense in itself, suppose $[x]<[y]$. 
If $([x],[y])=\emptyset$, then $(x,y) \subseteq ([x] \cup [y])$,
and thus $D \cup E$ is dense in $(x,y)$ where $D$ is dense
in $[x]$ and $E$ is dense in $[Y]$. Thus, $x \sim y$, so $[x]=[y]$,
a contradiction. 

To see $\tilde{X}$ is not separable, if $\{ [d_n] \}_{n \in \omega}$
were dense in $\tilde{X}$, then let for each $n$  $D_n \subseteq [d_n]$
de dense in $[d_n]$. Then $D= \bigcup_n D_n$ is dense in $X$, a 
contradiction. 

To see $\tilde{X}$ is \ccc, suppose $([x_\alpha],[y_\alpha])$ 
is an antichain in $\tilde{X}$. Then $(x_\alpha,y_\alpha)$ is an 
antichain in $X$, so must be countable. 
\end{proof}



\begin{exer}
Let $(X,<)$ be a linear order. The completion $\hat{X}$ of $X$ 
can de defined by adding points $\hat{x}$ for all 
cuts (bounded above, downward closed sets) $S \subseteq X$ 
which do not have a least upper bound in $X$. The point $\hat{x}$
is greater than any element of $S$ but less than any element of 
$X$ which is greater than all the elements of $X$. 
Show that $X$ is dense in $\hat{X}$. 
Show that if $\hat{x} \in \hat{X}-X$, then $X$ has no
largest element below $\hat{x}$, and $X$ has no least element above
$\hat{x}$. Show that $X$ is separable iff $\hat{X}$ is separable. 
[if $\hat{D}$ is countable dense in $\hat{X}$, show that 
$D \cup E$ is dense in $X$ where $D=\hat{D} \cap X$ and 
$E$ is chosen so that for all nonempty intervals $(\hat{d_1},
\hat{d_2})$ where $\hat{d_1}$, $\hat{d_2} \in \hat{D}$ 
we have $E \cap (\hat{d_1},\hat{d_2}) \neq \emptyset$.] 
Show that $X$ is \ccc{} iff $\hat{X}$ is \ccc{} [if $(\hat{x},
\hat{y})$ is a non-empty interval in $\hat{X}$, show that
there are $x,y\in X$ with $\hat{x} \leq x < y \leq \hat{y}$
and $(x,y)$ non-empty in $X$.]
\end{exer}




Suslin's hypothesis we formulated by Suslin around 1920. 
It was reformulated in terms of a certain kind of tree, called 
Suslin trees, by Kurepa in the 30's. 
As we will see, $\sh$ is independent of $\zfc$, by results from the
late 60's. Jech and Tennenbaum showed the consistency of 
$\zfc+\neg \sh$, and Solovay and Tennenbaum the consistency of $\zfc+\sh$.
Jensen showed that Suslin trees exist in $L$, that is, 
$\neg \sh$ holds in $L$ (we discuss these points in more
detail below).



\section{Various Trees}


As we mentioned, Kurepa introduced the notion of a Suslin tree,
and showed $\neg \sh$ is equivalent to the existence of a Suslin tree.
In other words, the existence of a Suslin line is equivalent to the existence
of a Suslin tree. We prove this in this section, and introduce
a few other types of trees of interest. 


\begin{defn}
A {\em tree} is a partially ordered (i.e., transitive, irreflexive) 
set $(T,<_T)$ with the property
that for every $x \in T$, $\{y \in T \colon y <_T x \}$ is well-ordered.
for $x \in T$ we write $|x|_T$ (or just $|x|$ if $T$ is understood)
to denote the order-type of $\{ y\in T \colon y <_T x \}$. 
We call this the rank or height of $x$ in $T$. The height of $T$
is defined by $|T|= \sup \{ |x|_T+1 \colon x \in T \}$. By the 
$\alpha$th level of $T$ we mean the set of $x \in T$ of height $\alpha$.
A {\em chain} of $T$ is a subset which is linearly ordered by $<_T$. 
A {\em branch} $b$ of $T$ means a chain which is closed downwards
(i.e., if $x \in b$ and $y <_T x$, then $y \in b$). An antichain
$A$ of $T$ is a subset of $T$ of pairwise incomparable 
elements. 
\end{defn}


We are interested in trees of size $\kappa$, for various 
cardinals $\kappa$, which satisfy a certain non-triviality
condition:


\begin{defn}
Let $\kappa \in \card$. A $\kappa$-tree is a tree $T$ of height $\kappa$
such that all levels of the tree have size $< \kappa$. That is, 
$\forall \alpha < \kappa\ | \{ x \in T \colon |x|_T = \alpha \} | < \kappa$.
\end{defn}




We now introduce several particular trees of interest. 



\begin{defn}
Let $\kappa$ be a cardinal. A $\kappa$ Aronszajn tree is a $\kappa$ tree
with no branch of size $\kappa$. An Aronszajn tree refers to an 
$\omega_1$ Aronszajn tree. 
\end{defn}




Requiring more we get the notion of a Suslin tree.



\begin{defn}
Let $\kappa$ be a cardinal. A $\kappa$ Suslin tree is a $\kappa$ tree
with no chains of size $\kappa$ and no antichains of size $\kappa$. 
A Suslin tree refers to an $\omega_1$ Suslin tree.
\end{defn}


In other words, a $\kappa$ Suslin tree is a $\kappa$ Aronszajn tree
with no antichains of size $\kappa$. 



\begin{defn}
Let $\kappa$ be a cardinal. A $\kappa$ Kurepa tree is a $\kappa$ tree
with $\geq \kappa^+$ many branches of length $\kappa$. A Kurepa
tree refers to an $\omega_1$ Kurepa tree. 
\end{defn}



It is not immediately clear if any of these kinds of trees exist. 
We will see that Aronszajn trees exist in $\zfc$, but the existence
of Suslin and Kurepa trees is independent of $\zfc$. 



If desired, a $\kappa$ tree can, with perhaps a fairly trivial 
modification, be viewed as a subtree of $(\kappa^-)^\kappa$, where 
$\kappa^-=\sup \{ \lambda \in \card \colon \lambda < \kappa \}$. 
The modifications required are: we assume the tree has a single root,
that is, a single element of height $0$ (if not, we add one), and 
if $x \neq y \in T$ have limit height, then $\{ z \colon z <_T x\}
\neq \{ z \colon z <_T y\}$ (this can be arranged by adding extra elements
at limit levels, one for each branch of that height, that sit immediately
below the old points of that limit height). Given these adjustments,
it is now straightforward to define an isomorphism $\pi$ between $T$
and a subtree of $(\kappa^-)^\kappa$. If $x \in T$ has
height $\alpha$, then $\pi(x)$ will be a sequence with domain $\alpha$ 
(define $\pi(x)$ by induction on $|x|_T$, at limit stages take
unions of the $\pi(y)$ for $y<_T x$, and at successor steps use the 
fact that any $x \in T$ has $< \kappa$ many immediate extensions).



\begin{defn}
A tree $T$ is {\em branching} if every $x \in T$ has at least two 
distinct immediate extensions. $T$ is said to be pruned if it 
has a single root and for every $x \in T$ and every 
$\alpha < |x|_T$ (with $\alpha < |T|)$ there is a $y \in T$ of 
height $\alpha$ with $x <_T y$. 
\end{defn}


In other words, a pruned tree has the property that every element
of the tree has arbitrarily high extensions in the tree. 



If $T$ is a $\kappa$ tree and $\kappa$ is regular, 
then there is a canonical subtree $T'$
of $T$ which is a pruned $\kappa$ tree. Let $T'$ be those $x \in T$
which have $\kappa$ many extension in $T$ (which implies $x$ 
has extensions of arbitrary height). It is easy to check that $T'$
is downward closed subtree of $T$, and that it is pruned (except
it may have more than one root; in that keep only the part of 
$T'$ above a particular root). [To see it is pruned, take $x \in T'$. 
Let $\alpha > |x|_T$. Let $S \subseteq T$ be $\kappa$ many 
extensions of $x$, all of which have height $> \alpha$. $\kappa$ many
elements of $S$ must extend a single $y \in T$ of height $\alpha$. 
Then $y \in T'$.]




Before investigating these trees, we first make the connection
with Suslin's hypothesis. 





\section{Suslin Trees and Suslin's Hypothesis}


The following lemma connects Suslin's hypothesis with Suslin trees.




\begin{lem} ($\zfc$)
There is a Suslin line iff there is a Suslin tree.
\end{lem}


\begin{proof}
Suppose first that $(X,<)$ is a Suslin line. We construct the tree
$T$ out of the intervals $I=(x,y)$ in $X$. Rather than take all 
intervals (which does not give a tree), we pick the intervals
$I_\alpha=(x_\alpha, y_\alpha)$, for $\alpha < \omega_1$,  inductively 
so that they do form a tree. If $I_\beta$ for $\beta < \alpha$
have been defined, let $C= \bigcup_{\beta < \alpha} \{ x_\beta, y_\beta \}$
be the set of endpoints so far constructed. This set is countable, so 
it is not dense in $X$ (recall $X$ is not separable). Let 
$I_\alpha$ be a non-empty interval with $I_\alpha \cap C = \emptyset$. 
Continue to define $I_\alpha$ for all $\alpha < \omega_1$. 
If $\alpha \neq \beta$, then $I_\alpha$ and $I_\beta$ are either
disjoint, or one is contained in the other. Let $T$ be the set
whose elements are the intervals $I_\alpha$ constructed, 
and define $I <_T J$ iff 
$J \subseteq I$. $(T,<_T)$ is easily a tree (note that if 
$I_\alpha$ and $I_\beta$ both contain $J$, and $\alpha < \beta$ 
then $I_\alpha \supseteq I_\beta$. Thus the $<_T$ predecessors
of $J$ are ordered by their indices.). We show that $T$ is a Suslin
tree. An uncountable antichain of $T$ would be an uncountable 
family of intervals of $X$ which are pairwise disjoint, a contradiction
since $X$ is \ccc{} (if $I$, $J$ in $T$ are not disjoint, then 
one contains the other so they are comparable in $T$). 
Suppose there were an uncountable branch, say 
$J_0 <_T J_1 < \dots < J_\alpha < \dots$. If $x_\alpha$ denote the
left endpoint of $J_\alpha$, then the $x_\alpha$ form an $\omega_1$ increasing
sequence from $X$. Then the intervals 
$(x_{2\cdot\alpha},x_{2 \cdot(\alpha+1}))$ are
non-empty, pairwise disjoint, a contradiction. Thus, $T$ is a Suslin tree. 


Suppose next that $T$ is a Suslin tree, and we construct a Suslin line. 
Let $X$ be the set of maximal branches of $T$. We fix an order on $T$
(say by identifying it with $\omega_1$) and order the branches of $T$
lexicographically. This defines the linear ordering $(X,<)$. 
To see it is \ccc{}, suppose $(x_\alpha, y_\alpha)$, $\alpha < \omega_1$
was an $\omega_1$ sequence of pairwise disjoint non-empty 
intervals. Let $z_\alpha \in (x_\alpha,y_\alpha)$. Let $\beta_0$
be the least ordinal $<|z_\alpha|$ such that $x_\alpha(\beta_0) 
\neq z_\alpha(\beta_0)$, and let $\beta_1$ 
be the least ordinal $<|z_\alpha|$ such that $y_\alpha(\beta_1) 
\neq z_\alpha(\beta_1)$. Let $\beta= \max \{ \beta_0,\beta_1\}$. 
Let $a_\alpha= z(\beta) \in T$. Then $\{ a_\alpha \}$ is an 
uncountable antichain in $T$, a contradiction. 

To see $(X,<)$ is not separable, let $A= \{ b_b \}$ be a countable
subset of $X$. Choose $\alpha < \omega_1$ of height greater than
the supremum of the heights of the branches $b_n$. There
is some $z \in T$ of height $\alpha$ which has three distinct
extensions (in fact, $\omega_1$ many) in $T$ (as $T$ is an 
$\omega_1$ tree). This defines a non-empty interval in $X$ 
which contains only branches of length $> \alpha$. Hence, 
this gives a non-empty interval missing $A$, so $A$ is not dense. 


This shows $(X,<)$ is \ccc{} but not separable. From lemma~\ref{lemsusequiv}
this gives a Suslin line. Alternatively, we can modify the tree $T$
directly so that $(X,<)$ as just constructed is dense in itself. 
To do this, first prune $T$ so that, without loss of generality,
every $x \in T$ has extensions to arbitrarily high levels (the pruned
subtree is clearly still a Suslin tree). Then consider levels 
$T_{\alpha_0}$, $T_{\alpha_1}, \dots$ of $T$ such that 
all points of $T$ of level $\alpha_\eta$ have $\omega$ many extensions  
at level $\alpha_{\eta+1}$. This defines a subtree $T'$ of $T$ (the union 
of the points at some level $\alpha_\eta$) which is still an 
$\omega_1$ tree (and thus still a Suslin tree). The tree $T'$
is $\omega$-splitting 
(i.e., every element has infinitely many immediate extensions). 
If we order the extensions of any point of $T'$ in order type 
$\Q$, then $X$ will clearly be dense in itself. We can then take
the completion of $(X,<)$ to get a Suslin line.
\end{proof}




\section{Aronszajn Trees}


Recall an Aronszajn tree is an $\omega_1$ with no $\omega_1$ branch. 
The next lemma shows we can construct them in $\zfc$. 



\begin{lem} ($\zfc$) \label{aron1}
There is an $\omega_1$ Aronszajn tree.
\end{lem}


We'll give two construction of an Aronszajn tree. 

\begin{proof}[first proof]
We construct the tree as a subtree of $\Q^{\omega_1}$.  The
$\alpha^{\text{th}}$ level of the tree will consist of increasing
sequences $t \in \Q^\alpha$ with $\sup(t)$ finite (i.e., $\ran(t)$ is
a bounded set of rationals.). We will have $t <_Y u$ iff $u$ extends
$t$.  We construct the levels of the tree, $T\alpha$ inductively and
will also satisfy $(*)$: for any $t \in T_\alpha$ and any $\beta >
\alpha$ and $q> \sup(t)$, there is a $u \in T_\beta$ with $t <_T u$
and $\sup(u) < q$.

If $T_\alpha$ is defined , we let $T_{\alpha+1}$ consist of all 
$t \conc q$ where $q \in Q$ and $q > \sup(t)$. This clearly 
maintains $(*)$. 

Suppose now $\alpha$ is a limit and $T_\beta$ has been defined for all 
$\beta < \alpha$. For each $t \in T_{< \alpha}= \bigcup_{\beta< \alpha}
T_\beta$ and each $q> \sup(t)$, choose a sequence of ordinals 
$|t|_T < \alpha_0 < \alpha_1 < \dots$ with $\sup_n \alpha_n= \alpha$
and choose rationals $\sup(t) < r_0 < r_1 < \dots$ with 
$\sup_n r_n < q$. By $(*)$, choose then $t <_T t_0 <_T t_1 <_T t_2 <_T \dots$
where $t_i \in T_{\alpha_i}$ and $\sup(t_i)< r_i$. Put then 
$u= \cup t_n$ in $T_\alpha$. Clearly we have maintained $(*)$,
and $T_\alpha$ is countable. Thus, $T$ is an $\omega_1$ tree. 
It clearly has no $\omega_1$ branch, since that would give 
an $\omega_1$ sequence of distinct rationals. 
\end{proof}


\begin{proof}[second proof]
We now give a second construction due to Kunen. 
We will construct a sequence $\{ s_\alpha \}_{\alpha< \omega_1}$
satisfying:
\begin{enumerate}
\item
$S_\alpha$ is a one-to-one function from $\alpha$ to $\omega$. 
\item
If $\alpha < \beta$ then $s_\beta \res \alpha$ agrees with 
$s_\alpha$ except on a finite set. 
\item 
$\omega- \ran(s_\alpha)$ is infinite.
\end{enumerate}
Granting this, we let $T$ be the set of all $s_\alpha \res \beta$
where $\beta \leq \alpha$, that is, all initial segments of 
all of the $s_\alpha$. We order $T$ again by extension. Clearly 
$T$ is a tree. $T$ is an $\omega_1$ tree from property (2), since 
there are countably many $s \in \alpha^\omega$ which agree with 
$s_\alpha$ up to a finite set. From (1) there are clearly no 
$\omega_1$ branches through $T$. 

It remains to construct the $s_\alpha$, which we do by induction. 
For successor steps, let $s_{\alpha+1}=s_\alpha \conc n$ where 
$n \notin \ran(s_\alpha)$. Suppose $\alpha$ is a limit, and let 
$\{ \alpha_n \}$ be an increasing sequence with supremum $\alpha$. 
Begin with $s_{\alpha_0}$. Get $t_{\alpha_1}=s_{\alpha_0} \cup u$ 
where $u$ is the result of changing 
$s_{\alpha_1}$ on a finite subset of $\alpha_1- \alpha_0$ so that 
$t_{\alpha_1}$ is one-to-one. In general, get $t_{\alpha_{n+1}}
=t_{\alpha_n} \cup u$ 
where $u$ is the result of changing $s_{\alpha_{n+1}}$
on a finite subset of $\alpha_{n+1}-\alpha_n$ so that 
$t_{\alpha_{n+1}}$ is one-to-one. We can do this from properties 
(2) and (3). Let $t= \bigcup_n t_{\alpha_n}$, then $t$ satisfies
properties (1) and (2). We can then modify $t$ to get $s_\alpha$
by, for example, changing the values at the $\alpha_n$, say by
$s_\alpha(\alpha_n)=t(\alpha_{2n})$. $s_\alpha$ now satisfies
(1)-(3).
\end{proof}


The second proof modifies to get $\kappa$-Aronszajn trees for 
$\kappa$ a successor of a regular, assuming $\gch$.


\begin{lem}
Let $\kappa=\lambda^+$ where $\lambda$ is regular and 
$2^{< \lambda}= \lambda$. Then there is a $\kappa$ Aronszajn tree. 
\end{lem}


\begin{proof}
We construct $s_\alpha$ for $\alpha< \kappa$ satisfying:
\begin{enumerate}
\item
$S_\alpha$ is a one-to-one function from $\alpha$ to $\lambda$. 
\item
If $\alpha < \beta$ then $s_\beta \res \alpha$ agrees with 
$s_\alpha$ except on a set of size $< \lambda$. 
\item 
$\ran(s_\alpha)$ is non-stationary in $\lambda$.
\end{enumerate}


Granting this, we again let $T$ be the tree os initial segments
of the $s_\alpha$. This is a $\kappa$ tree since for each $\alpha <
\kappa$ there are at most $\lambda^{< \lambda}=2^{< \lambda}=\lambda$
many $s \in \lambda^\alpha$ which agree with $s_\alpha$ except on 
a set of size $< \lambda$. 


We construct the $s_\alpha$ by induction as before. Successor 
steps are trivial. Suppose $\alpha$ is a limit ordinal. We assume
$\cof(\alpha)=\lambda$, as the other case is easier. Fix
$\{ \alpha_i \}_{i < \lambda}$ increasing, continuous, and cofinal in 
$\alpha$. We construct sequence $t_{\alpha_i} \in \lambda^{\alpha_i}$
by induction on $i$ as before. For $i < \lambda$ a limit we
take unions. Properties (1) and (2) are immediate, and (3)
follows since a $< \lambda$ intersection of sets \cub{} in 
$\lambda$ is \cub{} in $\lambda$. 
We let $t_{\alpha_{i+1}}= t_{\alpha_i} \cup u$, where 
$u=s_{\alpha_{i+1}} \res (\alpha_{i+1}-\alpha_i)$, except
we change the values on $< \lambda$ many points of $(\alpha_{i+1}-\alpha_i)$
to get $t_{\alpha_{i+1}}$ one-to-one. Using (2) and (3) and the trivial
fact that every \cub{} subset of $\lambda$ has size $\lambda$, there is no 
problem defining $t_{\alpha_{i+1}}$ (we redefine 
$s_{\alpha_{i+1}} \res (\alpha_{i+1}-\alpha_i)$ on a set of size $< \lambda$
to have values in a \cub{} set which $\ran(t_{\alpha_i})$ misses).
We still clearly have that each $\ran(t_{\alpha_i})$ misses a 
\cub{} subset of $\lambda$, say $C_i$. 

Let $t= \bigcup_{i< \lambda} t_{\alpha_{i+1}}$. $t$ then 
satisfies (1) and (2), and we must 
adjust it to get $s_\alpha$ also satisfying (3). Let 
$\{ \beta_i \}_{i < \lambda}$ be an increasing, continuous 
sequence with $\beta_i \in \bigcap_{j<i} C_j$. Define 
$s_\alpha$ to be $t$, except $t$ takes value $\beta_i$ we define
$s_\alpha$ to take value $\beta_{i+1}$. Clearly $s_\alpha$
then satisfies (3) (since $\{ \beta_i\}_{i \in \text{Limit}}$ is \cub{}). 
$s_\alpha$ still satisfies (2) 
since the modification of $t$ to $s_\alpha$ changes $< \lambda$
many values of $t \res \alpha_i$ for any $i< \lambda$ (since 
$\ran(t \res \alpha_i)$ doesn't contain any $\beta_j$ for $j > i$).
\end{proof}





If we don't assume $\ch$, then there may or may not be $\omega_2$
Aronszajn trees (Mitchell). For $\kappa$ strongly inaccessible,
there is a $\kappa$ Aronszajn tree iff $\kappa$ is weakly compact, a mild
large cardinal axiom (the existence of weakly compact
cardinals is consistent with $V=L$). On the other hand, Jensen showed
that in $L$, there is a $\kappa$ Suslin, hence a $\kappa$ Aronszajn,
tree for all regular $\kappa$ which are not weakly compact. 





\section{Suslin Trees}


Unlike Aronszajn trees, we cannot construct a Suslin tree in $\zfc$. 
We first show that $\Diamond$ implies the existence of a Suslin tree.



\begin{thm}
$\Diamond$ implies that there is  a Suslin tree.
\end{thm}



\begin{proof}
Fix a $\Diamond$ sequence $\{ A_\alpha\}_{\alpha< \omega_1}$. 
We construct the levels of the tree 
$T_\alpha=\{ x \in t \colon |x|_T \leq \alpha \}$ by induction. 
We will have that $T \subseteq \omega_1$. 
We will also maintain that every $x \in T$ has extensions to all 
higher levels.
Let $T_0$ consist 
of just the ordinal $0$. Given $T_\alpha$, let $T_{\alpha+1}$
be defined by extending every $x \in T_\alpha$ to $\omega$ many
immediate extensions in $T_{\alpha+1}$. Suppose now $\alpha$ is 
limit. Let $T_{< \alpha}= \bigcup_{\beta < \alpha} T_\beta$
be the part of the tree so far constructed. If $A_\alpha$ is not
a maximal antichain in $T_{< \alpha}$, then define $T_\alpha$ 
by picking for every $x \in T_{< \alpha}$ a branch $b_x$ of 
$T_{< \alpha}$ of length $\alpha$ containing $x$, and extending 
this branch to a point in $T_\alpha$. 
Suppose now that $A_\alpha$ is a maximal antichain of $T_{< \alpha}$.
We define $T_\alpha$ to ``seal-off'' this antichain, that it, prevent it
from growing further. For each $x \in T_{< \alpha}$, let $b_x$
be a branch of $T_{< \alpha}$ of length $\alpha$ which contains 
$x$ and some element of $A_\alpha$. We can do this since every $x$
is comparable with an element of $A_\alpha$. $T_{\alpha}$
is defined by extending each such $b_x$ to a point of $T_{\alpha}$. 

Let $T= \bigcup_{\alpha < \omega_1} T_\alpha$. Clearly $T$ is 
a pruned $\omega_1$ tree. Suppose $A \subset \omega_1$ is a maximal 
antichain of $T$. Let $C \subseteq  \omega_1$ be \cub{} 
such that for $\alpha \in C$, $T_{< \alpha } \subseteq \alpha$
and $A \cap \alpha$ is a maximal antichain of $T_{< \alpha}$. 
From $\Diamond$, let $\alpha \in C$ be such that $A \cap \alpha
= A_\alpha$. Then at stage $\alpha$ in the construction we defined 
$T_\alpha$ so that all elements of height $\alpha$ extend an
element of $A_\alpha$. This shows that $A \cap \alpha$ is a 
maximal antichain of $T$, so $A = A \cap \alpha$, and thus $A$ is countable.
\end{proof}




\begin{cor}
It is consistent with $\zfc$ that there is a Suslin line. 
\end{cor}






Constructing $\kappa$-Suslin trees for higher regular (non weakly compact)
cardinals requires more that $\Diamond_\kappa$. However, 
it is easier to force directly the existence of these trees. 
In fact, this was the original argument of Jech and Tennenbaum. 
To get a Suslin tree we can force with either countable trees (Jech) or 
finite trees (Tennenbaum). We sketch both proofs. The first 
proof works for all regular cardinals as well. 



For the first proof ($\kappa$ now a regular cardinal of $M$), 
let the partial order $\bP$ consist of 
pruned trees $T$, $|T| , \kappa$, 
of height $\alpha+1$ for some $\alpha < \kappa$
(i.e., for any $x \in T$ has an extension to the highest level $\alpha$
of $T$). 
For convenience we also require $T$
to be splitting, and 
we assume also 
$T \subseteq \kappa$, that is, the elements of $T$ are  
ordinals less than $\kappa$. 
We define $T_1 \leq T_2$ iff $|T_1| \geq |T_2|$ and 
$T_1 \res |T_2| = T_2$ (here $T \res \beta$ denotes the elements of $T$
of height $< \beta$ in $T$). Thus, $T_1$ must extend $T_2$
``vertically.'' 


$\bP$ is countably closed, but not in general $< \kappa$ closed
(the problem is with the pruned condition; an increasing union
of conditions of length $\omega_1$ may fail to be extendible 
to a condition as there may be no branches cofinal in the union).  
However, $\bP$ is $< \kappa$ distributive, which is enough to get that 
$\bP$ preserves all cofinalities and cardinalities $\leq \kappa$. 
To see this, let $\{ D_\eta\}_{\eta< \rho}$, $\rho < \kappa$, be a $< \kappa$
collection of dense sets in $\bP$.  We define conditions 
$p_\eta$ of height $\alpha_\eta+1$ inductively. We will have 
$p_0 \geq p_1 \geq \dots$. As we define $p_\eta$ we will also 
define for each $x \in p_\eta$ a  function $f_x$ which gives
a brach of $p_\eta$ containing $x$ of height $\alpha_\eta +1$. 
If $x \in p_{\eta_1} \geq p_{\eta_2}$, then we will have that 
the $f_x$ functions are compatible. At successor steps, if $p_\eta$ 
is defined we let $p_{\eta+1} \in D_{\eta+1}$ be any extension of $p_\eta$ of 
some successor height $\alpha_{\eta+1}+1 > \alpha_\eta+1$, 
and extend all of the $f_x$ function for $x \in p_\eta$ as well
as define the $f_x$ functions for $x \in p_{\eta+1}-p_\eta$. 
There is no problem doing this as $p_{\eta+1}$ extends $p_\eta$
and is pruned. For $\eta$ limit, let $\beta= \sup \{ \alpha_{i} \colon 
i < \eta \}$. Let $T = \bigcup_{i < \eta} p_i$. Our branch functions
define for each $x \in T$ a branch $f_x$ of $T$ of height 
$\beta$. Let $T' \leq T$ have height $\beta+1$ and obtained by
extending each branch $f_x$ to level $\beta+1$ of $T'$. $T'$
is now a condition in $\bP$. Let $p_{\eta} \in D_\eta$ extend $T'$,
and extend the branch fuctions of $T'$ appropriately. Continuing, 
we define a condition $p_\rho$ which extends conditons in 
all of the $D_\eta$. Thus, $\bigcap_{\eta< \rho} D_\eta$ is dense,
so $\bP$ is $< \kappa$ distributive. 




Let $G$ be $M$ generic for $\bP$, where 
$M$ is a transitive model of $\zfc$. We may identify $G$ with a 
pruned $\kappa$ tree ($G$ has height $\kappa$ since any condition
$T$ can be extended to a condition $T'$ of height $\alpha+1$ for any 
$|T| \leq \alpha+1 < \kappa$).

We claim that $G$ is a $\kappa$-Suslin tree. Suppose $\tau \in M^\bP$ and 
$T_0 \forces (\tau$ is a maximal antichain of $\dot{G})$. Let 
$D \subseteq P$ be those conditions $T$ such that for some 
$A \subseteq T$ we have
\begin{enumerate}
\item
$A$ is a maximal antichain of $T$.
\item
$\sup \{ |a| \colon a \in A\} < |T|$ (i.e., there is a level of $T$
such that all elements of $A$ are below that level).
\item
$T \forces (\check{A} \subseteq \tau)$. 
\end{enumerate}
We claim that $D$ is dense below $T_0$. For let $T \leq T_0$. 
As $\bP$ is $< \kappa$ distributive, we may get $T_1 \leq T$ such that 
for all $x \in T_0$, there is a $a \in T_1$ such that 
$x$ is compatible with $a$ and $T_1 \forces (a \in \tau)$. 
In general, define $T_{n+1} \leq T_n$ so that for all $x \in T_n$, 
there is a $a \in T_{n+1}$ such that 
$x$ is compatible with $a$ and $T_{n+1} \forces (a \in \tau)$. 
Let $T = \bigcup_n T_n$. Then there is a maximal antichain $A$ of 
such that $T \forces (A \subseteq \tau)$. Extend $T$ to $T'$
of height $|T|+1$ as follows. For each $x \in T$, let $b_x$ be 
a branch of $T$ containing $x$ and an element of $A$, with $b_x$
of height $|T|$. For each $x \in T$, put a point in $T'$ which
extends all the elements of $b_x$ (i.e., extend the 
branch $b_x$). This defines $T'$, and we have $T' \in D$. 
Thus, $D$ is dense in $\bP$. 
Let $T \in G \cap D$. Let $A \subseteq T$ witness $T \in D$. 
We must have $A=\tau_G$, since if $T' \leq T$ and $x \in 
T' -T$, then $x$ is above some element of $A$. Thus, $\tau_G=A$
has size $< \kappa$  in $M[G]$. This shows $G$ is a Suslin tree.




\begin{cor}
Let $M$ be a transitive model of $\zfc$ and $\kappa$ a regular
cardinal of $M$. Then there is a $\kappa$-distributive
forcing (hence preserves all cofinalities and cardinalites $\leq \kappa$)
such that in $M[G]$ there is a $\kappa$-Suslin tree.
\end{cor}





The second proof uses finite trees. $\bP$ now
consists of finite trees $T \subseteq \omega_1$ satisfying:
if $\alpha <_T \beta$ then $\alpha < \beta$. We define 
$T_1 \leq T_2$ iff $<_{T_1} \res (T_2 \times T_2) = <_{T_2}$. 
We again identify a generic $G$ with a tree $G$ on $\omega_1$ (to
see it is a tree, note that if $\alpha \in G$ then the $<_G$
predecessors of $\alpha$ are $<_G$ ordered in their usual order
as ordinals, hence the $<_G$ predecessors are well-ordered). 

First we show that $\bP$ is \ccc{} If $\{ T_\alpha \}_{\alpha< \omega_1}$
were an antichain, then by the $\lD$ system lemma we may assume
that each $T_\alpha$ consists of a root $R$ and a set $A_\alpha= 
\{ a_\alpha^1,\dots,a_\alpha^n\}$
(of some fixed size $n$),
where the $A_\alpha$ are pairwise disjoint. We may further assume that
the $T_\alpha$ orderings on the root $R$ are all the same. Further,
we may assume that for $r \in R$, $r <_{T_\alpha} a_\alpha^k$ 
iff $r <_{T_\beta} a_\beta^k$ for all $\alpha, \beta$. We may also assume that
$a_\alpha^k <_{T_\alpha} a_\alpha^l$ iff 
$a_\beta^k <_{T_\beta} a_\beta^l$ for all $k,l \leq n$ and all $\alpha, \beta$.
Thus, $T_\alpha$ and $T_\beta$ look the same except for the values of the
ordinals in $A_\alpha$, $A_\beta$. However it is now easy to get
a common extension of any two of the $T_\alpha$ (e.g., the union of
$T_\alpha$ and $T_\beta$ is now a condition). 

We show that $G$ has no uncountable antichain (from which it also
follows that $G$ is an $\omega_1$ tree (for another argument, see
the exercise below). Suppose $T \forces (\tau$ is an uncountable
antichain of $\dot{G})$. Get an $\omega_1$ sequence $T_\alpha$
of conditions extending $T$ and ordinals $\eta_\alpha \in T_\alpha$
with $T_\alpha \forces (\check{\eta}_\alpha \in \tau)$, and
the $\eta_\alpha$ are distinct. Thin the $T_\alpha$ to a $\lD$
system as above, $T_\alpha= R \cup A_\alpha$. It is easy to see that for
any $\alpha \neq \beta$ we can get a common extension of 
$T_\alpha$ and $T_\beta$ in which $\eta_\alpha$ is comparable with 
$\eta_\beta$, a contradiction. 




\begin{cor}
The existence of a Suslin tree is consistent with $\zfc + \neg \ch$.
In particular, the existence of a Suslin tree does not imply $\Diamond$.
\end{cor}



\section{Kurepa Trees}


Recall a Kurepa tree is an $\omega_1$ tree with at least $\omega_2$
branches of length $\omega_1$. We can give an easy reformulation of
this which does not mention trees. 






\begin{lem} \label{lemkurfamily}
There is a Kurepa tree iff there is a family $\sF$ of subsets of 
$\omega_1$ satisfying:
\begin{enumerate}
\item
$|\sF| \geq \omega_2$.
\item
$\forall \alpha < \omega_1\ |\{ A \cap \alpha \colon A \in \sF \}|
\leq \omega$.
\end{enumerate}
\end{lem}


We call a family $\sF$ as in lemma~\ref{lemkurfamily} a {\em Kurepa}
family.


\begin{proof}
Assume first that $T$ is a Kurepa tree. Without loss of generality
we may assume $T \subseteq \omega_1$ and if $\alpha <_T \beta$ then 
$\alpha < \beta$. Then $\sF=$ the set of $\omega_1$ branches through
$T$ is a Kurepa family (note that ib $b$ is a branch through $T$,
then $b \cap \alpha$ is determined by the $\alpha^{\text{th}}$
level of $b$). 

Conversely, assume $\sF$ is a Kurepa family. Let $T$ be the subtree of 
$2^{< \omega_1}$ consisting of all initial segments of characteristic
functions of $A \in \sF$. Easily $T$ is a Kurepa tree (note that the 
element of $T$ of height $\alpha$ correspond to the elements $A \cap \alpha$
for $A \in \sF$). 
\end{proof}


Just as $\Diamond$ implies the existence of a Suslin tree, there is a
combinatorial principle $\Diamond^+$ which implies the existence of
a Kurepa tree. $\Diamond^+$ implies $\Diamond$, however the existence
of a Kurepa tree does not imply the existence of a Suslin tree. 
Although we show here the consistency of the existence of Kurepa
tree directly by forcing, we state the principle $\Diamond^+$. 
We note also that $\Diamond^+$, like $\Diamond$ holds in $L$. 



\begin{defn}
$\Diamond^+$ is the statement that there is a sequence 
$\{ \sA_\alpha \}_{\alpha< \omega_1}$, where each $\sA_\alpha$ is a 
countable family of subsets of $\alpha$, such that for all 
$A \subseteq \omega_1$, there is a \cub{} $C \subseteq \omega_1$
such that for all $\alpha \in C$ we have $A \cap \alpha \in \sA_\alpha$
and $C \cap \alpha \in \sA_\alpha$.
\end{defn}


In view of theorem~\ref{diamondreform}, it is clear that 
$\Diamond^+$ implies $\Diamond$. 


\begin{thm}
Let $M$ be a transitive model of $\zfc +\ch$. Then there is a 
countably closed $\bP \in M$ such that if $G$ is $M$-generic for
$\bP$ then $M[G]$ satisfies that there is Kurepa tree. 
\end{thm}




\begin{proof}
$\bP$ consists of pairs $(T,f)$ where $T$ 
is a pruned countable subtree of $2^{< \omega_1}$
of height $\alpha< \omega_1$, and $f$ is a function with domain a 
countable subset of $\omega_2$ such that for $\alpha \in \dom(f)$, 
$f(\alpha)$ is a branch through $T$. We say $(T_1,f_1) 
\leq (T_2,f_2)$ if $T_1 \res |T_2| =T_2$ (i.e., $T_1$ extends
$T_2$ vertically), $\dom(f_2) \subseteq \dom(f_1)$, and 
for all $\alpha \in \dom(f_2)$, $f_1(\alpha)$ extends $f_2(\alpha)$ (i.e.,
$f_1$ extends all of the branches of $f_2$, and may give new ones as well).

Clearly $\bP$ is countably closed. Let $T$ be the tree produced by the
generic, and $F$ the function produced (in the obvious manner). 
Thus, $F$ is a map from $\omega_2^{M}$ to the length $\omega_1$
branches of $T$ (note: $\omega_1^M=\omega_1^{M[G]}$). 
It is easy to see that for a generic $G$, the resulting 
function $F$ will also be one-to-one (we may extend any 
$(T,f)$ with $\alpha, \beta \in \dom(f)$ to a $(T',f')$
where $f'(\alpha) \neq f'(\beta)$). Thus, in $M[G]$ the $\omega_1$ tree
$T$ has $\geq \omega_2^M$ branches of length $\omega_1$. 
We show finally that $\bP$ is $\omega_2$-\cc{} in $M$, which 
shows that $\omega_2^M=\omega_2^{M[G]}$ and completes the 
proof.


Suppose $\{ (T_\alpha,f_\alpha)\}_{\alpha < \omega_2}$ were an
antichain of $\bP$.  We may assume that all of the trees have the same
height $\beta < \omega_1$. By $\ch$ in $M$, there are
$2^\beta=\omega_1$ many trees of height $\beta$, so we may assume that
all of the $T_\alpha$ are equal to a fixed tree $T_0$. Again using
$\ch$, we may thin the antichain so the $\dom(f_\alpha)$ form a $\lD$
system on $\omega_2$, say $\dom(f_\alpha)=R \cup A_\alpha$ where the
$A_\alpha$ are pairwise disjoint. We may assume that that the
$f_\alpha$ all agree on the root $R$, as there are only
$\omega_1^\omega= 2^\omega=\omega_1$ many choices for $f \res R$.  At
this point, any two members of the antichain are compatible, a
contradiction.
\end{proof}




\section{A Model in which there are no Kurepa Trees}



Starting with a model $M$ of $\zfc+$ there is an inaccessible cardinal,
we produce a generic extension $M[G]$ in which there are no Kurepa
trees. The inaccessible cardinal is necessary since if $M$ satisfies
$\zfc+$ there are no Kurepa trees then $\omega_2^M$ is inaccessible
in $L$ [Work in $M$. If $\omega_2$ is not inaccessible in $L$, then 
$\omega_2= (\omega_2)^{L[A]}$ for some $A \subseteq \omega_1$. 
However $\Diamond^+$ holds in any $L[A]$ for $A \subseteq \omega_1$.
Thus there is a Kurepa tree in $L[A]$, and this remains a Kurepa tree
in $L[A]$ as $\omega_2= (\omega_2)^{L[A]}$.]


 
To motivate the forcing, note that if $T$ is a Kurepa tree, then $T$
will remain a Kurepa tree in any larger model unless 
$\omega_2$ is collapsed in the larger model. Conversely, collapsing
$\omega_2$ by a countably closed forcing 
will kill the Kurepa trees of the ground model (by lemma~\ref{nnb}), 
but may introduce
new Kurepa trees, so it will be necessary to collapse the new $\omega_2$,
etc.\ This suggests we collape to $\omega_1$ all the ordinals below some
large cardinal. 



\begin{defn}
Let $\kappa$ be a regular cardinal. The Silver collapse of 
$\kappa$ to $\omega_2$ is the forcing $\bP$ consisting of functions
with domain a countable subset of
$\{ (\alpha, \beta) \colon \alpha < \kappa \wedge \beta < \omega_1 \}$
and $f(\alpha, \beta) < \alpha$ for all $(\alpha,\beta) \in \dom(f)$.
\end{defn}



It is clear that if $g$ is generic for $\bP$, then 
$(|\kappa| \leq \omega_2)^{M[G]}$, as in $M[G]$ all ordinals $\alpha < \kappa$
are onto images of $\omega_1$. It is also clear that $\bP$ is countably
closed, so $\omega_1$ is preserved in forcing with $\bP$. 



\begin{lem} \label{silcc}
Let $\kappa$ be a strongly inaccessible cardinal of $M$. 
Then $\bP$ is $\kappa$-c.c.{} Thus, $\kappa$ is a cardinal 
of $M[G]$, and hence $\kappa= \omega_2^{M[G]}$. 
\end{lem}


\begin{proof}
Suppose $\{ p_\alpha \}_{\alpha< \kappa}$ were an antichain of size $\kappa$. 
Let $d_\alpha= \dom(p_\alpha)$. We can view $d_\alpha$ as a countable
subset of $\kappa$. We use the $\lD$-system argument. 
We may assume all the $d_\alpha$ has order-type $\tau< \omega_1$. 
Let $\eta(\beta)= \sup\{ d_\alpha(\beta) \colon \alpha < \kappa \}$. 
There must be a least $\beta_0 < \tau$ such that $\eta(\beta_0) 
= \kappa$ [otherwise there is an $\eta < \kappa$ such that 
$d_\alpha \subseteq \eta$ for all $\alpha < \kappa$. Using 
$\kappa$ strongly inaccessible this gives $< \kappa$ many possibilities
for the $p_\alpha$.] We may then thin the $\{ p_\alpha\}$
sequence so the $d_\alpha$ form a $\lD$-system with root $R \in \kappa^\tau$.
There are $< \kappa$ many possibilities for $p_\alpha \res R$,
using again the inaccessibilty of $\kappa$. So we may assume 
$p_\alpha \res R$ is constant, and this gives a contradiction
to the $p_\alpha$ being an antichain. 
\end{proof}





\begin{lem} \label{nnb}
Let $\bP$ be a countably closed forcing in $M$. If $T \in M$ is 
an $\omega_1$ tree of $M$, then any branch of $T$ in $M[G]$
lies in $M$. 
\end{lem}


\begin{proof}
Suppose $\tau \in M^\bP$ and $p \forces (\tau$ is a branch of $\check{T}
\wedge \tau \notin M)$. We define conditions $p_s$ for $s \in 2^{< \omega}$
and also $x_s \in T$. Let $p_{\emptyset}=p$ and $x_0$
be the root of $T$. Given $p_s$ and $x_s$, let $p_{s \conc 0}$
and $p_{s \conc 1}$ extend $p_s$ and $x_{s \conc 0}$, $x_{s \conc 1}$
be two extensions of $x_s$ in $T$ which are incompatible in $T$, and with
$p_{s \conc i} \forces x_{s \conc i} \in \tau$. We can do this
as otherwise $p_s$ determines the branch $\tau_G$. Let $\alpha < \omega_1$
be greater than the heights of all the $x_s$ in $T$. For each $r 
\in 2^\omega$, let $p_r$ extend all of the $p_s$ for $s$ an initial segment of
$r$, and (extending $p_r$ if necessary), let $x_r \in T$ have height 
$\alpha$ with $p_r \forces \check{x}_r \in \check{T}$ (we can do this
as $p$ forces that $\tau$ has elements of all heights $\alpha < \omega_1$,
as otherwise some $q \leq p$ would determine $\tau_G$.) We clearly have that
the $\{ x_r\}$ are distinct elements of $T$ of height $\alpha$, contradicting
$T$ being an $\omega_1$ tree. 
\end{proof}



\begin{thm}
Let $M$ be a transitive model of $\zfc$ and $\kappa$ an inaccessible
cardinal of $M$. Let $\bP \in M$ be the Silver collapse of $\kappa$
to $\omega_2$ as defined in $M$. Then if $G$ is $M$-generic for
$\bP$, $M[G]$ satisfies that there are no Kurepa trees. 
\end{thm}



\begin{proof}
Suppose $T=\tau_G \in M[G]$ and $(T$ is a Kurepa tree$)^{M[G]}$. 
We may assume $T \subseteq \omega_1^{M[G]}=\omega_1^M$. 
Let $\sigma$ be a nice name for $T$, that is $\tau_G=\sigma_G$ and
$\sigma$ is of the form $\bigcup_{\alpha<\omega_1}\{ \check{\alpha} \}
\times A_\alpha$ where $A_\alpha$ is an antichain of $\bP$. 
From lemma~\ref{silcc} it follows that $|\sigma| < \kappa$. 
For any $\lambda < \kappa$ we may write $\bP= \bP^{\leq \lambda} 
\times \bP^{> \lambda}$ where 
$\bP^{\leq \lambda}$ consists of those $p \in \bP$ whose domain
consists only of pairs $(\alpha,\beta)$ where $\alpha \leq \lambda$,  
and $\bP^{> \lambda}$
those $p$ whose domain consists only of pairs $(\alpha, \beta)$
with $\alpha > \lambda$. Let $\lambda< \kappa$ be large 
enough so that $\trcl(\sigma) \cap \on \subseteq \lambda$. 
Write $G=G^{\leq \lambda} \times G^{> \lambda}$. Then $T=\sigma_G
=\sigma_{G^{\leq \lambda}} \in M[G^{\leq \lambda}]$. From lemma~\ref{nnb}
there are at most $(2^{\omega_1})^{M[G^{\leq \lambda}]}$ many 
branches of $T$ in $M[G]$. Since $\kappa$ is inaccessible,
a simple name counting argument shows that 
$\rho=(2^{\omega_1})^{M[G^{\leq \lambda}]} < \kappa$. However, 
$\rho$ has cardinality $\omega_1$ in $M[G]$, as forcing with 
$\bP^{> \lambda}$ clearly collapses $\rho$ to cardinality $\omega_1$.
thus $T$ has $\leq \omega_1$ many branches in $M[G]$.
\end{proof}






\end{document}
