Supplementary Exercises*: Well-Ordering: Problem 8 Solution

Working problems is a crucial part of learning mathematics. No one can learn topology merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Using Exercises 1-4, construct an uncountable well-ordered set, as follows. Let $\mathcal{A}$ be the collection of all pairs $(A,<)$ , where $A$ is a subset of $\mathbb{Z}_{+}$ and $<$ is a well-ordering of $A$ . (We allow $A$ to be empty.) Define $(A,<)\sim(A',<')$ if $(A,<)$ and $(A',<')$ have the same order type. It is trivial to show this is an equivalence relation. Let $[(A,<)]$ denote the equivalence class of $(A,<)$ ; let $E$ denote the collection of these equivalence classes. Define $[(A,<)]\ll[(A',<')]$ if $(A,<)$ has the order type of a section of $(A',<')$ .

(a) Show that the relation $\ll$ is well defined and is a simple order on $E$ . Note that the equivalence class $[(\emptyset,\emptyset)]$ is the smallest element of $E$ .

(b) Show that if $\alpha=[(A,<)]$ is an element of $E$ , then $(A,<)$ has the same order type as the section $S_{\alpha}(E)$ of $E$ by $\alpha$ . [Hint: Define a map $f:A\rightarrow E$ by setting $f(x)=[(S_{x}(A),\mbox{ restriction of <})]$ for each $x\in A$ .]

(d) Show that $E$ is uncountable. [Hint: If $h:E\rightarrow\mathbb{Z}_{+}$ is a bijection, then $h$ gives rise to a well-ordering of $\mathbb{Z}_{+}$ .]

(a) "Well defined" means that the relation does not depend on the choice of $(A,<)$ representing a class. It does not, as all pairs in one class have the same order type. Then, using Exercises 2(b) and 4(a), the relation is non-reflexive and every two equivalence classes are comparable. Finally, transitivity follows from the fact that a section of a section is a section.

(b) Define the map $f$ as in the hint. This is an order preserving injection, as if $x<y$ then $S_{x}(A)$ is a section of $S_{y}(A)$ . Moreover, for every $x\in A$ , $f(x)$ is a subsection of $A$ , so $f(x)\in S_{\alpha}(E)$ . Now, if $[(B,<')]\ll\alpha$ , then there is an order preserving bijection from $B$ onto a section $S_{\gamma}(A)$ , and $f(\gamma)=[(B,<')]$ . Therefore, $f:A\rightarrow$ $f(A)=S_{[(A,<)]}(E)$ is an order preserving bijection from $(A,<)$ onto $S_{[(A,<)]}(E)$ .

(c) Take any element $\alpha=[(A,<)]$ of a nonempty subset $B\subset E$ . If $\alpha$ is not the smallest element of $B$ ( $B\cap S_{\alpha}(E)$ is not empty), we show that there is one. $(A,<)$ has the same order type as $S_{\alpha}(E)$ , and there is the order preserving bijection $f$ defined in (b). Then, $f(smallest[f^{-1}(B\cap S_{\alpha}(E))])$ is the smallest element in $B$ . (Simply said, by (b), every section of $E$ is well-ordered, hence, so is $E$ .)

(d) $E$ is infinite, as $e_{n}=[(\{1,\ldots,n\},<)]\in E$ for every $n\in\mathbb{Z}_{+}$ , and for $m\neq n$ , $e_{m}$ and $e_{n}$ have different order types (for example, Exercise 2(b)). Suppose $E$ is countable and $h:E\rightarrow\mathbb{Z}_{+}$ is a bijection. Define the order $\prec$ on $\mathbb{Z}_{+}$ such that $x\prec y$ iff $h^{-1}(x)\ll h^{-1}(y)$ . This is a well-ordering, and it has the same type as $\ll$ on $E$ ( $h$ is an order preserving bijection). But from (b) we know that $[(\mathbb{Z}_{+},\prec)]$ has the same order type as $S_{[(\mathbb{Z}_{+},\prec)]}(E)$ . Therefore, we conclude that $(E,\ll)$ has the same order type as one of its sections. Contradiction to Exercise 2(b). Hence, there is no bijection of $E$ with $\mathbb{Z}_{+}$ , and $E$ is uncountable.

