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."
Best Answer
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.)