# set theory problems (well-ordered sets, countability, Zorn's Lemma, …)

1. Let $A \subseteq P(\omega)$, where $\omega$ is the set of all natural numbers and $P(\omega)$ is the power set of $\omega$. If $\langle A,\subseteq\rangle$ is a well ordered set how can you prove that $A$ is a countable set.

2. Let $A$ be a set which elements are closed sets of real numbers. If $\langle A,\subseteq\rangle$ is a well ordered set how can you prove that $A$ is a countable set.

3. How can you prove that Zorn's lemma (so and the axiom of choice) is equivalent to that for every partially ordered set $\langle A,\le\rangle$ that satisfies Zorn's condition, for every $b\in A$ there exists a maximum element $a$ for which $b\le a$.

• I'll wager 3 has to be "maximal element $a$"; otherwise, the statement would assert that Zorn's condition implies the existence of a maximum. – Arturo Magidin Feb 25 '11 at 16:37
• And please say what you've tried or where you are stuck. – Arturo Magidin Feb 25 '11 at 16:38

1. Since $A$ is well-ordered, we can order-biject it with an ordinal $\beta$, $f\colon \beta\to A$. Now, you can use $f$ to define an injection from $\beta$ to $\omega$ by letting $g(\alpha)$ be the least element of $f(\alpha+1)-f(\alpha)$. Show that $g$ is an injection, and therefore $\beta$ is countable.
2. Consider the set of complements, which are open, and well ordered by $\supseteq$. Show that there is always a rational that is in one set but not in its $\supseteq$-successor, and that you can pick distinct rationals at each stage (that is, define an injection from $A$ to $\mathbb{Q}$).
3. Replacing "maximum element $a$" with "maximal element $a$", assuming Zorn's Lemma and given $\langle A,\leq\rangle$ and $b$, look at $\mathcal{C}=\{x\in A\mid x\geq b\}$ and apply Zorn's Lemma to it. For the converse, pick an arbitrary $b\in A$ and conclude the original set has maximal elements.