One of the most mind boggling results in my opinion is, with the axiom of choice/well-ordering principle, there exist such things as uncountable well-ordered sets $(A,\leq)$.

With this is mind, does there exist some well ordered set $(B,\leq)$ with some special element $b$ such that the set of all elements smaller than $b$ is uncountable, but for any element besides $b$, the set of all elements smaller is countable (by countable I include finite too).

More formally stated, how can one show the existence of a well ordered set $(B,\leq)$ such that there exists a $b\in B$ such that $\{a\in X\mid a\lt b\}$ is uncountable, but $\{a\in X\mid a\lt c\}$ is countable for all $c\neq b$?

It seems like this $b$ would have to "be at the very end of the order."

  • 5
    $\begingroup$ "with the axiom of choice/well-ordering principle, there exist such things as uncountable well-ordered sets". One does not need the axiom of choice to prove the existence of uncountable well-orders. In fact, given any well-ordered set, there is one of strictly larger cardinality. Even, given any collection of well-ordered sets, there is a well-order of size strictly larger than all the well-orders in the collection. $\endgroup$ – Andrés E. Caicedo Sep 6 '11 at 3:09
  • $\begingroup$ How do you show that without choice there exists a well ordering of strictly larger cardinality? I would want to take the union of all ordinals of a certain cardinality; however, I am not sure if the set of all ordinals of a certain cardinality is even a set without already having an ordinal of even larger cardinality $\endgroup$ – William Sep 6 '11 at 3:20
  • $\begingroup$ Thanks Andres Caicedo, I got mixed up thinking you need choice to show any set can be well ordered, which is not quite the situation here. $\endgroup$ – Gotye Sep 6 '11 at 3:32
  • $\begingroup$ Yes, exactly. One needs choice to show that there is a well-ordering of the same size as, say, the reals. But no choice is needed to simply show that there is an uncountable well-ordering. $\endgroup$ – Andrés E. Caicedo Sep 6 '11 at 5:02
  • $\begingroup$ @William, Goyte: math.stackexchange.com/questions/46833/… $\endgroup$ – Asaf Karagila Sep 6 '11 at 6:14

There is no need to use the axiom of choice here. Suppose $X$ is an infinite well-orderable set. We argue that there is a well-ordered set $(Y,<)$ with $Y$ of strictly larger cardinality than $X$.

For this, consider the set $A$ of all binary relations $R\subseteq X\times X$ such that $R$ is a well-ordering of a subset of $X$. Let's call $X_R$ this unique subset.

We introduce an equivalence relation on $A$ by setting that $R_1\sim R_2$ iff $(X_{R_1},R_1)$ and $(X_{R_2},R_2)$ are order isomorphic. Let $Y$ be the set of equivalence classes.

We can well-order $Y$ by saying that $[R_1]<[R_2]$ iff there is an order isomorphism from $(X_{R_1},R_1)$ to a proper initial segment of $(X_{R_2},R_2)$. One easily verifies that $<$ is well-defined. This means that if $R_1\sim R_3$ and $R_2\sim R_4$, then $(X_{R_1},R_1)$ is isomorphic to a proper initial segment of $(X_{R_2},R_2)$ iff $(X_{R_3},R_3)$ is isomorphic to a proper initial segment of $(X_{R_4},R_4)$. One also verifies easily that $<$ is a well-ordering.

Finally, $Y$ has size strictly larger than $X$. To see this, note first that $X$ injects naturally into $Y$, namely, given a well-ordering $\prec$ of $X$ and any two initial segments $X_1$ and $X_2$ of $X$ under $\prec$, with $X_1$ a proper initial segment of $X_2$, $[\prec\upharpoonright X_1]<[\prec\upharpoonright X_2]$. But each point of $X$ determines an initial segment of $X$.

Now, if there were an injection $f$ of $Y$ into $X$, then the range $Z$ of $f$ would be well-orderable in a way isomorphic to $(Y,<)$ by using $f$ to copy the well-ordering $<$ of $Y$: Simply set $f(a) R f(b)$ iff $a<b$ for any classes $a,b\in Y$. We then have a copy of $(Y,<)$ as a proper initial segment of $(Y,<)$ (again, looking at initial segments of $(Z,R)$), contradicting that $<$ is a well-ordering.

The above may seem complicated but it is simple: All it is saying is that a well-ordering is less than another if it is an initial segment, and this is a "well-ordering of well-orderings". (And we have to use equivalence classes because different well-orderings may actually be isomorphic.)

