# Set of ordinals less than the first uncountable ordinal and countability

I am trying to solve the following question from Royden's Real Analysis (3rd edition, Chap. 1, Problem 32).

Let $Y$ be the set of ordinals less than the first uncountable ordinal, i.e., $Y= \{ x\in X: x<\Omega \}$. Show that every countable subset $E$ of $Y$ has an upper-bound in $Y$ and hence a least upper-bound.

I have the following question: If $Y$ is assumed to be the set of ordinals less than the first uncountable ordinal, then shouldn't $Y$ be countable by definition? and so, every subset of a countable set is countable? and then, $\Omega$ is an upper-bound to each $E \subset Y$?

• No, because $\Omega$ is the set of all countable ordinals. – AJY Nov 11 '16 at 13:45
• To illustrate that there is no contradiction in $Y = \Omega$ being uncountable, note that $\omega_0$, the least infinite ordinal, is infinite while its elements are finite. – nombre Nov 11 '16 at 14:54

Each member of $Y$ (or, equivalently, each order type shorter than $Y)$ is countable, but $Y$ itself is the shortest possible uncountable well-ordering.  Added later in response to discussion in the comments: It's worth noting that this problem requires some use of the axiom of choice. Here's one approach: $S=\bigcup_{e\in E} \{x \mid x\lt e\}$ is a countable union of countable sets, so is countable (this uses AC). Since $\Omega$ is uncountable, there exists $b\in\Omega\setminus S;$ any such $b$ must be an upper bound for $E.$
It's consistent with ZF (without AC) that $\aleph_1$ is cofinal with $\omega,$ in which case the statement of Royden's problem is false.
• @Teodorism I took a look at the edit history to see what the other question was (I apologize if that isn't the final version of what you intended to ask). But the solution you quoted seems to be missing something, since the map $y\mapsto x_y$ isn't necessarily 1-1. I'd prefer a more direct approach anyway, and I've added an outline of such an approach to my answer. – Mitchell Spector Nov 12 '16 at 18:18
You're making an unfounded generalization from the part to the whole. In the set $\{\{0\}, \{1\}\}$, every element has cardinality $1$; but the set as a whole has cardinality $2$. Likewise, the fact that every member of $Y$ is countable says nothing whatsoever about the cardinality of $Y$ - to take an extreme example, the "set" of all singletons (sets of cardinality exactly $1$) is so large that it isn't even a set (it's a proper class).
It's certainly the case that every subset of a countable set is countable. But your final step doesn't work either - if $E \subseteq Y$ is countable, it's true that $\Omega$ is an upper bound on $E$, but it isn't an upper bound in $Y$. $Y$ is the set of countable ordinals; $\Omega$ is by definition not a countable ordinal, and so is not in $Y$.