Note, by the way, that for any $\alpha=[(A,<)]\in E$ , $S_{\alpha}(E)$ has the same order type as $(A,<)$ , and $A$ is countable. Therefore, by Exercise 4(b), the constructed well-ordered set is the minimal uncountable well-ordered set.

The same argument as in (d) can be applied to any other set $X$ . We start by considering all possible well-orderings on subsets of $X$ (including $X$ itself and the empty set). We define the set $E$ of the classes of well-ordered subsets having the same order type, define the well-ordering $\ll$ on $E$ as before, and show that each element of each class has the same order type as the section of $E$ by this class. Since $E$ includes all possible well-orderings on $X$ , neither one can have the same order type as the constructed well-ordering on $E$ , otherwise $E$ would have the same order type as one of its sections. Therefore, $(E,\ll)$ is a well-ordered set having greater cardinality than $X$ (if they had the same cardinality there would be a bijection giving rise to a well-ordering on $X$ having the same order type as $E$ ; the argument is the same as in (d)).

For example, let us start with the empty set $X_{1}=\emptyset$ . It has one well-ordered subset, and $E_{1}=\{[(\emptyset,\emptyset)]\}$ . Let us denote $[(\emptyset,\emptyset)]$ by the symbol $1$ . Now, $\ll_{1}$ on $E_{1}$ is empty, hence, we have a one-element well-ordered set $(E_{1},\ll_{1})=(\{1\},\emptyset)$ . Further, let the one element set $X_{2}=E_{1}=\{1\}$ . Then, there are two well-ordered subsets of $X_{2}$ , and $E_{2}=\{[(\emptyset,\emptyset)],[(\{1\},\emptyset)]\},$ where $[(\emptyset,\emptyset)]\ll_{2}[(\{1\},\emptyset)]$ as $(\emptyset,\emptyset)$ has the order type of $(S_{1}(\{1\})=\emptyset,\emptyset)$ . Let us denote $[(\{1\},\emptyset)]$ by the symbol $2$ . The constructed $(E_{2},\ll_{2})=(\{1,2\},\{(1,2)\})$ is a well-ordered two-element set, where $1\ll_{2}2$ . Now, having a two-element set $X_{3}=E_{2}=\{1,2\}$ , there are five well-ordered subsets of $X_{3}$ (can you name them all?), but only three classes of equivalent well-orderings (this is where the equivalence of well-orderings starts mattering). Moreover, the type of the order depends only on the number of elements in the subset (Theorem 10.1), and for different numbers of elements we have different orders (Exercise 2(b)). Hence, as representatives for the classes of equivalent well-orderings we can choose $\emptyset$ , $\{1\}$ and $\{1,2\}$ . Therefore, we have $E_{3}=\{[(\emptyset,\emptyset)],[(\{1\},\emptyset)],[(\{1,2\},\{(1,2)\})]\}.$ Let us denote $[(\{1,2\},\{(1,2)\})]$ by the symbol $3$ . Then, clearly, $1\ll_{3}2\ll_{3}3$ . The constructed $(E_{3},\ll_{3})=(\{1,2,3\},\{(1,2),(1,3),(2,3)\})$ is a well-ordered three-element set. We can continue this way. Having an $(n-1)$ -element set $X_{n}=\{1,2,\ldots,n-1\}$ , the set of all well-ordered subsets of $X_{n}$ consists of approximately $(n-1)!e$ ( $n>1$ ) well-ordered subsets, where each class of equivalent $k$ -element subsets consists of $k!$ subsets. Then, the set $E_{n}=\{1,2,\ldots,n-1,[(X_{n},<)]\}$ where $<$ is the usual order. We denote $[(X_{n},<)]$ by $n$ . Then, $(E_{n},\ll_{n})=(X_{n+1}=\{1,2,\ldots,n\},<).$ Now, let $X_{\omega}$ be the set of all $[(X_{n},<)]=n$ , $X_{\omega}=\{1,2,\ldots\}$ . Then, the classes of equivalent well-ordered subsets of $X_{\omega}$ include all finite well-orderings, i.e. $1,2,\ldots$ , as well as all order types of countably infinite well-orderings. What we prove in (d) is that there are uncountably many countably infinite order types, and $E_{\omega}$ is uncountable.

Subpages

Supplementary Exercises*: Well-Ordering: Problem 8 Solution

Supplementary Exercises*: Well-Ordering: Problem 8 Solution