When $X$ is a countably infinite set, the resulting set $Y$ is well-ordered and uncountable, but any initial segment of $Y$ corresponds to a well-ordering of $X$, so it is countable. If you want a set $B$ as required, simply set $B=Y\cup\{*\}$ where $*$ is some point not in $Y$, ordered by simply making $*$ larger than all the elements of $Y$. Then $\{a\in B\mid a<*\}$ is uncountable, but $\{c\in B\mid c<d\}$ is countable for any $d\in Y$, i.e., for any $d\in B$ with $d\ne *$.

Once you are familiar with the construction of ordinals, the above can be streamlined a bit: Rather than using an equivalence class, we simply use the ordinal isomorphic to any representative of the class. The argument above gives us that the collection of countable ordinals is actually a set, and its union is an (in fact, the first) uncountable ordinal. As a matter of fact, there is not even the need to take a union. The set of countable ordinals is already an uncountable ordinal.

(The argument above shows that given any well-ordered set there is a larger well-ordered set. A similar argument gives that if we have a family of well-orders, we can paste them together to get a well-ordering larger than all the ones in the family.)

  • $\begingroup$ Ah, good to have you back! :-) $\endgroup$ – Asaf Karagila Sep 6 '11 at 6:14
  • $\begingroup$ Thanks Andres Caicedo, a great answer. $\endgroup$ – Gotye Sep 6 '11 at 21:56
  • $\begingroup$ Given that any relation gives a well-ordering when restricted to the empty set, and the empty set is a subset of every set, isn't $A$ simply the powerset of $X\times X$? Also, isn't $R_X$ non-unique for example for the empty relation (every one-element subset is well-ordered, but no larger subset is)? Also for $X=\{a,b,c,d\}$ and $R=\{(a,b),(c,d)\}$ it seems to me that both $\{a,b\}\subset X$ and $\{c,d\}\subset X$ should be candidates for $X_R$. $\endgroup$ – celtschk Jul 2 '16 at 9:26
  • $\begingroup$ @celtschk $R$ must be a well-ordering of all of ${\rm dom}(R)\cup{\rm ran}(R)$, which should be a subset of $X$, and is what we call $X_R$. $\endgroup$ – Andrés E. Caicedo Jul 2 '16 at 14:40

Let $\aleph_1$ be the first uncountable ordinal. It can be defined to be the smallest ordinal which is not in bijection with $\omega$. This set exists using the ZF axioms. The ordinal $\aleph_1 + 1 $ is defined as $\aleph_1 \cup \{\aleph_1\}$. Hence $\aleph_1 + 1$ is the desired set which contains an element particularly $\aleph_1$ such that $\{x \in \aleph_1 + 1 : x < \aleph_1\}$ is uncountable, but the initial segment determined by any other element is countable.

To elaborate on how to show $\aleph_1$ exists : With the axion of choice, let $Z$ be an uncountable ordinal. Let $A = \{x \in Z : x \text{ is in bijection with } \omega\}$, which can be written more formally in the language of sets, which exists by separation. $\aleph_1$ is then $\bigcup A$, which exists by the axiom of union.

  • 3
    $\begingroup$ @William: An issue of style: when considering ordinals, I believe it is more common to use $\omega_1$ rather than $\aleph_1$. I know they denote the same object in ZFC, but when one is trying to emphasize its ordinal nature rather than its cardinal nature, $\omega_1$ seems to be more common (just like we tend to use $\omega$ when we want to emphasize the order, and $\aleph_0$ when we are trying to emphasize the cardinality). $\endgroup$ – Arturo Magidin Sep 6 '11 at 4:11

Let $b$ be the first uncountable ordinal, and $B$ be the set of all ordinals up to and including $b$.


The best explanation I've seen of this for the layman has to be "The Pancake at the Bottom", by Scott Aaronson: http://www.scottaaronson.com/writings/pancake.html

  • $\begingroup$ This is not an answer. You merely reference to some link. This should be made into a comment. $\endgroup$ – Asaf Karagila Sep 6 '11 at 16:22
  • 1
    $\begingroup$ Given that the link in question explicitly contains the answer, I don't see that it's a problem. $\endgroup$ – Craig Sep 6 '11 at 17:30
  • $\begingroup$ That I don't see how this is your answer. I don't find it wrong to reference someone else's writing online. I just don't see how this is an answer and not a comment. $\endgroup$ – Asaf Karagila Sep 6 '11 at 18:17
  • $\begingroup$ @Asaf: I don't see the problem here. There are 10k+ users whose specialty is to post such answers... Moreover, it's a great link and it would likely get lost as a comment. $\endgroup$ – t.b. Sep 6 '11 at 18:31
  • 1
    $\begingroup$ @Asaf: I don't like it either. Nevertheless it does answer the question, like it or not :) $\endgroup$ – t.b. Sep 6 '11 at 18:48

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.