Click here to return to the main course web page.

This homework set has three parts. Complete 2 questions from part one and 1 question each from parts two and three.

Part 1 (do 2 problems) This first set of exercises gives an introduction to Todorcevic's method of minimal walks. For this problem, fix a sequence \(\langle C_\alpha \mid \alpha \in \omega_1 \rangle\) such that \(C_0 = \emptyset\), \(C_{\alpha+1} = \{\alpha\}\), and if \(\alpha\) is a limit ordinal, \(C_\alpha \subseteq \alpha\) has ordertype \(\omega\) and supremum \(\alpha\).

1. (upper trace) If \(\alpha < \beta < \omega_1\), define \(\mathrm{Tr}(\alpha,\beta) := \{ \beta_i \mid i < l \} \) where \(\beta_0 = \beta\), \(\beta_{i+1} = \min (C_{\beta_i} \setminus \alpha)\) if \(\beta_i > \alpha\), and where \(l\) is such that \(\beta_l = \alpha\). This is the trace of the walk from \(\beta\) down to \(\alpha\). Define \(\lambda(\alpha,\beta) := \sup \bigcup \{C_{\beta_i} \cap \alpha \mid i < l\}\) with the convention that \(\sup(\emptyset) = -1\). Show that the following are equivalent for \(\alpha < \beta < \gamma\):
   • \(\beta\) in \(\mathrm{Tr}(\alpha,\gamma)\)
   • \(\mathrm{Tr}(\alpha,\gamma) = \mathrm{Tr}(\alpha,\beta) \cup \mathrm{Tr}(\beta,\gamma) \)
   • \(\lambda(\beta,\gamma) < \alpha\)
2. (nontrivial coherent sequence) If \(\alpha < \beta < \omega_1\), define \[ \varrho_1(\alpha,\beta) := \max \{|C_\xi \cap \alpha| \mid \xi \in \mathrm{Tr}(\alpha,\beta)\}. \] Show that for each \(\beta < \gamma < \omega_1\) and \(n < \omega\) that the following sets are finite: \[ \{ \alpha \in \beta \mid \varrho_1(\alpha,\beta) \leq n\} \qquad \qquad \{ \alpha \in \beta \mid \varrho_1(\alpha,\beta) \ne \varrho_1(\alpha,\gamma)\} \] Hint: suppose that one of these sets is infinite, walk down to a limit point from above, and get a contradiction.
3. (coherent Aronszajn tree) Define \(T(\varrho_1)\) to be the set \[ \{ \varrho_1(\cdot,\beta) \restriction \alpha \mid \alpha \leq \beta < \omega_1\} \] partially ordered by \(s \leq t\) if \(s\) is a restriction of \(t\). Show that for each \(\alpha\), there are only countably many elements of \(T(\varrho_1)\) of length \(\alpha\) but that there is no \(b: \omega_1 \to \omega\) such that for all \(\alpha \in \omega_1\), \(b \restriction \alpha \in T(\varrho_1)\).
4. (Countryman line) Let \(C(\varrho_1)\) be the set \(\{\varrho_1(\cdot,\beta) \mid \beta < \omega_1\}\) equipped the lexicographic order: \(s \leq_{\mathrm{lex}} t\) if \(s\) is an initial part of \(t\) or \(s(\xi) < t(\xi)\) where \(\xi\) is minimal such that \(s(\xi) \ne t(\xi)\). Show that \(C(\varrho_1) \times C(\varrho_1)\) is a countable union of chains in the coordinatewise partial order. Hints: It's sufficient to show that that the region above the diagonal in \(C(\varrho_1)^2\) is a countable union of chains. If \(\alpha < \beta < \omega_1\), define \[ n_{\alpha,\beta} := \max (\{\varrho_1(\xi,\alpha),\varrho_1(\xi,\beta),\varrho_1(\alpha,\beta) \mid \varrho(\xi,\alpha) \ne \varrho(\xi,\beta) \}) \] \[ E_{\alpha,\beta} := \{\xi \in \alpha \mid \varrho_1(\xi,\alpha) < n_{\alpha,\beta}\} = \{\xi \in \alpha \mid \varrho_1(\xi,\beta) < n_{\alpha,\beta}\} \] If \(E_{\alpha,\beta} = \{\xi_0 < \xi_1 < \ldots < \xi_{l-1}\}\) define \[ s_{\alpha,\beta} (i) := \varrho_1(\xi_i,\alpha) \qquad \textrm{ and }\qquad t_{\alpha,\beta} (i) := \varrho_1(\xi_i,\alpha) \]for \(i < l\) and set \(t_{\alpha,\beta}(l) := \varrho_1(\alpha,\beta)\). Show that \[ C_{s,t} := \{(\varrho_1(\cdot,\alpha),\varrho_1(\cdot,\beta)) \mid s_{\alpha,\beta} = s \land t_{\alpha,\beta} = t\} \] is a chain for each pair \(s,t \in \omega^{<\omega}\). Remark: an uncountable linear order \(C\) such that \(C \times C\) is a countable union of chains is called a Countryman line. They were first considered by Countryman and first shown to exist by Shelah; this construction is due to Todorcevic.

