General Topology – How Can a Single Element Affect Countability of a Set Section?

general-topology

I'm reading Munkres' Topology book, and confused by Lemma 10.2:

Theorem. There exists a well-ordered set $A$ having a largest element $\Omega$, such that the section $S_{\Omega}$ of $A$ by $\Omega$ is uncountable, but every other section of $A$ is countable.

Proof.$\quad$We begin with an uncountable well-ordered set $B$. Let $C$ be the well-ordered set $\{1,2\}\times B$ in the dictionary order; then some section of $C$ is uncountable. (Indeed, the section of $C$ by any element of the form $2\times b$ is uncountable.) Let $\Omega$ be the smallest element of $C$ for which the section of $C$ by $\Omega$ is uncountable. Then let $A$ consist of this section along with the element $\Omega$. $\Box$

Relevant definitions:

If a set $X$ is "well-ordered", it means that any non-empty subset of $X$ has a smallest element.

For a well-ordered set $X$, a "section" of $X$ by $a \in X$ is the set $S_a = \{x \in X \mid x < a\}$.

The dictionary order on $X \times Y$ is the ordering where $x_1 \times y_1 < x_2 \times y_2$ if $x_1 <_X x_2$, or if $x_1 = x_2$ and $y_1 <_Y y_2$.

In the proof, I see why the section of $C$ by any element $2 \times b$ is uncountable, because in the dictionary ordering, all elements of the form $1 \times b$ are smaller than it, and there are uncountably many of those (since it's basically just a copy of $B$).

But why does $C$ necessarily have a smallest element $\Omega$ such that the section of $C$ by it is uncountable?

Is there a clear example of such a set $A$?

(I suspect part of my confusion is that this seems to rely on the Well-ordering theorem, which says that any set (countable or not) has an order relation that makes it a well-ordered set, but gives no way of finding it. So trying to come up with an example for this is difficult because $B$ is an uncountable, well-ordered set.)

edit: after the fact I found this question where they ask nearly the identical thing from the book.

Best Answer

I thought Noah Schweber's suggestion is excellent, and it might be easier to think about this if we consider an analogous but simpler application of the same ideas. Let's say that $\omega$ is simply the natural numbers: $$\omega = \{0,1,2,3,\ldots\}$$

The fact that $\omega$ is well-ordered should be plausible. Maybe try a couple of examples if you're not sure. Does the set of all prime odd numbers have a smallest element? The set of all house numbers in your town?

Now let's consider something analogous to the $C = \{1, 2\}\times B$ from Munkres, but a little easier. Consider $$T = \{\color{darkred}{\text{red}}, \color{darkblue}{\text{blue}}\} \times \omega.$$ $T$ is an infinite set that looks like this:

$$T = \{\color{darkred}{0,1,2,3,\ldots}, \color{darkblue}{0,1,2,3,\ldots} \}.$$

It's just two copies of $\omega$, one red and one blue, with the red numbers considered to be smaller than the blue ones. From reading your question I think you understand this well already.

Notice that $T$ is also well-ordered. Why? (Maybe prove this yourself; it's not hard.)

Suppose we have a nonempty subset $S\subset T$. Then it must be all blue, or it must have some red elements. If it's all blue then it's a nonempty subset of $\{\color{darkblue}{0,1,2,3,\ldots}\}$, so it certainly has a smallest element. And if it has any red elements then $S\cap \{\color{darkred}{0,1,2,3,\ldots}\}$ is a nonempty subset of $\{\color{darkred}{0,1,2,3,\ldots}\}$ and that certainly has a smallest element which, being smaller than any blue elements of $S$, will be the smallest element of $S$ itself.

Now let's get back to Munkres. The thing in Munkres that is giving you trouble is:

Let $\Omega$ be the smallest element of $C$ for which the section of $C$ by $\Omega$ is uncountable.

The analogous thing for $T$ is:

Let $w$ be the smallest element of $T$ for which the section of $T$ by $w$ is infinite.

Let's think about what sections of $T$ are like. The section of a red number $\color{darkred}{r}$ is all the elements of $T$ that are less than $\color{darkred}{r}$. For example the section of red $\color{darkred}{4}$ is $$\color{darkred}{\{0,1,2,3\}}.$$

The section of a blue number $\color{darkblue}{b}$ is all the elements of $T$ that are less than $\color{darkblue}{b}$. This will include all the red numbers, because every red number is less than every blue number. And it might include some blue numbers also. For example the section of blue $\color{darkblue}{2}$ is $$\{\color{darkred}{0,1,2,3,\ldots}, \color{darkblue}{0,1}\}.$$

It should be clear that some of the elements of $T$ have finite sections and some have infinite sections. In the examples above, the section of red $\color{darkred}{4}$ was finite and the section of blue $\color{darkblue}{2}$ was infinite.

Now let $I$ be the subset of all elements of $T$ that have an infinite section. We proved above that every nonempty subset of $T$ has a smallest element. $I$ is a nonempty subset of $T$ (since it contains blue $\color{darkblue}{2}$), so $I$ must have a smallest element. Let's call this smallest element $w$.

What is $w$ exactly? Is it red or blue? And what number is it? You can find out by following the proof that $T$ was well-ordered. If you did one yourself you should follow it now and see what you get. I'll follow mine:

Either $I$ must be all blue, or it has some red elements. Every red number $\color{darkred}{n}$ has only a finite section $\{\color{darkred}{0,1,2,3,\ldots, n-1}\}$, so $I$ is all blue. Blue $\color{darkblue}{0}$ does have an infinite section, because every red number is less than $\color{darkblue}{0}$. So $\color{darkblue}{0} \in I$. Since $I$ is all blue and $\color{darkblue}{0}$ is the smallest blue number, it must be the smallest element of $I$, and $w=\color{darkblue}{0}$.

$w$, the smallest element of $T$, is exactly the blue $\color{darkblue}{0}$.

Your question was:

how can a single element make the difference between the section of a set being countable or uncountable?

The structure of $T$ here is completely analogous, so ask yourself the analogous question:

how can a single element make the difference between the section of a set being finite or infinite?

Does this help at all?


You also asked:

Is there a clear example of such a set A?

And, uh, actually, there is not. The standard example of such a set would be a set called $\Omega$, the set of all countable ordinal numbers. (It's more often called $\omega_1$, but since Munkres is calling it $\Omega$ we'll use that.) $\Omega$ is uncountable and well-ordered by construction. It's quite easy to prove it has the required properties. But I don't think you can get much concrete intuition about it, because its construction is sort of like this:

Take all the infinite quantities anyone could possibly think of, and mash them together into something even bigger.

If you can somehow get your head around the whole mashup, well, that was just step one because the mashup itself is one of the things you were supposed to mash up. And if you can't, well, what you had wasn't $\Omega$ anyway.

So we reason about uncountable sets not by intuitive examples but from abstract properties (as Munkres is doing), and for intuition the best we can do is to make analogies where “finite” and “infinite” take on the roles of “countable” and “uncountable” as Noah suggested.

Related Question