1

Suppose \(\mathcal{A}\) is an uncountable family of pairwise disjoint non-stationary subsets of \(\omega_1\). Show that there exists \(\mathcal{B}\subseteq\mathcal{A}\) such that \(\mathcal{B}\) is uncountable and \(\bigcup\mathcal{B}\) is a non-stationary subset of \(\omega_1\).

Suppose for a contradiction that for all \(\mathcal{B}\subseteq \mathcal{A}\), whenever \(\mathcal{B}\) is uncountable, \(\bigcup\mathcal{B}\) is stationary subset of \(\omega_1\).

Claim. We can refine \(\mathcal{A}\) into an uncountable sequence \(\mathcal{B}= \left\langle B_\alpha: \alpha < \omega_1\right\rangle\) where each \(B_\alpha\in A\) such that \[ \alpha < \beta \implies \alpha < \min A_\alpha < \min A_\beta .\]

Let \(\left\langle A_\alpha: \alpha < \left\lvert\mathcal{A}\right\rvert\right\rangle\) be a well-ordering of the subsets in \(\mathcal{A}\), first recursively define an increasing function \(f:\omega_1\to\omega_1\) which we use to obtain a subsequence \(\mathcal{B}\).

\[ f(0) = \begin{cases} 0 &\text{if } \min A_0 > 0 \\ 1 &\text{otherwise} \end{cases}\] and when \(f(\alpha)\) is defined for all \(\alpha<\beta\), let \(\mu = \sup\left\{\min(A_{f\alpha}): \alpha<\beta\right\}\) and define \[ f(\beta) = \min\left\{\gamma: \beta<\gamma \text{ and } \sup\left\{\mu,\beta\right\} < \min A_{\gamma} \right\} \] and note that \(f(\beta)\) is well defined as both \(\mu,\beta\) are countable and by pairwise disjointedness of \(A_\alpha\)’s I can always find a suitable \(\gamma\) below \(\omega_1\). We can now verify that \(\mathcal{B}= \left\langle B_\alpha = A_{f(\alpha)}: \alpha<\omega_1\right\rangle\) is an uncountable subsequence of \(\mathcal{A}\).

Define \(g: \bigcup_{\alpha<\omega_1} B_\alpha \to \omega_1\) as \[ g(\gamma) = \beta \text{ where } \gamma \in B_\beta \] which is regressive by construction as \(\beta < \min B_\beta \leq \gamma\). Then by Fodor’s lemma there exists a stationary \(T\subseteq \bigcup_{\alpha<\omega_1} B_\alpha\) where \(g\upharpoonright T\) is constant, but if the restriction is constant it means that \(T\subseteq B_\beta\) for some \(\beta<\omega_1\), which means \(T\) is non-stationary.

2

Let \(\operatorname{Lim}(\omega_1)\) denote the set of limit ordinals in \(\omega_1\). Suppose \(\left\langle A_\alpha:\alpha\in\operatorname{Lim}(\omega_1)\right\rangle\) satisfies the following

1. For every \(\alpha\in\operatorname{Lim}(\omega_1)\), \(A_\alpha\) is an unbounded subset of \(\alpha\) of order type \(\omega\).
2. For every uncountable \(A\subseteq \omega_1\), there exists \(\alpha\in\operatorname{Lim}(\omega_1)\) such that \(A_\alpha\subseteq A\).

Show that for every uncountable \(A\subseteq\omega_1\), the set \(\left\{\alpha\in\operatorname{Lim}(\omega_1): A_\alpha\subseteq A\right\}\) is stationary in \(\omega_1\).

