Click here to return to the main course web page.
\(\newcommand\Tr{\mathrm{Tr}}\)
-
Fix a \(C\)-sequence on \(\omega_1\) and let \(\mathrm{Tr}\) be defined as in Homework 5.
If \(\alpha < \beta < \omega_1\), define
\[
F(\alpha,\beta):= \{\xi \in \alpha : \Tr(\xi,\alpha) \cap \Tr(\xi,\beta) = \emptyset\} \cup \{\alpha\}.
\]
-
Show that \(F(\alpha,\beta)\) is finite for all \(\alpha < \beta < \gamma\).
-
Show that if \(\eta \in \alpha\) and \(\xi = \min (F(\alpha,\beta) \setminus \eta)\), then
\[
\Tr(\eta,\alpha) = \Tr(\eta,\xi) \cup \Tr(\xi,\alpha) \qquad
\Tr(\eta,\beta) = \Tr(\eta,\xi) \cup \Tr(\xi,\beta)
\]
-
Show that if \(\alpha,\beta,\gamma < \omega_1\) are distinct, then
\[
F(\alpha,\beta) \cap \min (\alpha,\beta,\gamma) \subseteq F(\alpha,\gamma) \cup F(\beta,\gamma)
\]
Remark: This is the full lower trace.
It provides a finite set of "meeting points" \(\leq \alpha\) such that any pair of walks for \(\alpha\) and \(\beta\) toward
a common destination proceed by first heading toward a meeting point and then taking a common walk to the destination.
The last containment is useful in much of the finer analysis of minimal walks, both at \(\omega_1\) and at higher
cardinals.
-
(Todorcevic's square bracket function)
If \(\alpha < \beta < \omega_1\), define
\[
\Delta(\alpha,\beta) := \min
( \{\xi \in \alpha \mid \varrho_1(\xi,\alpha) \ne \varrho_1(\xi,\beta)\} \cup \{\alpha\} )
\]
\[
[\alpha, \beta] := \min (\mathrm{Tr} (\Delta (\alpha,\beta) , \beta) \setminus \alpha)
\]
where \(\varrho_1\) and \(\mathrm{Tr}\) are defined as in Homework 5.
-
Prove that if \(X \subseteq \omega_1\) is uncountable, then
\[
\{[\alpha,\beta] \mid (\alpha < \beta) \land (\alpha,\beta \in X)\}
\]
contains a closed and unbounded set.
-
Prove that there is a function \(f:[\omega_1]^2 \to \omega_1\) such that if
\(X \subseteq \omega_1\) is uncountable, the range of \(f \restriction [X]^2\) is all of
\(\omega_1\).
Hints:
For the first part it is sufficient to show that if \(M \prec H_{\omega_2}\) is
countable and \(\varrho_1\) and \(X\) are in \(M\), then there are \(\alpha,\beta \in X\) with
\(\alpha < M \cap \omega_1 < \beta\) and \([\alpha,\beta] = M \cap \omega_1\).
The only property of \(\varrho_1\) that is needed here is that \(T(\varrho_1)\) has countable
levels and no uncountable chains.
You may then use without proof that if \(E \subseteq [H_{\omega_2}]^\omega\) is a club, then
\(\{M \cap \omega_1 \mid M \in E\}\) contains a closed and unbounded subset of \(\omega_1\).
For the second part, compose \([\alpha,\beta]\) with a suitably chosen function from
\(\omega_1\) to \(\omega_1\).
-
Define
\(
\mathscr{U}(\varrho_1) := \{U \subseteq \omega_1 \mid \exists X \in [\omega_1]^{\omega_1} (\Delta(X) \subseteq U) \}.
\)
Here \(\Delta(X)\) is the set of all \(\Delta(\alpha,\beta)\) such that \(\alpha < \beta\) are in \(X\)
and \(\varrho_1(\cdot,\alpha)\) is not an initial part of \(\varrho_1(\cdot,\beta)\).
Prove that \(\mathscr{U}(\varrho_1)\) is a filter on \(\omega_1\).
Here \(\mathscr{F}\) is a filter on \(X\) if \(\mathscr{F} \subseteq \mathscr{P}(X) \setminus \{\emptyset\}\)
is nonempty, is closed under taking finite intersections, and supersets.
-
If \(V \subseteq \omega_1\), define \(Q_U\) to be the collection of all finite subsets \(q\) of
\(\omega_1\) such that \(\Delta(q) \subseteq U\).
Show the following:
-
If \(V \subseteq \omega_1\) is such that \(\omega_1 \setminus V\) is not in
\(\mathscr{U}(\varrho_1)\), then \(Q_U\) is c.c.c..
-
For every \(V \subseteq \omega_1\), \(Q_V \times Q_{\omega_1 \setminus V}\) is not c.c.c..
-
If the countable chain condition is productive, then \(\mathscr{U}(\varrho_1)\) is an ultrafilter.
-
Suppose that \(X \subseteq \omega^\omega\) consists of increasing functions and \(X\) is countably directed and unbounded with respect to \(<^*\),
where \(x <^* y\) if \(x(n) < y(n)\) for all but finitely many \(n\).
Prove that there are \(x \ne y \in X\) such that \(x(n) \leq y(n)\) for all \(n\).
Hint: start by fixing a countable dense subset \(D\) of \(X\) and letting \(u \in X\) be a \(<^*\) upper bound for \(D\).
-
The Open Coloring Axiom (OCA) is the assertion that if \(X\) is a separable metric space and \(E \subseteq [X]^2\) is an open graph, then either \((X,E)\) is countably chromatic or else has an uncountable clique.
Here a graph is open if whenever \(x,y \in X\) are connected by an edge, there are open \(x \in U\) and \(y \in V\) such that every element of \(U\) is
connected to every element of \(V\).
Show that the Open Coloring Axiom implies that \(\mathfrak{b} > \aleph_1\),
where \(\mathfrak{b}\) is the minimum cardinality of an unbounded subset of \(\omega^\omega\).
Hint: if \(\mathfrak{b} = \aleph_1\), then there is a \(<^*\)-increasing sequence \(f_\xi\) \((\xi < \omega_1)\) of increasing functions from \(\omega\) to
\(\omega\) which is \(<^*\)-unbounded.
Use the previous exercise to define an open graph which contradicts OCA.
-
Suppose that \(\kappa,\lambda\) are regular cardinals and \(a_\xi\) \((\xi < \kappa)\) and \(b_\xi\) \((\xi < \lambda)\) are elements of \(\omega^\omega\) such that:
-
if \(\xi < \eta < \kappa\), then \(a_\xi <^* a_\eta\).
-
if \(\xi < \eta < \lambda\), then \(b_\eta <^* b_\xi\).
-
if \(\xi < \kappa\) and \(\eta < \lambda\),
\(a_\xi <^* b_\eta\).
-
There is no \(c \in \omega^\omega\) such that
\(a_\xi <^* c <^* b_\eta\) for all \(\xi < \kappa\) and \(\eta < \lambda\).
Such a pair of sequences is called a \((\kappa,\lambda^*)\)-gap.
Let \(X\) be the set of all pairs \((a,b) \in \omega^\omega \times \omega^\omega\) such that \(a \leq b\) and there exist \(\xi < \kappa\) and \(\eta < \lambda\) such that
\(a =^* a_\xi\) and \(b =^* b_\xi\).
Consider the graph on \(X\) such that \(\{(a,b),(a',b')\} \in E\) if and only if there is an \(n\) such that either
\(b'(n) < a(n)\) or \(b(n) < a'(n)\).
Show:
-
If \((X,E)\) has an uncountable clique, then \(\kappa = \lambda = \omega_1\).
Hint: without loss of generality the clique has size \(\aleph_1\). Show that the set of \(a_\xi\)'s and \(b_\eta\)'s which "appear" in the clique already form a gap.
-
\((X,E)\) is countably chromatic if and only \(\min(\kappa,\lambda) = \omega\).
-
Show that there is a \((\lambda,\omega^*)\)-gap if and only if there is an unbounded \(<^*\)-chain in \(\omega^\omega\) of order type \(\lambda\).
-
Show that if \(\mathfrak{b} > \aleph_2\), then there is an \((\omega_2,\lambda^*)\)-gap for
some uncountable regular cardinal \(\lambda\).
-
Show OCA implies that the only gaps in \(\omega^\omega\) which exist are \((\kappa,\omega^*)\)-gaps, \((\omega,\kappa^*)\)-gaps,
and \((\omega_1,\omega_1^*)\)-gaps, where \(\kappa \geq \omega_2\).
Show that OCA implies \(\mathfrak{b} = \aleph_2\).
Remark: it is an open problem whether OCA implies \(2^{\aleph_0} = \aleph_2\).
-
Let \(\mathcal{F} \subseteq [\omega]^\omega\) be closed under taking finite intersections.
Define \(\mathscr{K}\) to be the collection of all finite subsets \(\mathcal{F}_0\) of \(\mathcal{F}\) such that for
for each \(n\), \(|\Delta(\mathcal{F}_0 ) \cap n| \leq |\bigcap \mathcal{F}_0 \cap n|\)
where \(\Delta(\mathcal{F}_0) := \{\Delta(A,B) \mid A\ne B \textrm{ are in } \mathcal{F}_0 \}\) and
\(\Delta(A,B)\) is the least element of the symmetric difference of \(A\) and \(B\).
-
Prove that \((\mathscr{K},\supseteq)\) is \(\sigma\)-linked.
-
Prove that if \(\mathcal{H} \subseteq \mathcal{F}\) and every finite subset of \(\mathcal{H}\) is in \(\mathscr{K}\),
then \(\bigcap \mathcal{H}\) is infinite.
Hint:
if \(\mathcal{F}_0 \restriction k := \{A \cap k \mid A \in \mathcal{F}_0\}\), then
\(\{ \mathcal{F}_0 \restriction k \mid (\mathcal{F}_0 \in \mathscr{K}) \land (k \in \omega)\}\) is countable.
If \(\mathcal{F}_0 , \mathcal{F}_1 \in \mathscr{K}\) and \(k\) is such that
\(\mathscr{F}_0 \restriction k = \mathscr{F}_1 \restriction k\) with cardinality equal to \(|\mathcal{F}_0| = |\mathcal{F}_1|\),
how large can \(\Delta (\mathcal{F}_0 \cup \mathcal{F}_1) - \Delta(\mathcal{F}_0)\) be?
Also, observe that \(\lim_{n \to \infty} |\bigcap \mathcal{F}_0 \cap n | = \infty\) for every \(\mathcal{F}_0\) in \(\mathscr{K}\).
Remark: This exercise shows that if every uncountable subset of a c.c.c. poset contains an uncountable centered family,
then \(\mathfrak{p} > \aleph_1\), which combined with Bell's theorem implies \(\mathrm{MA}_{\aleph_1}(\sigma-\mathrm{centered})\).
-
Let \(S \subseteq \omega_1\) be stationary and let \(Q_S\) denote
the collection of all countable closed subsets of \(S\) ordered by \(q \leq p\) if \(p\) is an initial segment of \(q\).
Show that forcing with \(Q_S\) does not add new reals and hence preserves
subsets of \(\omega_1\).
Hint: Let \(M\) be a countable elementary submodel of \(H({2^{\aleph_0}}^+)\) which contains \(S\) and such that \(M \cap \omega_1 \in S\).
Show that for every \(p \in M \cap Q_S\), there is a \(q \leq p\)
such that \(\{r \in Q_S \cap M : q \leq r\}\) is an \(M\)-generic filter.
Show that this suffices.
-
Show that if \(S,T \subseteq \omega_1\) are disjoint stationary sets,
then \(Q_S \times Q_T\) collapses \(\omega_1\).