1

Suppose \(\left\langle X_n:n<\omega\right\rangle\) is a sequence of infinite sets. Show that there is a sequence \(\left\langle Y_n:n<\omega\right\rangle\) of pairwise disjoint sets such that for every \(n<\omega\), \(Y_n\subseteq X_n\) and \(\left\lvert Y_n\right\rvert = \left\lvert X_n\right\rvert\).

Let the cardinalities of the sets in the sequence be \(\omega\leq \kappa_1 < \kappa_2 < \kappa_3 < \dots\), then we can easily obtain a sequence where \(Y_i\subseteq X_i\) and \(\left\lvert Y_i\right\rvert \ne \left\lvert Y_j\right\rvert \implies Y_i \cap Y_j = 0\). This can be achieved by doing

• for all \(i\) where \(\left\lvert X_i\right\rvert = \kappa_1\), set \(Y_i = X_i\),

• for each \(n > 2\), for all \(i\) where \(\left\lvert X_i\right\rvert = \kappa_n\), set \(Y_i = X_i \setminus\bigcup\left\{X_j: \left\lvert X_j\right\rvert \leq \kappa_{n-1}\right\}\).

Hence without loss of generality we can assume that in the sequence, sets of different cardinalities do not intersect. By refining the resultant sequence at each cardinality, we can reduce to the case where all the \(X_i\) are of the same size \(\kappa\). Then it suffices to prove that given a sequence \(\left\langle X_n:n<\omega\right\rangle\) of subsets of \(\kappa\) where \(\left\lvert X_i\right\rvert = \kappa\) for all \(i\), we can create a disjoint refinement.

Given two sequences \(A = \left\langle A_n:n<\omega\right\rangle\) and \(B = \left\langle b_n:n<\omega\right\rangle\) we let \(\operatorname{acc}(A,B) = \left\langle A_n\cup\left\{b_n\right\}: n<\omega\right\rangle\).

Define \(f:\kappa \to {}^\omega\kappa\) by

\[\begin{align*} f(0) &= \left\langle\left\{\min(X_0)\right\},0, 0, \dots\right\rangle \\ f(n+1) &= \left( \begin{aligned} \textbf{ let } D &= \bigcup \operatorname{range}(f(n)) \\ y_0 &= \min(X_0\setminus D) \\ y_1 &= \min(X_1\setminus D\setminus\left\{y_0\right\}) \\ y_2 &= \min(X_2\setminus D\setminus\left\{y_0,y_1\right\}) \\ &\dots\\ y_{n+1} &= \min(X_{n+1}\setminus D\setminus\left\{y_0,y_1,\dots,y_n\right\}) \textbf{ in }\\ &\operatorname{acc}\left(f(n), \left\langle{y_0},{y_1},\dots,{y_{n+1}},0,0,\dots\right\rangle\right) \end{aligned} \right) \end{align*}\] whenever \(n<\omega\), \[ f(\alpha)(i) = \bigcup_{\beta<\alpha} f(\beta)(i) \] whenever \(\alpha\) is a limit ordinal and \(i<\omega\), and \[\begin{align*} f(\alpha+1) &= \left( \begin{aligned} \textbf{ let } D &= \bigcup \operatorname{range}(f(\alpha)) \\ y_0 &= \min(X_0\setminus D) \\ y_{n+1} &= \min\left(X_{n+1}\setminus\left(D\cup\left\{y_0,y_1,\dots,y_n\right\}\right)\right) \textbf{ in }\\ &\operatorname{acc}\left(f(\alpha), \left\langle y_i: i<\omega\right\rangle\right) \end{aligned} \right) \end{align*}\] whenever \(\alpha\geq\omega\).

Finally let \(Y_i = \bigcup_{\beta<\kappa} f(\beta)(i)\) and the pairwise disjointedness and containment properties arise from construction.

For each \(n<\omega\), we see that \(f(n+1)\) is well-defined, as \(\left\lvert D\right\rvert < \omega \leq \left\lvert X_i\right\rvert\) for any \(X_i\). Next we see that in the sequence \(f(\omega)\), each \(f(\omega)(i)\) has size \(\omega\), this observation also completes the proof in the case \(\kappa=\omega\).

For any \(i<\omega\) we want to show that \(\left\lvert\alpha\right\rvert \geq \left\lvert f(\alpha)(i)\right\rvert\) for all \(\alpha\geq\omega\). Proceed by induction and the successor case is obvious. When \(\alpha\) is a limit, then \[ \left\lvert f(\alpha)(i)\right\rvert = \left\lvert\bigcup_{\beta<\alpha} f(\beta)(i)\right\rvert = \left\lvert\alpha\right\rvert \] as each \(\left\lvert f(\beta)(i)\right\rvert \leq \left\lvert\beta\right\rvert\leq\left\lvert\alpha\right\rvert\). This means \(f(\alpha+1)\) is also well defined for any \(\alpha\geq\omega\) as \(\left\lvert D\right\rvert \leq \left\lvert\alpha\right\rvert < \kappa\).