Let \(A\subseteq \omega_1\) be uncountable, and let \(C\subseteq\omega_1\) be a club. We want to show that \(\left(\exists\alpha\in C\right)\left(\alpha\in \operatorname{Lim}(\omega_1)\land A_\alpha\subseteq A\right)\). By considering \(C\cap \operatorname{Lim}(\omega_1)\), which is the intersection of 2 clubs, we can without loss of generality let \(C\subseteq \operatorname{Lim}(\omega_1)\) and simplify the condition to \[\left(\exists\alpha\in C\right)\left(A_\alpha\subseteq A\right).\] Recursively define \(f:\omega_1\to A\) as \[ f(0) = \left(\begin{aligned} \textbf{let } & \mu = \min\left\{\alpha\in\operatorname{Lim}(\omega_1):A_\alpha\subseteq A\right\} \textbf{ in} \\ &\min A_{\mu} \end{aligned}\right)\] and when \(f\) is defined for all \(\alpha<\beta\), \[ f(\beta) = \left(\begin{aligned} \textbf{let }& \gamma_1 = \sup\left\{f(\alpha):\alpha<\beta\right\}\\ &\gamma_2 = \min(C\setminus\gamma) \\ &A' = A\setminus\gamma_2 \\ &\mu = \min\left\{\alpha\in\operatorname{Lim}(\omega_1): A_\alpha\subseteq A'\right\} \textbf{ in} \\ &\min A_\mu \end{aligned}\right)\] in both cases \(f\) is well-defined as \(\mu\) always exists since \(A'\) remains unbounded. Now observe that by construction \(f\) has the property \[ \alpha<\beta \implies \left(\exists\gamma\in C\right)\left(f(\alpha) < \gamma < f(\beta)\right). \] Let \(B = \operatorname{range}(f)\subseteq A\), which is uncountable, let \(\alpha\in\operatorname{Lim}(\omega_1)\) such that \(A_\alpha\subseteq B\). As the order type of \(A_\alpha\) is \(\omega\) we enumerate it as an increasing sequence \(A_\alpha = \left\{\beta_0,\beta_1, \dots\right\}\). Then for each \(n\in\omega\) use property of \(f\) to choose \(\gamma_n \in C\) such that \(\beta_n < \gamma_n < \beta_{n+1}\). Then \(\sup\left\{\beta_n:n\in\omega\right\} = \sup\left\{\gamma_n:n\in\omega\right\} = \alpha\). As \(C\) is closed \(\alpha \in C\).

3

Suppose \(\kappa\) is an infinite cardinal. For each \(\alpha<\kappa^+\), fix a one-one function \(f_\alpha: \alpha\to\kappa\). For each \(\xi<\kappa\) and \(\alpha<\kappa^+\), define \(A_\alpha^\xi = \left\{\beta<\kappa^+:\alpha<\beta \text{ and } f_\beta(\alpha) = \xi\right\}\).

(a) For every \(\xi<\kappa\), \(\left\langle A_\alpha^\xi:\alpha<\kappa^+\right\rangle\) is a sequence of pairwise disjoint sets.

Fix \(\xi<\kappa\) and compare \(A^\xi_\alpha\) and \(A^\xi_\beta\) where \(\alpha < \beta < \kappa^+\). If they intersect, then there is a \(\gamma\in (\beta,\kappa^+)\) where \(f_\gamma(\alpha) = \xi\) and \(f_\gamma(\beta) = \xi\). This cannot happen because \(f_\gamma\) is one-one.

(b) For every \(\alpha<\kappa^+\), \(\bigcup\left\{A_\alpha^\xi: \xi<\kappa\right\} = \kappa^+\setminus\left(\alpha+1\right)\).

Each \(\mathcal{A}_\alpha^\xi\) is a subset of \(\kappa^+\setminus\left(\alpha+1\right)\) by construction. Now let \(\beta\in(\alpha, \kappa^+)\), then let \(\xi = f_\beta(\alpha) < \kappa\) and by definition we see that \(\beta\in A_\alpha^\xi\).

(c) There is a family \(\mathcal{F}\) of pairwise disjoint stationary subsets of \(\kappa^+\) such that \(\left\lvert\mathcal{F}\right\rvert = \kappa^+\).

Let \(\mathcal{I}\) be the non-stationary ideal on \(\kappa^+\). For any \(\alpha<\kappa^+\), we cannot have \(\left(\forall\xi<\kappa\right)\left(A_\alpha^\xi \in \mathcal{I}\right)\) or else the union would also be in \(\mathcal{I}\) as \(\mathcal{I}\) is \(\kappa^+\)-complete. Let \(h:\kappa^+\to\kappa\) such that \(A_\alpha^{h(\alpha)} \notin \mathcal{I}\), and there is a \(\xi\) where \(\left\lvert h^{-1}\left\{\xi\right\}\right\rvert = \kappa^+\), otherwise \(\kappa^+\) would be a union of \(\kappa\)-many sets of size at most \(\kappa\). Now let \(\mathcal{F}= \left\{A_\alpha^\xi: h(\alpha) = \xi\right\}\), pairwise disjointedness is due to part (a) and each \(A_\alpha^\xi\) is non-stationary by our choice of \(h\).

4

Let \((L, \prec)\) be a dense linear ordering without end points. Show that \((L, \prec)\) is separable iff \((L, \prec)\) is order isomorphic to a sub-ordering of the real line \((\mathbb{R}, <)\).

Suppose \((L, \prec)\) is separable, then let \(M\subseteq L\) be countable dense subset, so every nonempty open interval in \(L\) contains an \(m\in M\). Clear that \((M,\prec)\) is still a linear order, we want to show that \((M,\prec)\) is dense. Let \(a,b\in M\), then there exists (by density of \((L,\prec)\)) \(c,d\in L\) with \(a \prec c \prec d \prec b\). By \(M\) being dense in \(L\) there exists \(e\in M\) with \(c \prec e \prec d\), this shows \((M, \prec)\) is dense. Then \((M,\prec)\) is isomorphic to \((\mathbb{Q}, <)\) and let \(f\) witness the isomorphism. Using continuity, \(f\) can be extended uniquely to get an isomorphism between \((L,\prec)\) and \((\mathbb{R},<)\).

Conversely suppose \(Y\subseteq \mathbb{R}\) such that \((L,\prec)\) is isomorphic to \((Y, <)\). If \(Y\) is countable we are done. If not we first consider the collection of real intervals \(S = \left\{\left(x-\frac 1n,x+\frac 1n\right): x\in\mathbb{Q}, n\in\omega\right\}\), for each \((a,b)\in S\) we choose \(z\in (a,b)\cap Y\) if the intersection is nonempty.

Let \(Z\) be the set consisting of all the chosen \(z\)’s and we prove that \(Z\) is a countable dense subset of \(Y\). It is immediate from construction that \(\left\lvert Z\right\rvert\leq \left\lvert S\right\rvert = \omega\). Let \(a, b \in Y\) with \(a < b\), then since \((Y,<)\) itself is dense choose \(c\in Y\) with \(a < c < b\). Let \(\varepsilon = \min(\left\lvert b-c\right\rvert,\left\lvert c-a\right\rvert) > 0\), and let \(n\in\omega\) such that \(\frac1n < \frac\varepsilon2\). Let \(x\in\mathbb{Q}\) such that \(\left\lvert x-c\right\rvert < \frac1n\), then \(c \in \left(x-\frac1n,x+\frac1n\right) \in S\), so \(\left(x-\frac1n,x+\frac1n\right) \cap Y\) is nonempty. Let \(z\in\left(x-\frac1n,x+\frac1n\right) \cap Y\) be chosen, then \(\left\lvert z-c\right\rvert < \frac2n < \varepsilon\) so \(z\) is still between \(a\) and \(b\).

Let \(g: L\to Y\) witness the isomorphism, then we can easily check that \(g^{-1}(Z)\) is a countable dense subset in \((L,\prec)\).

5

Let \((\mathbb{Q}, <)\) be the usual ordering of rationals. Show that there is a family \(\mathcal{F}\) of subsets of \(\mathbb{Q}\) such that \(\left\lvert\mathcal{F}\right\rvert = 2^\omega\) and for every \(A,B\in\mathcal{F}\), \((A,<)\ncong(B,<)\).

For any \(x\in\mathbb{Q}\) we let \(Z(x)\) denote a \(\mathbb{Z}\)-chain centered around \(x\) \[ Z(x) = \left\{ x\pm \left(1-\frac 1{n+1}\right) : n\in\omega \right\}, \] and when \(k\in\omega\), we let \(C(x,k)\) denote the \(k\)-chain around \(x\) \[ C(x,k) = \left\{ x + \frac{i}{k} : i< k \right\}. \]

Whenever \(X\) is an infinite subset of \(\omega\), let \(x_0, x_1, \dots\) be an increasing enumeration of elements of \(X\), and define a map \(F: [\omega]^\omega \to \mathcal{P}(\mathbb{Q})\) as \[ F(X) = \bigcup_{i<\omega} Z(2i)\cup C(2i+1, x_i). \] \(F\) is clearly injective, so set \(\mathcal{F} = \operatorname{range}(F)\) and we have \(\left\lvert\mathcal{F}\right\rvert = 2^\omega\).

Let \(A,B\in\mathcal{F}\), we want to show that \((A,<)\ncong(B,<)\). Let \(X,Y\subseteq \omega\) be infinite such that \(F(X) = A\) and \(F(Y)=B\). Since \(A \ne B\), \(X \ne Y\), without loss of generality let \(x\in X\), \(x\notin Y\), then \(A\) has a finite chain of exactly \(x\) elements while \(B\) does not. To complete the proof, we just need to observe that when \(x\in\omega\) is fixed, the statement expressing “there exists a chain with exactly \(x\) elements where the least member of the chain has no predecessor and the greatest member of the chain has no successor” is first-order definable.