Ordinals and upper-bounds 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.
In the solution manual, the solution is as follows:
Let $Y = \{ x : x < \Omega\}$ and let $E$ be a countable subset of $Y.$ $Y$ is uncountable so $Y \backslash E$ is nonempty. If for every $y \in Y \backslash E$ there exists $x_y \in E$ such that $y < x_y$, then $y \rightarrow x_y$ defines a mapping from $Y \backslash E$ into the countable set $E$ so $Y \backslash E$ is countable. Contradiction. Thus there exists $y \in Y \backslash E$ such that $x < y$ for all $x \in E$, i.e., $E$ has an upper bound in $Y.$ Consider the set of upper bounds of $E$ in $Y.$ This is a nonempty subset of $Y$ so it has a least element, which is then a least upper bound of $E.$
My question is: What is the logic behind breaking $Y$ into $E$ and $Y \backslash E$ and checking whether there's an upper-bound of one set in its complement?
 A: As Bob1123 notes, the ‘proof’ is fallacious. The existence of a function from the set $Y\setminus E$ into the countable set $E$ by no means implies that $Y\setminus E$ is countable: that is the case only if the function is countable-to-one, meaning that each element of $E$ has a countable preimage under the function.
Here is a correct argument.
For each $y\in Y$ let $P_y=\{x\in X:x<y\}$; by hypothesis $P_y$ is countable. Let $A=\bigcup_{y\in E}P_y$; $A$ is the union of countably many countable sets, so $A$ is countable. $Y\setminus A$ is therefore non-empty and therefore has a smallest element, say $z$. Let $y\in E$, and suppose that $y>z$; then $z\in P_y\subseteq A$, which is impossible, so $y\le z$, and since $y$ was an arbitrary element of $E$, $z$ is an upper bound for $E$. That’s enough to establish that $E$ has a least upper bound, since we can use the well-ordering of $Y$ to pick the smallest member of the non-empty set of upper bounds for $E$.
With just a little extra work, however, we can show more: we can show that $z$ is the least upper bound of $E$. If $z\in E$, then certainly $E$ has no smaller upper bound, and $z$ is therefore the least upper bound for $E$, so suppose that $z\notin E$, and let $u<z$. Then $u\notin Y\setminus A$, so $u\in A$, and there is therefore a $y\in E$ such that $u\in P_y$. But then $u<y\in E$, so $u$ is not an upper bound for $E$, and $z$ is again the least upper bound for $E$.
A: This proof is actually incorrect. The problem is in the statement "$y \rightarrow x_y$ defines a mapping from $Y\setminus E$ into the countable set $E$ so $Y\setminus E$ is countable." You generally don't want to say a statement like this without showing that the mapping is injective, which it certainly may not be in this case. (For instance, what if we sent everything in $\omega$ to 0? This function's range is finite, but we certainly cannot conclude that its domain is then finite.) Also, we usually don't want to break a set into two parts to check if there's an upper bound of one in the other; it may be the case that neither has an upper bound in the other (take the even and odd natural numbers, for instance).
The way one should go about proving this is by taking the supremum of $E$. This ordinal is certainly an upper bound for $E$, and now all we must check is that this upper bound is still in $Y$. On the ordinals, taking a supremum is equivalent to taking a union; thus, the supremum of $E$ is a countable union of countable ordinals, which is then countable. Since the supremum is countable, it is in $Y$.
The reason this works is because $\omega_1$, the set you call $Y$, is regular; that is to say that all sequences in $\omega_1$ of length less than $\omega_1$ have an upper bound. This is the same as saying the smallest sequence in $\omega_1$ that is unbounded has length $\omega_1$. This concept easily generalizes to higher cardinals.
