% LaTex2e \documentclass[12pt]{article} \usepackage{amssymb,latexsym} \oddsidemargin 5pt \evensidemargin 5pt \marginparwidth 68pt \marginparsep 10pt \topmargin 10pt \headheight 10pt \headsep 15pt \footskip 35pt \textheight = 625pt \textwidth 440pt \columnsep 10pt \columnseprule 5pt \def\forces{\mid\vdash} \def\prob{\par\bigskip\noindent} \def\cc{{\mathfrak c}} \def\res{{\upharpoonright}} \def\qed{{$\Box$}} \def\ka{\kappa} \def\om{\omega} \def\al{\alpha} \def\be{\beta} \def\de{\delta} \def\ga{\gamma} \def\ep{\epsilon} \def\su{\subseteq} \def\pr{\prime} \def\rr{{\mathbb R}} \def\pp{{\mathbb P}} \begin{document} \begin{flushright} A.Miller\\ M771 \\ Spring 2000\\ http://www.math.wisc.edu/$\sim$miller/m771/hmwk.html\\ \end{flushright} \prob 1. (1-27) Let $(L,\leq)$ be a wellorder and for any $a \in L$ let $L_a = \{ c \in L : c < a \}$. \par Suppose $f:P(X)\to X$ is such that $f(A) \in X\setminus A$ for all $A$ a proper subset of $X$. Call a well ordering $(L,\leq)$ respectful of $f$ iff $L\subseteq X$ and for every $a\in L\; f(L_a)=a$. \par Prove that for any two respectful well-orderings $(A,\leq_A)$ and $(B,\leq_B)$ that either \par $A=B$ or \par $A_x=B$ for some $x\in A$ or \par $B_x=A$ for some $x\in B$ \par\noindent and in any of these cases $\leq_A$ and $\leq_B$ agree on $A\cap B$. \prob 2. (2-3) Define $0! = 1$, $(\alpha + 1)! = \alpha! \cdot (\alpha + 1)$, and $\gamma ! = \sup_{\alpha < \gamma} \alpha!$ for limit $\gamma$. \par\noindent Prove that: $\varepsilon_0$ is the least $\alpha > \omega$ such that $\alpha ! = \alpha$ \par\noindent where $\varepsilon_0 = \sup_{n \in \omega} \tau_n$, where $\tau_0 = \omega$ and $\tau_{n+1} = \omega^{\tau_n}$. \prob 3. (2-8) Prove there exists a family ${\cal B}$ with $|{\cal B}|=2^\cc$ such that each $X\in {\cal B}$ is a Bernstein set. \prob 4. (2-8) Prove that for any limit ordinal $\alpha>\omega$ that $V_\alpha$ is model of Z+AC (Zermelo set theory plus the axiom of choice). \prob 5. (2-8) Prove in Z (no replacement) that \par For any set $X$ and $G:X\to X$ and $x_0\in X$ there exists a unique $f:\omega\to X$ such that $f(0)=x_0$ and for all $n\in\omega$ we have that $f(n+1)=G(f(n))$. \prob Extra Credit (no time limit) \par Does Z prove that for every set $X$ there exists a transitive set $Y\supseteq X$? \prob 6. (2-15) (Goodstein) The complete expansion of a positive integer in a base is gotten by writing everything possible including exponents and exponents of exponents etc. as powers of the base. For example the number 36 written in complete base two is: $ 2^{( {2^2} + 1)}+2^2$. The same number in complete base 3 is: $ 3^3 + 3^2$. \par Let $a_n$ be a sequence described as follows. Given $a_k$ calculate $a_{k+1}$ by writing $a_k$ in base k then substitute k+1 for every k, then subtract one. For example: $$ a_2 =36=2^{( {2^2} + 1)}+2^2 \mbox{ implies } a_3 = 3^{( {3^3} + 1 )}+3^3 - 1 = 2.2876\ldots \times 10^{13} $$ or for example if $a_6 = 6^4 + 2 \cdot 6^3 = 1728$, then $$ a_7 = ( 7^4 + 2 \cdot 7^3) -1 = 7^4 +7^3 +6\cdot 7^2 + 6\cdot 7^1 + 6 = 3086 $$ Show that given any pair of positive integers n and m, if we let $a_n = m$ then for some $k > n$ we get $a_k = 0$. \prob 7. (2-15) (Bukovsky, Hechler) Suppose $\lambda$ is a singular limit cardinal and for some $\gamma$ we have $2^\alpha=\gamma$ for a cofinal set of $\alpha<\lambda$. Prove that $2^\lambda=\gamma$. \prob 8. (2-22) Show that $V_\kappa\models$ZFC for any strongly inaccessible cardinal $\kappa$. \prob 9. (2-22) Show that the least ordinal $\kappa$ (assuming one exists) for which $V_\kappa\models$ZFC is an uncountable cardinal with countable cofinality. \par Hint: Prove: If $V_\kappa\models$ZFC, then there exists $\alpha\leq\kappa$ of countable cofinality such that $V_\alpha$ is and elementary substructure of $V_\kappa$. \prob 10. (2-22) Define $H_\kappa=\{x:|TC(x)|<\kappa\}$. Show that: \par (a) $H_\kappa\subseteq V_\kappa$ for any infinite cardinal $\kappa$. \par (b) for any uncountable regular cardinal $\kappa$ that $H_\kappa\models$ZFC$\setminus$PowerSetAxiom. \par (c) for any regular $\kappa\geq\omega$ that $V_\kappa=H_\kappa$ iff $\kappa=\omega$ or $\kappa$ is strongly inaccessible. \par (d) there exists a cardinal $\kappa>\omega$ with countable cofinality such that $V_\kappa=H_\kappa$. \par\medskip Hint: (10d) If $\kappa_{n+1}=|V_{\kappa_n}|^+$ then $V_{\kappa_n}\in H_{k_{n+1}}$. \prob 11. (2-29) Suppose $M$ and $N$ are standard transitive models of ZFC with the same set of ordinals. Suppose that for every ordinal $\al\in M$ $$P(\al)\cap M=P(\al)\cap N$$ Prove that $M=N$. \par Hint: It isn't true for models of ZF. \par Show $P(\al\times\al)\cap M= P(\al\times\al)\cap N$. \par Consider $(X,\in)\simeq (\al,E)$ for some $E\subseteq \al\times\al$. \prob 12. (2-29) For any set $X$ let $[X]^{<\om}=\bigcup_{n<\om}[X]^n$ where $[X]^n=\{s\subseteq X: |s|=n\}$. \par A cardinal $\ka$ is Erd\"os iff $\ka\to (\om)^{<\om}_2$ which means for every $f:[\ka]^{<\om}\to 2$ there exists an infinite $X\subseteq \ka$ such that for every $n<\om$ the function $f$ is constant when restricted to $[X]^n$. The smallest Erd\"os cardinal (if any exist) is strongly inaccessible. \par Suppose $M\subseteq N$ are standard transitive models of ZFC and $\ka\in M$ and $N\models ``\ka$ is Erd\"os''. \par Prove that $M\models ``\ka$ is Erd\"os''. \par Hint: If not, find a well-founded partial order in $M$ which is not well-founded in $N$. Consider $\{s\in [\kappa]^{<\omega}: \forall n\leq |s|\;\; f\res [s]^n$ is constant $\}$. \prob 13. (3-7) Suppose that ZF has a well-founded model. Then prove there exists a countable $\delta$ such that \par (a) $L_\delta\models$ZFC and for any transitive standard model $M$ of ZF we have that $L_\delta\subseteq M$ \par (b) every element of $L_\delta$ is definable in $L_\delta$ without parameters. \par Hint: $L$ has a well-ordering which is definable without parameters. Also if $$X=\{a\in L_\de: a \mbox{ def without para in }L_\de\}$$ then show $X$ is an elementary substructure of $L_\de$. \prob 14. (3-7) For $X$ a set of ordinals define the class $L[X]$ as follows: \par (a) $L_0[X]=\emptyset$ \par (b) $L_\lambda[X]=\cup_{\al<\lambda}L_\al[X]$ for $\lambda$ limit \par (c) $L_{\al+1}[X]=$Def$(L_\al[X],X\cap \al,\in)$ (add a new unary predicate to language) \par (d) $L[X]=\cup_{\al\in ORD}L_\al[X]$ \par\noindent Prove that if $V=L[X]$ for some $X\subseteq \omega_1$ then ZFC+GCH is true in $V$. \prob 15. (3-21) Prove that if there exists a Souslin tree then there exists a nice Souslin subtree of $\om^{<\om_1}$. \par\noindent Hint: Define a Souslin tree $T$ is normal iff for all $\al<\be<\om_1\;\; \forall s\in T_\al\exists t\in T_\be\;\; s\leq t$ \par (a) Show that every Souslin tree contains a normal subtree which is Souslin. \par (b) Show that if $T$ is a normal Souslin tree then there exist a club $C\su\om_1$ such that for every $\al,\be\in C$ if $\al<\be$ then $\forall s\in T_\al\exists^\infty t\in T_\be\;\; s\leq t$. \prob 16. (3-21) Show that for every club $C\su\ka$ (unctble regular $\ka$) there exists $f:\ka\to\ka$ such that if $C_f=\{\al<\ka:\forall \be<\al \;\; f(\be)<\al\}$ then $C_f\su C$. \prob 17. (3-21) Prove there is a stationary subset of $\om_1$ whose compliment is also stationary. \par Hint: Given $x_\al:\om\to 2$ for $\al<\om_1$ and $n<\om$, consider $\{\al<\om_1:\; x_\al(n)=0\}$ \prob 18. (3-23) Suppose $S\su\ka$ is a stationary subset of the regular uncountable cardinal $\ka$. Prove there exists $S^\pr\su S$ a stationary subset of $\ka$ such that $\forall \al\in S^\pr$ the set $S^\pr\cap\al$ is not stationary in $\al$. \par Hint: Define $S^\pr$ inductively by $\al\in S^\pr$ iff $\al\in S$ and $S^\pr\cap \al$ not stationary in $\al$. \prob 19. (3-23) Suppose $\Diamond_{\om_1}$. Prove there exists $\langle S_\al\su\om_1:\al<2^{\om_1}\rangle $ such that each $S_\al$ is stationary in $\om_1$ and $S_\al\cap S_\be$ is countable for all $\al\not=\be$. \prob 20. (3-28) Suppose V=L. Prove that for any regular $\ka$ that $L_\ka=H_\ka$. \prob 21. (4-4) Suppose $T$ is a Souslin tree and $f:T\to\rr$ is continuous. Prove that the range of $f$ is countable. \par Hint: First show for every $\ep>0$ for every $s\in T$ there exists $t\in T$ with $s\leq t$ and the diameter of $\{f(r):t\leq r\in T\}$ less than $\ep$. \prob 22. (4-4) Assume $V=L$. Prove that there is a diamond sequence on every stationary $S\su\om_1$. \prob 23. (4-4) Assume $V=L[X]$ for some $X\su\om_1$. Prove that $\Diamond_{\om_1}$ holds. \prob 24. (4-11) Assume $M$ is a transitive standard model of ZFC and \par\noindent $M\models$``$ \pp=(T,\geq)$ where $T$ is a Souslin tree''. Suppose $G$ is an $\om_1$-branch thru $T$. Prove that $G$ is a $\pp-$generic filter over $M$. \par Hint: Suppose $M\models D\subseteq T$ is dense. Show that \par $M\models\exists \al<\om_1\;\; \forall s\in T_\al\;\; \exists t\in D\;\; t