% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\newcount\probno
\probno=0
\def\prob#1{\advance\probno by 1 \par \bigskip
    \noindent\the\probno . (#1)}

\def\dex#1{{\it #1 }}
\def\famc{{\mathcal C}}
\def\famf{{\mathcal F}}
\def\kk{{\mathcal K}}
\def\ll{{\mathcal L}}
\def\mm{{\mathcal M}}
\def\om{{\omega}}
\def\pp{{\mathcal P}}
\def\proves{{\vdash}}
\def\qq{{\mathbb Q}}
\def\reals{{\mathbb R}}
\def\rmiff{\mbox{ iff }}
\def\sent{{\mathcal S}}
\def\su{{\subseteq}}

\begin{document}

\begin{flushright}
A.Miller\\
M771\\
Fall 2010
\end{flushright}

Homework problems are due in class one week from the day assigned
(which is in parentheses).



\prob{1-22 F} (Tarski) Suppose $A$ is an infinite Dedekind finite set.
For $n\in\om^+$ define
$A_n=\{s:n\to A\;\;:\;\; s \;\;1-1\}.$
Prove that

(a) $A_n$ is Dedekind finite.

(b) For $X\su \om$ the set $A_X=\bigcup_{n\in X}A_n$ is Dedekind finite.


(c) There is a 1-1 map of $A_n$ into $A_m$ iff $n\leq m$.


(d) If $X\su Y\su \om^+$ and there is a 1-1 map of $A_X$ into $A_Y$,
then $X=Y$.

(e) Show that if there is an infinite Dedekind finite cardinal then
there are continuum many distinct infinite Dedekind finite cardinals.

\def\al{\alpha}
\def\be{\beta}
\def\ka{\kappa}

\prob{1-22 F} (a) Suppose $L$ is a linear order and
for every $X\su L$ either $X\simeq L$ or $\overline{X}\simeq L$.
(Overline denotes the complement.)

(b) Suppose $\al$ is ordinal. Show that (1) and (2) are equivalent.


(1) $X\simeq \al$ or $\overline{X}\simeq \al$ for every  $X\su \al$.

(2) There is a $\be$ with $\al=\om^\be$.

\prob{1-27 W} Prove that the following are equivalent:

(1) There exists infinite sets $(A_\al\su \om_1: \al<\om_2)$ 
which are pairwise almost
disjoint, i.e., $A_\al\cap A_\be$ is finite whenever $\al<\be<\om_2$.

(2) CH is false.


\prob{2-1 M} (Solomon) Prove that if ${\mathfrak b}>\om_1$ and
$\{a_\al\in[\om]^\om:\al<\om_1\}$ are almost disjoint, then
there exists $a\in [\om]^\om$ with $a\cap a_\al$ finite
for every $\al<\om_1$.

\prob{2-5 F} (a) Let $\ka>\om$ be a regular cardinal. Prove
that for every $(F_\al\in [\ka]^{<\om}\;:\; \al<\ka)$ there
exists $\Sigma\in [\ka]^{\ka}$ such that
$(F_\al\in [\ka]^{<\om}\;:\; \al\in \Sigma)$ is a $\Delta$-system.
(b) Show that this fails for singular $\ka$.

\prob{2-8 M} Assume MA$_{\om_1}$.  Prove that there
exists $(A_\al\in [\om_1]^{\om_1}\;:\;\al<\om_2)$ such that
$A_\al\cap A_\be$ is finite for every $\al<\be<\om_2$.


\def\poset{{\mathbb P}}
\prob{2-10 W} Prove that MA$_{\om_1}$ is equivalent to:
\par For every ccc $\poset$ and $(E_\al\su \poset:\al<\om_1)$ 
there exists a $\poset$-filter $G$ such that for
every $\al<\om_1$ either $G\cap E_\al$ is nonempty or
there exists $p\in G$ such that no $q\leq p$ is in $E_\al$.

\def\aa{{\mathcal A}}

\prob{2-12 F} Assume MA$_{\om_1}$.  Prove there exists
an almost disjoint family $\aa\su [\om]^\om$ of size 
$\om_1$ such that for every $\aa_0\su \aa$ there exists
$b\su\om$ such that $a\su^* b$ for all $a\in \aa_0$
and 
$a\su^* \overline{b}$ for all $a\in \overline{\aa_0}$.

\def\res{\upharpoonright}

\prob{2-17 W} Let $T\su \om^{<\om_1}$ be a Souslin subtree.

(a) Suppose $f:T\to\reals$ satisfies
$$\forall s,t\in T\;\; (s\su t \to f(s)\leq f(t))$$
Prove that the range of $f$ is countable.

(b) Suppose $f:T\to\reals$  is continuous. This
means that for any $s\in T_\lambda$ for $\lambda$ limit,
$f(s\res\al_n)$ converges to $f(s)$ for 
any sequence $\al_n$ converging up to $\lambda$.
Prove that the range of $f$ is countable.

\prob{2-19 F} Suppose $(C_\al\;:\;\al<\om_1)$ is a ladder system.
Show that for every $\Sigma\in [\om_1]^{\om_1}$ there exists
$\Gamma\in [\Sigma]^{\om_1}$ such that $(C_\al\;:\;\al\in\Gamma)$
is a $\Delta$-system.

\prob{2-19 F} (MA$_{\om_1}$)
Suppose $(C_\al\;:\;\al<\om_1)$ is a ladder system. Prove
that for every $(f_\al:C_\al\to\om\;:\;\al<\om_1)$ there
exists $F:\om_1\to\om$ such that $F\res C_\al=^*f_\al$ for
every $\al<\om_1$.

\prob{2-22 M} Suppose $T\su (\om+\om^*)^{<\om_1}$ is a subtree which is
an Aronszajn tree and which has the property that
for every $s\in T$ all immediate successors of $s$ are in $T$.
Let $(T,\unlhd)$ be the following ordering:

\noindent $s\lhd t$ iff either 
\begin{enumerate}
\item there exists $\al<|s|,|t|$ such
that $s\res \al=t\res\al$ and $s(\al)<t(\al)$ or
\item $s\subset t$ with $|s|=\al<|t|$
and $t(\al)\in\om^*$.
\end{enumerate}
Prove:

(a) $(T,\unlhd)$ is a dense linear order.

(b) Neither $\om_1$ nor $\om_1^*$ order embed into $(T,\unlhd)$.

(c) If $X\su\reals$ and $X$ order embeds into $(T,\unlhd)$, then
$X$ is countable.

\prob{2-26 F} For $A\su\om_1$ define the following linear
order type, $$L_A=\sum_{\al<\om_1}L_A^\al.$$
$$L_A^\al=\left\{
\begin{array}{ll}
\eta & \mbox{if } \al\notin A\\
1+\eta & \mbox{if } \al\in A\\
\end{array}\right.$$
Here $\eta$ stands for the order type of the rationals.
Prove
$$L_A\simeq L_B\rmiff (A\Delta B) \mbox{ is nonstationary}.$$


\prob{3-1 M} Assume $\Diamond$. Prove there exists a rigid
Souslin tree.

\prob{3-3 W} Suppose there exists $(S_\al\su\al:\al<\om_1)$ such
that for every $X\su\om_1$ there exists a limit ordinal $\al<\om_1$
with $X\cap \al=S_\al$.  Prove that there exists a diamond sequence.

\prob{3-5 F} Let $\al>\om$ be a limit ordinal.  Prove
that $(V_\al,\in)$ is a model of ZFC minus the replacement
axiom.  Prove that $(V_{\om+\om},\in)$ does not model ZFC.

\prob{3-8 M} Let $\ka$ be an uncountable regular cardinal.
Prove that $(H_\ka,\in)$ is a model of ZFC minus the power set axiom.

\prob{3-10 W} Let ZC=ZFC minus the replacement axioms.  Prove
that (ZC plus the reflection schema) implies the replacement axioms.

\prob{3-12 F} (Kumar) Prove that the Mostowski collapse of OD is HOD,
if
$$f(x)=\{f(y):y\in x\cap OD\}$$
then $HOD=\{f(x):x\in OD\}$.
\prob{3-15 M} Let $M,N$ be standard models of ZFC with same ordinals
and sets of ordinals.  Prove that $M=N$.

\def\lam{\lambda}

\prob{3-17 W} Suppose that $M\su N$ are standard models of
ZF and $\ka,\lam\in M$.  Prove that if $N\models \ka\to(\om)^{<\om}_\lam$,
then $M\models \ka\to(\om)^{<\om}_\lam$.

\prob{3-19 F} (Kumar) Say that a limit ordinal $\al$ is weakly-reflecting
iff for any sentence $\theta$ if $V_\al\models\theta$, then
there are unboundedly many $\be<\al$ such that $V_\be\models\theta$.
Prove that the set $\{\al<\om_1\;:\;\al$ is not weakly-reflecting$\}$
is not stationary.  Hence ZC+weakly reflecting does not imply ZFC.

\prob{3-22 M} Suppose that $\ka$ is a strongly inaccessible cardinal.
Prove that $V_\ka$ is a model of ZFC.   Prove that $V_\ka=H_\ka$.

\prob{3-22 M} Prove that the least $\ka$ (if it exists) such
that $V_\ka$ is a model of ZFC is a strong limit cardinal with
countable cofinality.

\prob{3-24 W} Assume ZFC+V=L. Prove that for any regular
$\ka$ that $L_\ka=H_\ka$.

\prob{3-26 F} Assume ZFC+V=L. For any regular cardinal $\ka>\om$ let
$$Q_\ka=\{\al<\om_1\;:\; L_\al \equiv L_\ka\}.$$
Prove that $Q_\ka$ is unbounded in $\om_1$ and
$Q_\ka$ is stationary iff $\ka=\om_1$.

\prob{4-6 M} Assume ZFC+V=L.  Let $\ka$ be an uncountable regular cardinal.
Let $N$ be the elements of $L_\ka$ which are definable in $L_\ka$ without
parameters.  Prove that $N$ is a countable elementary 
substructure of $L_\ka$.
Let $\al$ be minimal such that $L_\al\equiv L_\ka$.  Prove
that $Th(L_\ka)\notin L_\al$.

\def\ga{\gamma}

\prob{4-16 F} ($M$ a countable standard transitive model of ZFC.)
Suppose $G$ is $\poset$-generic over $M$ and for every
$f\in M[G]$
if $M[G]\models f:\ka\to\ga$ where $\ka$ and $\ga$ are ordinals,
there exists $g\in M$ such that $M\models g:\ka\to[\ga]^\om$ with 
$f(\al)\in g(\al)$ for every $\al<\ka$. Prove that there exists 
$p\in G$ such that $M\models \poset_{\leq p}$ is ccc.


\prob{4-23 F}
Suppose $M\models \poset_1\su \poset$ is a dense suborder. Prove
\begin{enumerate}
\item If $G_2$ is $\poset_2$-generic over $M$, then
$G_1=G_2\cap\poset_1$ is $\poset_1$-generic over $M$.
\item If $G_1$ is $\poset_1$-generic over $M$, then
$G_2=\{p\in\poset_2:\exists q\in G_1\;\; q\leq p\}$ is 
$\poset_2$-generic over $M$.
\item In either case, $M[G_1]=M[G_2]$.
\end{enumerate}

\prob{4-23 F}  Prove that if $\poset$ is a countable poset which
is everywhere non-trivial ($\forall p\in\poset\;\exists q_1,q_2\leq p
\;\; q_1\perp q_2$), then $\om^{<\om}$ is isomorphic to a dense
subset of $\poset$.

\prob{4-26 M} Suppose there is a standard model of ZFC.  Prove
there exists a countable standard model $M$ such that
$$M\models ZFC+\forall n<\om\;\; ZFC_n\mbox{ has
a standard model}$$
 but $M\models$``$ZFC\mbox{ does not have
a standard model}$''.
\end{document}