Note that we are in the case that \(\kappa>\omega\) and we still need to prove that for each \(i<\omega\), \(\left\lvert Y_i\right\rvert = \left\lvert\kappa\right\rvert\), it suffices to define an injective function \(g: \left(\kappa\setminus\omega\right) \to Y_i\), which we can do by defining \(g(\alpha)\) to be the only element of \(f(\alpha+1)(i)\setminus f(\alpha)(i)\).

2

Use transfinite recursion to construct \(X \subseteq \mathbb{R}^2\) such that \(X\) intersects every line in \(\mathbb{R}^2\) at exactly two points.

Let \(<\) be a well ordering of lines in \(\mathbb{R}^2\) with the order type exactly \(\left\lvert\mathbb{R}\right\rvert\) and \(\prec\) a well ordering of points in \(\mathbb{R}^2\).

Suppose \(l\) is a line and at stage \(l\), \(X_l\) is a set of points satisfying

• no 3 points in \(X_l\) are colinear,

• \(l'<l\) implies \(l' \in L(X_l)\) the set of all lines generated by points in \(X_l\).

First note that for any line \(l\), let \(Y_l = \bigcup L(X_l)\) denote the span and we have \[ \left\lvert Y_l \cap l\right\rvert = \left\lvert\bigcup_{l'\in L(X_l)} l'\cap l\right\rvert \leq \left\lvert L(X_l)\right\rvert \leq [X_l]^2 < \left\lvert\mathbb{R}\right\rvert = \left\lvert l\right\rvert \] whenever \(l\notin L(X_l)\).

Then we define \(X_{S(l)}\) as

• if \(l \in L(X_l)\) then \(X_{S(l)} = X_l\),

• if \(l\cap Y_l \ne 0\) then choose a minimum point \(a\in l\setminus Y_l\) and set \(X_{S(l)} = X_l\cup\left\{a\right\}\),

• if \(l\cap Y_l = 0\) then choose two minimum points \(a,b\in l\setminus Y_l\) and set \(X_{S(l)} = X_l\cup\left\{a,b\right\}\),

and when \(l\) corresponds to a limit ordinal, then define \[ X_l = \bigcup_{l'<l} X_{l'}. \]

We start the induction by setting, where \(m\) is the minimal line \(X_m = 0\), and notice that the invariant is preserved throughout.

Define \(X\) as the final union and observe that no 3 points are colinear in \(X\), otherwise they would occur in some \(X_l\). Also all lines are taken care of so \(X\) intersects every line at exactly two points.

3

Let \(\kappa\) be an infinite cardinal and suppose \(\lambda\) is the least cardinal such that \(\kappa^\lambda > \kappa\). Show that \(\lambda\) is a regular cardinal.

Suppose \(\lambda\) is singular (\(\lambda\) obviously cannot be finite), we can decompose \(\lambda\) (in a fashion similar to Homework 2 Q2) as \[ \lambda = \bigcup_{\eta<\operatorname{cf}(\lambda)} X_\eta \] where each \(\left\lvert X_\eta\right\rvert < \lambda\). We can verify by chasing elements that \[ \left\lvert{}^\lambda\kappa\right\rvert \leq \left\lvert\prod_{\eta<\operatorname{cf}(\lambda)} {}^{X_\eta}\kappa\right\rvert \] and at each \(\eta\), we have \(\left\lvert{}^{X_\eta}\kappa\right\rvert \leq \kappa\) which can be used to get the bound \(\kappa^\lambda \leq \kappa^{\operatorname{cf}(\lambda)} \leq \kappa\), a contradiction.

4

Let \(\kappa\) be an infinite cardinal. Show that there is a family \(\mathcal{A}\) of subsets of \(\kappa\) such that \(\left\lvert\mathcal{A}\right\rvert = \kappa^+\) and for every \(X,Y\in\mathcal{A}\), either \(X\subseteq Y\) or \(Y\subseteq X\).

Following hint, let \(\lambda\) be the least cardinal such that \(2^\lambda > \kappa\). Let \(\prec\) be the following linear order on \({}^\lambda 2\): \(f\prec g\) iff \(\left(\exists \alpha<\lambda\right)\left(f\upharpoonright\alpha = g\upharpoonright\alpha \land f(\alpha) < g(\alpha)\right)\). Let \(D\) be the set of all \(f\in{}^\lambda 2\) such that \(f\) is eventually \(0\). For \(f\in {}^\lambda2\), let \(A_f = \left\{g\in D: g\preccurlyeq f\right\}\).

First let \(f, g\in{}^\lambda2\) where \(f\prec g\), and we want to show that \(A_f \subsetneq A_g\). The containment is clear as \(h\in D, h\preccurlyeq f\implies h\preccurlyeq g\). Case \(g\in D\) then clearly \(g\notin A_f\), when \(g\notin D\) let \(\alpha<\lambda\) such that \(f\upharpoonright\alpha = g\upharpoonright\alpha\) and \(f(\alpha) < g(\alpha)\), let \(\beta>\alpha\) be minimal such that \(g(\beta) = 1\), we produce \(h\in D\) by \[ h(\gamma) = \begin{cases} g(\gamma)&\text{if }\gamma < \beta\\ 0&\text{if }\gamma \geq \beta \end{cases} \] and note that \(f\prec h\) because \(h(\alpha) = g(\alpha)\), also \(h\prec g\) since \(g\notin D\), this shows properness of containment.

Note that since \(\kappa < 2^\kappa\), \(\lambda \leq \kappa\). In addition, by definition we can see a natural injection from \(D\) into \(\bigcup_{\alpha<\lambda} {}^\alpha2\), and for each \(\alpha<\lambda\), we have \(2^\alpha \leq \kappa\) by minimality of \(\lambda\). Then \[ \left\lvert D\right\rvert \leq \left\lvert\bigcup_{\alpha<\lambda} 2^\alpha\right\rvert \leq \kappa \] and let \(i:D\to\kappa\) be injective.

Define \(F:{}^\lambda2\to\mathcal{P}(\kappa)\) as \(f\mapsto i(A_f)\) which is injective, so \(\left\lvert\operatorname{range}(F)\right\rvert = 2^\lambda > \kappa\). For any \(i(A_f), i(A_g) \in \operatorname{range}(F)\), we have \(A_f\subseteq A_g\) or \(A_g \subseteq A_f\) and this property is still preserved after taking the image of an injective mapping, so \(\operatorname{range}(F)\) is a family with size at least \(\kappa^+\) satisfying the property. We let \(\mathcal{A}\) be any subset of \(\operatorname{range}(F)\) with size exactly \(\kappa^+\) and complete the proof by making the observation that the property still holds for any infinite subset of \(\operatorname{range}(F)\).

5

Let \(\mathcal{F}\) be a filter on \(X\). Show that there is a filter \(\mathcal{U}\) on \(X\) such that \(\mathcal{F}\subseteq \mathcal{U}\) and for every \(Y\subseteq X\), either \(Y\in\mathcal{U}\) or \(X\setminus Y\in \mathcal{U}\).

Define \(\mathscr{A} = \left\{\mathcal{G}: \mathcal{G}\text{ is a filter on }X\right\}\), which is partially ordered by inclusion. Let \(C\subseteq \mathscr{A}\) be a chain and we want to show that \(\bigcup C \in \mathscr{A}\), that is \(\bigcup C\) is a filter on \(X\),

1. for all \(\mathcal{G}\in C\), \(0\notin \mathcal{G}\) and \(X\in \mathcal{G}\), so \(0\notin \bigcup C\) and \(X\in \bigcup C\),

2. for all \(A,B\in\bigcup C\), let \(A\in \mathcal{G}_A\in C\) and \(B\in \mathcal{G}_B\in C\), since \(C\) is a chain without loss of generality let \(\mathcal{G}_A\subseteq \mathcal{G}_B\), then \(A\cap B\in \mathcal{G}_B\) which means \(A \cap B \in \bigcup C\),

3. for all \(A\subseteq B\subseteq X\), if \(A\in\bigcup C\) then let \(A\in \mathcal{G}_A\in C\), then \(B\in G_A\) which means \(B \in \bigcup C\).

As every chain \(C\) is bounded above by \(\bigcup C\) in \(\mathscr{A}\), we can apply Zorn’s lemma and let \(\mathcal{U}\supseteq\mathcal{F}\) be the maximal element above \(\mathcal{F}\) in \(\mathscr{A}\).

We now show that \(\mathcal{U}\) has the ultrafilter property. Suppose not, let \(Y\subseteq X\) with \(Y\notin \mathcal{U}\) and \(X\setminus Y\notin \mathcal{U}\). Let \(Z\in\mathcal{U}\) and we have \(Z\cap Y \ne 0\), otherwise \(Z \subseteq X\setminus Y\). Since \(Y\) meets every \(Y\in\mathcal{U}\) on a nonempty set the upward closure of \(\mathcal{U}\cup\left\{Z\right\}\) is a filter which contradicts maximality of \(\mathcal{U}\).