% 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\power(#1){{\mathcal P}(#1)}
\def\om{{\omega}}
\def\pp{{\mathcal P}}
\def\uu{{\mathcal U}}
\def\aa{{\mathcal A}}
\def\poset{{\mathbb P}}
\def\proves{{\vdash}}
\def\qq{{\mathbb Q}}
\def\reals{{\mathbb R}}
\def\rmiff{\mbox{ iff }}
\def\su{{ \;\subseteq \;}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\de{\delta}
\def\ka{\kappa}
\def\cc{{\mathfrak c}}
\def\res{{\upharpoonright}}
\def\ff{{\mathcal F}}
\def\sm{{\setminus}}

\begin{document}

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

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

\prob{1-19 W}
Prove that for ordinals if $0<\al\leq \be$, then there
are unique $\ga,\de$ with $\be=\al\cdot\ga+\de$ and $0\leq \de<\al$.

\prob{1-19 W}[Kunen]
Prove that if $\al$, $\be$ are non-zero ordinals, then
there is a largest ordinal which divides both of them.
Here, $\de$ divides $\al$ iff $\al = \de \xi$
for some $\xi$.

\prob{1-21 F} Prove that there are unboundedly many cardinals
$\ka$ with $\aleph_\ka=\ka$.

\prob{1-24 M} Prove that $[\aleph_\om]^{\om}$ has cardinality
strictly larger than $\aleph_\om$.
$$[X]^\ka=\{A\su X\;:\; |A|=\ka\}.$$

\prob{1-24 M} Assume the continuum hypothesis.  Prove
that $[\aleph_n]^{\om}=\aleph_n$ for every $n$ with $1\leq n<\om$.

\prob{1-26 W} Suppose for all $n<\om$ that $2^{\aleph_n}=\aleph_{n+1}$.
Prove that
$\aleph_\om^\om=2^{\aleph_\om}$.

\prob{1-26 W} Suppose there exists $\al$ such that
for all $n<\om$ that $2^{\aleph_n}=\aleph_{\al}$.  Prove that
$2^{\aleph_\om}=\aleph_{\al}$.

\prob{1-28 F} Let INV stand for the property that
every onto function has an inverse, i.e., if $f:A\to B$ is
onto, then there exists $g:B\to A$ such that $f(g(b))=b$ for
every $b\in B$.   Prove that INV is equivalent to AC (the axiom
of choice).

\prob{1-28 F} Prove there exists a 
pairwise disjoint family $\{X_\al\;\su\; 2^\om\;:\;\al<\cc\}$ of
Bernstein sets.

\prob{1-28 F}
Prove there exists a 
family $\{X_\al\;\su \;2^\om\;:\;\al<2^\cc\}$ of
Bernstein sets which are distinct, i.e., $X_\al\neq X_\be$ whenever
$\al\neq\be$.


\prob{1-31 M} 
Prove there exists a subset $X$ of the plane which meets every
line in exactly two points.

\prob{2-4 F}
Assume MA.  Prove there exists $(f_\al\in\om^\om\;:\;\al<\cc)$ such
that
\par (a) $\al<\be<\cc$ implies $f_\al<^* f_\be$
\par (b) for every $g\in\om^\om$ there exists $\al<\cc$ such
that $g<^*f_\al$


\prob{2-7 M}
Assume MA.  Prove there exists an ultrafilter
$\uu\su[\om]^\om$  such
that for every $f\in\om^\om$ there exists $X\in\uu$ such
that $f\res X$ is either constant or one-to-one.

\prob{2-9 W} For $x\in 2^\om$ let
$b_x=\{x\res n\;:\;n<\om\}$ be the infinite branch thru
$2^{<\om}$ determined by $x$.
Let $\aa=\{b_x\su 2^{<\om}\;:\; x\in 2^\om\}$ be the
almost disjoint family of infinite paths.

Given $\aa_0,\aa_1\su\aa$ with $\aa_0\cap \aa_1=\emptyset$
define the poset $\poset$ as follows:

$(A_0,A_1)\in\poset$ iff $A_0\cap A_1=\emptyset$ and
there exists finite $F_0\su \aa_0$ and $F_1\su\aa_1$ such
that $A_0=^*\cup F_0$ and $A_1=^*\cup F_1$. 

Order $\poset$ by $(A_0,A_1)\trianglelefteq (B_0,B_1)$ iff
 $A_0\supseteq B_0$ and  $A_1\supseteq B_1$.
 
\noindent Prove that $\poset$ has ccc.

\prob{2-9 W} Assume MA.  Prove that if $\aa_0,\aa_1\su\aa$ with 
$\aa_0\cap \aa_1=\emptyset$ and $|\aa_0\cup \aa_1|<|2^\om|$, then
there are disjoint $a_0$ and $a_1$ such that 
$b\su^*a_0$ for every $b\in \aa_0$ and
$b\su^*a_1$ for every $b\in \aa_1$.

\prob{2-11 F} Assume MA. Suppose $\ff\su\om^\om$ and $|\ff|<|2^\om|$.
Prove there exists $g\in\om^\om$ such that for every $f\in\ff\;\;\;
\exists^\infty n\in\om\;\; g(n)=f(n)$.

\prob{2-14 M} Suppose $D\su 2^\ka$ is an open dense set.  Prove
there exists $E\su D$ a dense open set which is countably supported,
i.e., there exists a countable $S\su\ka$ such that for every
$x,y\in 2^\ka$ if $x\res S=y\res S$, then ($x\in E$ iff $y\in E$).

\prob{2-14 M} For each $\al<\om_1$ define
$$C_\al=\{x\in 2^{\om_1}\;:\; \forall n\in\om \;\;x(\al+n)=0\}.$$
(a) Prove that $C_\al$ is closed nowhere dense in $2^{\om_1}$.
\par\noindent
(b) Prove that $\bigcup_{\al<\om_1}C_\al$ is not meager in $2^{\om_1}$.

\prob{2-16 W} Suppose $A_\al\su\al$ for $\al$ a countable limit
ordinal has order type $\om$ and is an unbounded subset
of $\al$.   Prove that $(A_\al\;:\;\al^{lim}<\om_1)$
 contains an uncountable $\Delta$-system,
i.e., there exists an uncountable set $\Sigma$ of countable limit ordinals
and a finite $R$ such that 
$A_\al\cap A_\be=R$ for every pair of distinct $\al,\be\in\Sigma$.

\prob{2-18 F} Prove that $2^\om$ is compact.

\prob{2-21 M} Suppose that $T$ is a Souslin tree and $D\su T$ is
dense open.  Prove that there exists $\al<\om_1$ such 
that $T_\al\su D$.

\prob{2-23 W}  Let $T$ be a tree of height $\om_1$ such that
$T_\al$ is finite for every $\al<\om_1$.  Prove that $T$ must
contain a chain of size $\om_1$.

\medskip
Bonus Problem: Show that a tree of height $\om_2$ and countable
width must have a chin of size $\om_2$.

\prob{2-25 F} Suppose $f:\om_1\to\om_1$.  Define
$$C_f=\{\al<\om_1\;:\; \forall \be<\al \; f(\be)<\al\}$$
Prove that $C_f$ is a closed unbounded subset of $\om_1$ (club).

\noindent Prove that for every club $C\su\om_1$ there exists $f$ with
$C_f\su C$.

\medskip
Bonus Problem: Suppose $M$ is structure in a countable language
and $M$ has universe $\om_1$.  Prove that the set
$$\{\al<\om_1\;:\; M\cap\al\preceq M\}$$
is a club.   The symbol $\preceq$ stands for elementary substructure.

\prob{2-28 M} Assume CH. Given 
$\{A_\al\in[\om_2]^{\leq \om}\;:\;\al<\om_2 \}$
prove there exists a stationary $S\su\om_2$ such that
$\{A_\al \;:\;\al\in S \}$
is a $\Delta$-system.

\prob{3-2 W} Assume $\Diamond$.  Prove there exists
$(A_\al\;:\;\al<2^{\om_1})$ such that each $A_\al$ is
a stationary subset of $\om_1$ and $A_\al\cap A_\be$ is
countable whenever $\al\neq\be$.


\prob{3-7 M} Let $\al>\om$ be a limit ordinal.  Prove
that $(V_\al,\in)$ is a model of $ZC$, i.e., 
$ZFC$ minus the replacement axioms.

\prob{3-9 W} For $\ka$ an uncountable regular cardinal, define
$H_\ka$ to the family of all sets $X$ whose
transitive closure has cardinality less than $\ka$,
$|TC(X)|<\ka$.
Prove that $(H_\ka,\in)$ is a model of $ZFC\sm$Powerset Axiom.

\prob{3-11 F} Prove that the following are equivalent:
\par (a) $x$ is an ordinal
\par (b) $x$ and every element of $x$ is transitive
\par (c) $x$ is transitive and $(x,\in)$ is a strict linear order

\prob{3-21 M} (Ashutosh 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$.

(a) Prove that the set $\{\al<\om_1\;:\;\al$ is weakly-reflecting$\}$
contains a closed unbounded set.  

(b) Show that ZC+weakly-reflecting schema does not imply ZFC.

\prob{3-23 W} Assume ZFC+V=L.  Prove that
$L_{\om_1}=H_{\om_1}$.

\prob{3-25 F} Assume ZFC+V=L.  Suppose that $Q\su\om_1$ 
is a stationary set.  Prove that $\diamondsuit(Q)$ holds.
This means that there exists $(S_\al\su\al\;:\;\al\in Q)$
such that for every $X\su\om_1$ 
$$\{\al\in Q\;:\; S_\al=X\cap\al\}$$ is stationary.


\prob{3-28 M} Assume there is a standard model of ZFC.
Prove that there is a model of 
ZFC + Con(ZFC) + there is
no standard model of ZFC.

\prob{3-30 W} Assume that $\poset$ is a poset in $M$ 
a transitive standard model of ZFC and $G\su\poset$ is
a $\poset$-filter.  Prove that the following are equivalent:
\begin{enumerate}
\item $G$ is $\poset$-generic over $M$.
\item For every $A\in M$ if 
$$M\models A \su\poset \mbox{ is a maximal antichain in }\poset$$
then $G\cap A\neq\emptyset$.
\item For every $E\su\poset$ with $E\in M$ there exists $p\in G$
such that either $p\in E$ or no $q\leq p$ is in $E$.
\end{enumerate}

\def\forces{{\;\Vdash}}

\prob{4-1 F} Given $\poset$-names $\tau$ and $\sigma$ construct 
a $\poset$-name $\rho$
such that for every $G$ $\poset$-generic over $M$
$$\rho^G=\tau^G\times \sigma^G$$
Do not use $\forces$ in your construction.

\prob{4-4 M} Suppose $\ff$ is a family of subsets of $\poset$.
Define
$$D=\{p\in\poset\;:(\forall E\in\ff\;\;E \mbox{ is dense beneath $p$})
\mbox{ or }
(\exists E\in\ff\;\forall q\leq p \;\;q\notin E)\}$$
Prove that $D$ is dense in $\poset$.

\prob{4-4 M} Suppose $G$ is $\poset$-generic over $M$ and
$p\in\poset$.  Prove that either $p\in G$ or there
exists $q\in G$ with $p\perp q$.

\prob{4-4 M} Suppose $G\su\poset\in M$ satisfies
\begin{enumerate}
\item $\forall p,q\in G\;\;\;p$ and $q$ are compatible
\item $\forall p\leq q$ if $p\in G$ then $q\in G$
\item $G\cap D\neq\emptyset$ for all $D\in M$ which are dense in $\poset$
\end{enumerate}
Prove that $G$ is a $\poset$ filter, i.e., $\forall p,q\in G\;\;\exists
r\in G$ with $r\leq p$ and $r\leq q$.

\prob{4-8 F} Suppose $\poset\in M$ and $\poset$ is everywhere
non-trivial: 
$$\forall p\in\poset\;\exists q,r\leq p\;\; q\perp r.$$
Prove that $G\notin M$ for every $G$ $\poset$-generic over $M$.

\prob{4-11 M} Suppose $G$ is $\poset$-generic over $M$
and for all $\ka,\ga$ ordinals in $M$ if $f\in \ka^\ga\cap M[G]$
there exists $g\in M$ such that $M\models g:\ga\to[\ka]^\om$ and
$\forall \al<\ga\;\; f(\al)\in g(\al)$.  Prove that
there exists $p\in G$ such that
$$M\models \poset_{\leq p}\mbox{ has ccc. }$$

\prob{4-15 F} Suppose $M$ is a countable transitive standard model
satisfying
$$M\models ZFC +\neg CH + \poset=2^{<\om_1}$$
and $G$ is $\poset$-generic over $M$.  Prove that
\par (a) $M\cap\power(\om)=M[G]\cap\power(\om)$ and
\par (b) $M[G]\models CH$.

\prob{4-18 M} In a countable transitive model $M$ of ZFC+GCH define
$\poset$ by:

$p\in\poset$ iff there exists $\al<\om_1$ such that
$p=(S_\be\su\be\;:\;\be<\al)$.  

Define $p\leq q$ iff
$\al_p\geq\al_q$ and $S_\be^q=S_\be^p$ for all $\be<\al_q$.

\noindent Prove that if $G$ is $\poset$-generic over $M$ then
\par (a) $M$ and $M[G]$ have the same cardinals and
\par (b) $M[G]\models \diamondsuit$

\prob{4-20 W} Suppose that $M$ is a countable
transitive model of ZFC,
$$M\models\poset=Fn(\om_2,2,\om)$$
$G$ is $\poset$-generic over $M$, and $x\in\power(\om)\cap M[G]$
is definable in $M[G]$ with parameters from $M$.  Prove
that $x\in M$.

\def\nn{{\mathcal N}}
\prob{4-25 M} Suppose that $M$ is a countable
transitive model of ZFC and $\al\in ORD^M$.  Prove that
there is a symmetry model $\nn$ with
$M\su \nn\su M[G]$ and
\par (a) $\nn\models ZF+\neg AC$
\par (b) $\;\;\;\; V_\al^\nn=V_\al^M$


\prob{4-27 W} Suppose that $\nn$ is Cohen Basic model for
$\neg AC$ and $X\in\nn$ is the Dedekind-finite dense
subset of $2^\om$.  Prove
that $\nn$ satisfies:
$$\forall Y\su X \;\exists U\su 2^\om \mbox{ open such that }\;\; Y=^* X\cap U$$
where $=^*$ means equal mod finite.

\def\st{\;:\;}

\prob{4-28 F} Let $\nn$ be same model as in (44), i.e.,
$M\su \nn\su M[G]$ where $X=\{x_n\st n<\om\}$ and $x_n$ is
the $n^{th}$ column of $G$.  Working in $\nn$ define
$$\poset_0=\{s\st \exists n<\om\;\; s:n\to X \mbox{ is one-to-one }\}$$
where $s\unlhd t$ iff $s\supseteq t$.  Working in $M[G]$ define
$G_0=\{s_n\st n<\om\}$ where $s_n:n\to X$ is defined by $s_n(i)=x_i$.
Prove that $G_0$ is $\poset_0$-generic over $\nn$ and
$\nn[G_0]=M[G]$.


\end{document}


