1

Show that if \(\alpha\cdot\alpha =\beta\cdot\beta\), then \(\alpha = \beta\).

Without loss of generality assume \(\alpha < \beta\), as ordinal multiplication is weakly monotonic over its left argument we have \[ \alpha\cdot\beta \leq \beta\cdot\beta \] ordinal multiplication is strictly increasing over the right operand so we have \[ \alpha\cdot\alpha < \alpha\cdot\beta \] compose inequalities to get \(\alpha\cdot\alpha < \beta\cdot\beta\). \(\square\)

2

Suppose \(\kappa\) is a infinite cardinal and \(\prec\) is a well ordering on \(\kappa\). Show that there exists \(X\subseteq \kappa\) such that \(\left\lvert X\right\rvert = \kappa\) and for every \(\alpha,\beta\) in \(X\), it follows that \(\alpha < \beta\) iff \(\alpha\prec\beta\).

In the case that \(\kappa\) is regular we can basically reuse the argument in Homework 1 Question 3. Without loss of generality (by only considering initial segments) we can assume \(\operatorname{type}(\kappa,\prec) = \kappa\). Let \(X\subseteq \kappa\) be any maximal subset such that \(<\) and \(\prec\) agree and suppose for a contradiction \(\left\lvert X\right\rvert < \kappa\), then both the \(<\) and \(\prec\)-downward closures of \(X\) are of size strictly less than \(\kappa\), and there exists an element above \(A\) under both \(<\) and \(\prec\), contradicting maximality.

In the case where \(\kappa\) is singular, Let \(\lambda = \operatorname{cf}(\kappa)\) and \(f: \lambda\to\kappa\) be a strictly increasing cofinal map, then because \(\kappa\) is singular, we can define a cofinal map \(g: \lambda\to\kappa\) in a fashion similar to lemma 6.5 as \[ g(\xi) = \max\left( \left\lvert f(\xi)\right\rvert^+, \left\lvert\sup\left\{ g(\eta): \eta < \xi \right\}\right\rvert^+ \right) \] then \(\kappa = \bigcup_{\alpha<\lambda} g(\alpha)\) and note that \(g\) is strictly increasing and only outputs regular cardinals. Proceed to clean up \(g\) by defining \(h: \lambda\to\mathcal{P}(\kappa)\) as \[ h(\xi) = g(\xi)\setminus\bigcup\left\{g(\eta):\eta <\xi\right\} \] and we still can express \(\kappa\) as the union \(\kappa = \bigcup_{\alpha<\lambda} h(\alpha)\). We achieve the following

• \(\alpha<\beta\) implies for every \(\gamma\in h(\alpha), \delta\in h(\beta)\), we have \(\gamma<\delta\),

• \(\left\lvert h(\alpha)\right\rvert = g(\alpha)\) for each \(\alpha\).

Again without loss of generality (by considering \(\prec\)-initial segments) we can assume \(\operatorname{type}(\kappa,\prec) = \kappa\) and \(\operatorname{type}\left(h(\alpha),\prec\right) = g(\alpha)\) at each \(\alpha\). Define the order \(\triangleleft\) on \(\lambda\) as \[ \alpha \triangleleft\beta \iff \sup_\prec(h(\alpha)) \prec \sup_\prec(h(\beta)) \] the two \(\sup\)s are distinct as each \(\left\lvert h(\alpha)\right\rvert\) is regular, and from here it is easy to see that \(\triangleleft\) is a well order.

As \(\lambda\) is in fact a regular cardinal, we can use the earlier case to obtain a cofinal set \(\left\{t_\alpha: \alpha<\lambda\right\}\) where \(<\) and \(\triangleleft\) agree. Note that at each \(t_\alpha\) there exists \(W_{t_\alpha} \subseteq h(t_\alpha)\) with size \(\left\lvert h(t_\alpha)\right\rvert\) where \(<\) and \(\prec\) agree, and \(W_{t_\alpha}\) is also \(\prec\)-cofinal due to our assumption on \(\operatorname{type}(h(\alpha),\prec)\).

