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. Consider an uncountable well ordered set $B$, consider $C=\{1,2\}\times B$ with the lexicographic order and let $\Omega $ be the smallest element of $C$ for which $S_\Omega=\{x\in C| x<\Omega\}$ is uncountable. Let $A=S_\Omega\cup\{\Omega\}$ .

I'm trying to show that if $X_0$ is a subset of $S_\Omega$ of all elements that have no immediate predecessors, then $X_0$ is uncountable.

Assume the converse: $X_0$ is countable. Any countable subset of $S_\Omega$ has an upper bound in $S_\Omega$. Let $\Gamma \in S_\Omega$ be this bound: $x\le \Gamma$ for all $x\in X_0$. Now $S_\Omega$ has no largest element, so every element in $S_\Omega$ has an immediate successors. I believe I have to apply this to elements of $X_0$ and find connection with immediate predecessors. So for every $x$ in $X_0$, there is an immediate successor $s(x)\in X_0$. But how to establish connection between immediate predecessors and get a contradiction?

  • $\begingroup$ A countable union of countable sets is countable. $\endgroup$ – Carl Mummert Aug 27 '18 at 0:59
  • $\begingroup$ @Carl Mummert I'm not sure to which sets I should apply this. I don't see a countable collection of countable sets. $\endgroup$ – user531587 Aug 27 '18 at 1:07
  • 1
    $\begingroup$ Try to prove that if $b$ is any element of the ordering then (since there is no maximal element) $b$ is followed by a sequence $b_1, b_2, \ldots$ of elements that all have immediate predecessors, and the limit $c$ of that sequence, if there is one in the ordering, will not have an immediate predecessor. So each element with no immediate predecessor determines a countable subset ordered like the natural numbers, and the ordering overall is the union of these subsets. One thing that you learn from these problems in Munkres is a little bit of intuition about the structure of well ordered sets. $\endgroup$ – Carl Mummert Aug 27 '18 at 1:16

If you're allowed to use the fact that any countable set is bounded in $S_\Omega$ (which is true, but not quite trivial from what you've mentioned so far unless I'm missing something), then you're on the right track with letting $\Gamma$ be an upper bound for $X_0.$

What you want to look at then is the set $Z=\{x\in S_\Omega : x \ge \Gamma\}.$ In this set, by definition, every element except possibly $\Gamma$ has an immediate predecessor. And it's easy to see that for every element of $Z$ except $\Gamma,$ the element's immediate predecessor is in $Z.$ So $Z$ is a well-ordered set with least element $\Gamma$ such that every other element has an immediate predecessor. This means $Z$ is order isomorphic to the natural numbers with their usual ordering, and hence is countable, which gives the required contradiction.

To see that it is isomorphic to the natural numbers, take any $z_0\in Z$ (other than $\Gamma$). Then let $z_1$ be the immediate predecessor of $z_0,$ and $z_2$ the predecessor of $z_1$ if $z_1\ne \Gamma,$ and so on. This sequence must hit $\Gamma$ at some point, because otherwise the sequence would give a set with no least element. Thus every element of $Z$ is the $n$-th successor of $\Gamma$ for some $n.$

Alternatively, you can prove that $X_0$ is unbounded (and hence uncountable) directly, as Carl suggested in the comments. Let $a\in S_\Omega.$ Well ordering implies every element has an immediate successor, so define recursively $a_0=a,$ $a_{n+1}=s(a_n),$ and $A=\{a_n :n\in \mathbb N\}$

You know that the initial segment $S_a$ of elements $< a$ is countable, and that that $A$ is countable. You can also show that $S_a\cup A$ contains the initial segment of each of its elements and the successor of each of its elements.

$S_a\cup A$ is countable, hence not all of $S_\Omega,$ so there is a least element $b\in S_\Omega$ larger than all of its members. In fact, we have $S_a\cup A=S_b.$ We can see that $b$ does not have an immediate predecessor since any element $c<b$ is in $S_a\cup A,$ so $s(c)\in S_a\cup A$ so is not equal to $b.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.