Part 2 (do one problem) This set of problems analyses Aronszajn and Countryman lines.

5. A linear order is Aronszajn if it is uncountable but does not contain an uncountable separable suborder and does not contain a copy of \(\omega_1\) or \(-\omega_1\). Show that any Aroszajn line has cardinality \(\aleph_1\).
6. Suppose that \(T\) is a tree. Prove that \(T\) is a countable union of antichains if and only if there is a function \(f:T \to \mathbb{Q}\) such that \(f(s) < f(t)\) whenever \(s < t\).
7. Show that if \(C\) is a Countryman line then \(C\) does not contain an uncountable separable suborder, \(C\) does not contain an uncountable well order or reverse well order, and no uncountable linear order embeds into both \(C\) and \(-C\), the reverse of \(C\).

Part 3 (do one problem) The problems in this section give an analysis of \(\diamondsuit\), filling in some details omitted in the lecture. For the purpose of these problems, \(\diamondsuit\) is the following assertion: There is a sequence \(\langle A_\alpha : \alpha \in \omega_1\rangle\) such that for all \(\alpha \in \omega_1\), \(A_\alpha \subseteq \alpha\) and for all \(X \subseteq \omega_1\), there is an infinite \(\alpha \in \omega_1\) such that \(A_\alpha = X \cap \alpha\).

8. If \(X \subseteq \omega_1\) and \(k \in \omega\), define \(X^{(k)}:=\{\xi \in \omega_1 \mid \omega \cdot \xi + k \in X\}\). Now suppose that \(\langle A_{\alpha,n} \mid \alpha \in \omega_1 \land n \in \omega\rangle\) is such that for every \(X \subseteq \omega_1\), there is an \(n \in \omega\) such that \[ \{\alpha \in \omega_1 \mid X \cap \alpha = A_{\alpha,n}\} \] is stationary in \(\omega_1\). Prove that for some \(n\), \(\langle A_{\alpha,n}^{(n)} \mid \alpha \in \omega_1\rangle\) is a \(\diamondsuit\)-sequence.
9. With the notation from the previous exercise, suppose that \(\langle \mathscr{A}_\alpha \mid \alpha \in \omega_1 \rangle\) is such that:
   • each \(\mathscr{A}_\alpha \subseteq \mathscr{P}(\alpha)\) is countable,
   • if \(A\) is in \(\mathscr{A}_\alpha\) then so is \(A^{(k)}\) for each \(k \in \omega\), and
   • for every \(X \subseteq \omega_1\) there is an infinite \(\alpha \in \omega_1\) such that \(X \cap \alpha \in \mathscr{A}_\alpha\).
   Show that:
   • If \(X,Y \subseteq \omega_1\), then there is an infinite \(\alpha\) such that \(X \cap \alpha\) and \(Y \cap \alpha\) are both in \(\mathscr{A}_\alpha\).
   • If \(E \subseteq \omega_1\) is club, then there is an \(X \subseteq \omega_1\) such that if \(X \cap \alpha \in \mathscr{A}_\alpha\), then \(\alpha \in E\). Hint: assume that \(E\) consists of only limit ordinals and construct an \(X \subseteq \omega_1\) such that if \(A \in \mathscr{A}_\alpha\) for \(\alpha\) at most the \(\xi\)th element of \(E\), \(X \cap [\omega \cdot \xi, \omega \cdot \xi + \omega) \ne A \cap [\omega \cdot \xi, \omega \cdot \xi + \omega)\).
   • If \(X \subseteq \omega_1\), then \(\{\alpha \in \omega_1 \mid X \cap \alpha \in \mathscr{A}_\alpha\}\) is stationary.