Now we recursively define \(X_\alpha\) for all \(\alpha<\lambda\) as \(\left\{x\in W_{t_\alpha}: \left(\forall\beta<\alpha\right)\left(\forall w\in X_{\beta}\right)\left(w\prec x\right)\right\}\). At every \(\alpha\), \(\left\lvert X_\alpha\right\rvert = \left\lvert W_{t_\alpha}\right\rvert\), because the number of elements we deleted from \(W_{t_\alpha}\) to get \(X_\alpha\) is less than \(\left\lvert W_{t_\alpha}\right\rvert\), and as a result \(X_\alpha\) is still \(\prec\)-cofinal. The deletion forces out the property that \[\alpha<\beta \implies \left(\forall \gamma\in X_\alpha, \delta\in X_\beta\right)\left(\gamma\prec\delta\right).\] Finally define \[X = \bigcup_{\alpha<\lambda} X_\alpha\] which has cardinality \(\kappa\) and by construction \(<\) agrees with \(\prec\) on \(X\). \(\square\)

3 Prove Schröder-Bernstein Theorem without AC

I shall reproduce Zermelo’s proof.

Suppose \(A\subseteq B\subseteq C\) are sets and suppose that \(f:C\to A\) is a bijection. Define \(Q = B\setminus \operatorname{Im}_f(C)\) and let \(\mathcal{F} = \left\{X\subseteq C: Q\cup \operatorname{Im}_f(X)\subseteq X\right\}\). Define \(T = \bigcap \mathcal{F}\).

(1) Verify that \(T\in \mathcal{F}\).

Which is to say that \(Q\cup \operatorname{Im}_f(T)\subseteq T\). Pick \(a\in Q\cup\operatorname{Im}_f(T)\), case \(a\in Q\) then \(a\in T\) as we can see that for all \(X\in \mathcal{F}, Q\subseteq X\). Case \(a\in \operatorname{Im}_f(T)\), for all \(X\in\mathcal{F}\), \(a\in X\), so \(f(a)\in X\), which means \(a\in T\) too.

(2) Show that \(T = Q\cup \operatorname{Im}_f(T)\).

Due to part 1 we already know that \(T\supseteq Q\cup \operatorname{Im}_f(T)\). Suppose for a contradiction the containment is proper, let \(w\in \left(T\setminus Q\right)\cap\left(T\setminus\operatorname{Im}_f(T)\right)\) and we know that all of the below hold

1. \(w\in T\)
2. \(w\notin B \lor w\in \operatorname{Im}_f(C)\)
3. \(w\notin \operatorname{Im}_f(T) \implies \left(\forall t\in T\right)\left(f(t)\ne w\right)\)

Case \(w\notin B\) for 2, then \(w\) lies outside the range of \(f\), and for the other case, \(f^{-1}(w) \notin T\) by 3 and \(w\notin Q\) by hypothesis, so we can delete \(w\) from \(T\) with \(T\setminus\left\{w\right\}\) still in \(\mathcal{F}\), that is \(Q\cup \operatorname{Im}_f(T\setminus\left\{w\right\}) \subseteq T\setminus\left\{w\right\}\). This contradicts \(T\) being minimal under set inclusion.

(3) Show that \(B = T\cup \left(\operatorname{Im}_f(C)\setminus \operatorname{Im}_f(T)\right)\) and conclude that \(\left\lvert C\right\rvert = \left\lvert B\right\rvert\)

Use part (2) to simplify the expression as \[\begin{align*} T\cup \left(\operatorname{Im}_f(C)\setminus \operatorname{Im}_f(T)\right) &= Q\cup\operatorname{Im}_f(T)\cup\left(\operatorname{Im}_f(C)\setminus \operatorname{Im}_f(T)\right) \\ &= Q\cup\operatorname{Im}_f(C) \\ &= \left(B\setminus\operatorname{Im}_f(C)\right)\cup\operatorname{Im}_f(C) \\ &= B \end{align*}\] because \(\operatorname{Im}_f(T) \subseteq \operatorname{Im}_f(C)\) and \(\operatorname{Im}_f(C)\subseteq A\subseteq B\).

