# Supremum and ordinals

Question: Show that sup{$\xi \dotplus 1 : \xi \in A$} is the least ordinal that is greater than each element of $A$.

I tried to get a better feel for this by letting $A=3=${$0,1,2$}. Then I know that the least ordinal greater than each element of $3$ is $3$ itself. So, sup{$\xi \dotplus 1 : \xi \in 3$}=$\bigcup_{\xi \in 3}${$\xi \dotplus 1$}={$0 \dotplus 1$}$\cup${$1 \dotplus 1$}$\cup${$2 \dotplus 1$}$=${$1,2,3$}.

I take it that {$1,2,3$} and {$0,1,2$} are the same because there's an order-preserving isomorphism from one to the other.

Now I'm having trouble generalizing.

-
You have to show that the supremum is greater than every member of A (take a member of A - show from the definition that the supremum is greater). And also that if $\sigma$ is greater than every member of A, then it is at least as great as the supremum as defined. You need to look at your sets and work with "least upper bound" rather than "order type". It is quite common in these situations that it can help to consider limit ordinals separately. – Mark Bennet Jul 6 '11 at 21:34
@furs: $\bigcup_{\xi\in3}(\xi+1)$ is not $\{1,2,3\}$: it's $1\cup2\cup3 = \{0\}\cup\{0,1\}\cup\{0,1,2\} = \{0,1,2\} = 3$. – Brian M. Scott Jul 6 '11 at 21:41

Suppose $\alpha=\sup\{\xi+1\colon\xi\in A\}$ then $\alpha$ is bigger than all $\xi\in A$ for obvious reasons.

Suppose $\beta<\alpha$ is also greater than all $\xi\in A$. Since $\alpha$ is the supremum of $\xi+1$ we have that it is the least ordinal greater or equal than $\xi+1$ for $\xi\in A$; in particular we have that $\beta\le\xi_0+1\le\alpha$ for some $\xi_0\in A$.

Since $\beta<\alpha$ we have that if $\xi_0+1=\alpha$ then $\beta=\xi_0$, in contradiction to the fact $\beta$ was strictly greater than all $\xi\in A$, and if $\beta<\xi_0+1$ then $\beta=\xi_0$, once again in contradiction to the aforementioned fact.

-
The last paragraph is unnecessary: from $\xi_0 \le \beta$ you already get that $\beta$ is not strictly greater than all $\xi \in A$. (You already assumed that $\beta < \alpha$.) – Brian M. Scott Jul 6 '11 at 21:54
@Brian: I edited the answer to clarify this point completely. It might be unneeded, but I think it makes the point clearer, which is as important to the least. – Asaf Karagila Jul 6 '11 at 21:59

The sets $\{ 1, 2, 3 \}$ and $\{ 0, 1, 2 \}$ are different sets. They have different elements.

Back to the question. For any set $X$ of ordinals there is an ordinal that is greater than or equal to each and every ordinal in $X$. Since the ordinals are well-ordered there is a least ordinal that is greater than or equal to each and every ordinal in $X$. This ordinal is the supremum of $X$. If $X$ happens to have a largest element then that largest element is the supremum of $X$. (Compare this with the real numbers.)

For your problem there are two cases: either $A$ has a largest element or $A$ does not have a largest element.

Suppose the first case holds. Let $\xi^*$ be the largest element of $A$. The element $\xi^* + 1$ is larger than every element in $A$ and is the supremum of the elements of $\{ \xi + 1 \colon \xi \in A \}$. Any ordinal that is strictly smaller than $\xi^*$ will be no larger than at least one element of $A$, namely $\xi ^*$. In this case we have the desired result.

Suppose the second case holds. In this case $\sup A$ is the least ordinal greater than every ordinal in $A$. To see this choose $\xi_{0} \in A$. By our assumption that the second case holds there is a $\xi_{1} \in A$ satisfying $\xi_{0} < \xi_{1} \leq \sup A$. Since $\xi_{0}$ was an arbitrarily chosen element of $A$ we get $\sup A$ is the least ordinal greater than every element of $A$. Now we show that $\{ \xi + 1 \colon \xi \in A \} = \sup A$. Select $\xi_{0} \in A$. Not that $\xi_{0} < \xi_{0} + 1 \leq \xi_{1}$, where $\xi_{1}$ is some ordinal in $A$ that is greater than $\xi_{0}$. Since for every element $\alpha \in B = \{ \xi + 1 \colon \xi \in A \}$ there is another element of $A$ which is greater than $\alpha$ the supremum of $A$ is no smaller than the supremum of $B$. But then the two supremum are equal.

-

Let $\alpha = \sup \{\xi+1:\xi\in A\}$. For each $\eta \in A$, $\eta \in \eta+1 \subseteq \bigcup\limits_{\xi \in A}(\xi+1) = \sup \{\xi+1:\xi\in A\} = \alpha$, so $\eta < \alpha$. That is, $\alpha$ is greater than each member of $A$.

Now suppose that some ordinal $\beta < \alpha$. Then $\beta \in \alpha = \bigcup\limits_{\xi \in A}(\xi+1)$, so there must be some $\xi \in A$ such that $\beta \in \xi+1$. But then $\beta < \xi+1$, and hence $\beta \le \xi$. Thus, $\beta$ is not greater than every member of $A$.

Putting the pieces together, we see that $\alpha$ must be the least ordinal greater than all members of $A$.

-

You haven't formed the union correctly (you inadvertantly added another layer of braces). What you actually get in your example is $\cup\{1,2,3\}=1\cup 2\cup 3$, and this is just $3$ itself, since $1=\{0\}\subset\{0,1\}= 2\subset\{0,1,2\}= 3$.

In general, it is clear that the supremum of $\{\xi+1:\xi\in A\}$ is at least as large as $\xi+1$ for every $\xi\in A$, and so you just have to argue that nothing smaller will also be larger than each of these.

-