To see that \(\left\lvert C\right\rvert = \left\lvert B\right\rvert\), define \(g: C\to B\) as \[ g(c) = \begin{cases} f(c) &\text{if } c\notin T\\ c &\text{if } c\in T \end{cases}\] The two cases do not collide, that is \(\operatorname{Im}_g(T) = T\) and \(\operatorname{Im}_g(C\setminus T) = \operatorname{Im}_f(C)\setminus\operatorname{Im}_f(T)\) are disjoint, since \(x\in \operatorname{Im}_f(C)\) implies \(x\notin Q\) and we also have \(x\notin \operatorname{Im}_f(T)\). It is trivial to see that \(g\) is injective and the decomposition of \(B\) as a disjoint union \(T\cup \left(\operatorname{Im}_f(C)\setminus \operatorname{Im}_f(T)\right)\) helps us see that \(g\) is also surjective which completes the proof.

(4) Schröder-Bernstein theorem reduces to (3)

Let \(f: X\to Y\) and \(g: Y\to X\) be injective functions, we want to show that \(\left\lvert X\right\rvert = \left\lvert Y\right\rvert\). To use propositions above we make the following connections

• identify \(Y\) with \(C\)
• identify \(\operatorname{ran}(f)\) with \(B\)
• identify \(\operatorname{Im}_f\left(\operatorname{ran}\left(g\right)\right)\) with \(A\)

and we have \(\left\lvert Y\right\rvert = \left\lvert C\right\rvert = \left\lvert\operatorname{ran}(f)\right\rvert = \left\lvert X\right\rvert\). \(\square\)

4

Assume CH. Show that \(\left(\omega_n\right)^\omega = \omega_n\) for every \(1\leq n < \omega\).

By CH \(\left(\omega_1\right)^\omega = 2^{\omega^\omega} = 2^\omega = \omega_1\).

Each \(\omega_n\) is regular so \(\omega < \operatorname{cf}(\omega_n) = \omega_n\), let \(n>2\) and assume result holds for \(n-1\), then \[ {}^\omega \omega_n = \bigcup_{\alpha<\omega_n} {}^\omega\alpha \] note that for each \(\alpha\), \(\alpha^\omega \leq \left(\omega_{n-1}\right)^\omega = \omega^{n-1}\) by induction hypothesis. This means \(\left(\omega_n\right)^\omega \leq \omega_n\). \(\square\)

5

Prove that the following statement is equivalent to CH. There exists \(X\subseteq \mathbb{R}^2\) such that \(X\) meets every vertical line on a countable set and \(\mathbb{R}^2\setminus X\) meets every horizontal line on a countable set.

Assume CH, then \(\left\lvert\mathbb{R}\right\rvert = \omega_1\). Let \(\mathbb{R}= \left\{t_{\alpha}: \alpha < \omega_1\right\}\) be a well ordering. Define \[ X = \left\{\left(t_\alpha,t_\beta\right): \alpha \geq \beta \right\}. \] To see that \(X\) meets every vertical line on a countable set, fix \(x\) and let \(\alpha\) such that \(x = t_\alpha\), then by definition of \(X\) there are exactly \(\left\lvert\alpha\right\rvert\) many points with \(x = t_\alpha\), and since \(\alpha < \omega_1\), it follows that the intersection is countable. Similarly fix \(y\) and let \(\beta\) such that \(y = t_\beta\), we observe that \(\left(t_\alpha, t_\beta\right)\in \mathbb{R}^2\setminus X\) whenever \(\alpha < \beta\), so \(\mathbb{R}^2\setminus X\) meets the horizontal line on less than \(\left\lvert\beta\right\rvert = \omega\) points too.

Assume \(X\) exists with the property, let \(A\subset \mathbb{R}\) be of size \(\left\lvert A\right\rvert = \omega_1\). We consider the subset of the \(X\) given by \[ S = \left(A\times \mathbb{R}\right)\cap X \] size of \(S\) is \(\omega_1\cdot\omega_0 = \omega_1\). Define \(S_Y = \left\{y:\left(\exists x\in\mathbb{R}\right)\left((x,y)\in S\right)\right\}\), claim is \(S_Y = \mathbb{R}\). To see this, let \(y\in\mathbb{R}\) and notice that by hypothesis, the set \[ \left\{x: (x,y)\in \mathbb{R}\setminus X\right\} \] is only countable which means there must exist \(x\in\mathbb{R}\) with \((x,y)\in S\). Then we have \[2^{\omega_0} = \left\lvert\mathbb{R}\right\rvert = \left\lvert S_Y\right\rvert \leq \left\lvert S\right\rvert \leq \left\lvert X\right\rvert = \omega_1 \] which shows CH. \(\square\)