The sum of two well-ordered subsets is well-ordered

Question

Apologies if the answer is trivial, this is far from my domain. In order to define the field of Hahn series, one needs the following fact: if $A,B$ are two well-ordered subsets of $\mathbb{R}$ (or any ordered group — with the induced order of course), the subset $A+B:=\{a+b\,|\,a\in A,b\in B\} $ is well-ordered. How does one see that?

Answer 1

Ramsey theory! Suppose $A + B$ is not well-ordered. Then there is a strictly decreasing sequence $a_1 + b_1 > a_2 + b_2 > \cdots$. Observe that for any $i < j$, either $a_i > a_j$ or $b_i > b_j$ (or both). Make a graph with vertex set $\mathbb{N}$ by putting an edge between $i$ and $j$ if $a_i > a_j$, for any $i < j$. By the countably infinite Ramsey theorem, there is either an infinite clique or an infinite anticlique, and hence either a strictly decreasing sequence in $A$ or a strictly decreasing sequence in $B$, contradiction.

Answer 2

A more general result:

Let $G$ be an abelian totally ordered group. Let $E \subseteq G^+$. Write $E^*$ for the semigroup generated by $E$. If $E$ is well-ordered, then $E^*$ is well-ordered.

The case here is $G = (\mathbb R, +, <)$ and $E$ is an appropriate translate of $A \cup B$.

Attributed to Graham Higman with a simplified proof by C. St. J. A. Nash-Williams (the "minimal bad sequence" argument).

Higman, Graham, Ordering by divisibility in abstract algebras, Proc. Lond. Math. Soc., III. Ser. 2, 326-336 (1952). ZBL0047.03402.

Nash-Williams, C. St. J. A., On well-quasi-ordering finite trees, Proc. Camb. Philos. Soc. 59, 833-835 (1963). ZBL0122.25001.

Answer 3

There's also a more elementary proof than the one given by Nik Weaver (although I also enjoy the use of the countably infinite Ramsey's theorem!). First prove that an ordered set is well-ordered if and only if every sequence in it has a non-decreasing subsequence. Then given a sequence $(u_n)_{n \in \mathbb{N}}$ in $A+B$, for each $n \in \mathbb{N}$, pick the least $a_n \in A$ such that there exists a $b_n \in B$, which is then unique, with $u_n=a_n+b_n$. Extract a non-decreasing subsequence from $a$, then from $b \circ \varphi$ where $\varphi: \mathbb{N} \rightarrow \mathbb{N}$ is the first "extraction map".

Answer 4

Let's suppose the well-order of $A$ and $B$ have order-types $p$ (assume limit for simplicity) and $q$ respectively. So we use the notation $a_i$ ($i<p$) to denote the $i$-th element of $A$. We have $a_i<a_j$ whenever $i<j<p$. Similarly, we use $b_i$ ($i<q$) to denote the $i$-th element of $B$.

Since $A+B$ is already linearly-ordered, we want to prove that $A+B$ has no infinite descent. In other words, we want to disprove the existence of a function $f:\mathbb{N} \rightarrow \mathbb{R}$ such that (i) For all $x$ in domain of $f$ we have $f(x)=a_i+b_j$ (for some $i<p$ and $j<q$) (ii) $f$ is a 1-1 function (iii) For all $i,j \in \mathbb{N}$ (with $j>i$) we must have $f(j)<f(i)$.

---

So if we have $f(i)=r \in A+B$, then we can write $first(r)=\min\{x\in A\,|\, \exists y \in B \, (x+y=r) \}$ and $second(r)=r-first(r)$. The specific definition of $first(r)$ is justified because $A$ is well-ordered. Now we can define $\alpha_0=\min\{\alpha \in p \,|\, \exists x \in \mathbb{N}(first(f(x))=a_\alpha)\}$. Let's denote $n_0 \in \mathbb{N}$ as the "last" value for which $first(f(n_0))=a_{\alpha_0}$.

Now we define $\alpha_1=\min\{\alpha \in p \,|\, \exists x \in \mathbb{N}(first(f(x))=a_\alpha \, \wedge \,x>n_0)\}$. Let's denote $n_1 \in \mathbb{N}$ as the "last" value for which $first(f(n_1))=a_{\alpha_1}$. Now because of $\alpha_1>\alpha_0$, we should get $a_{\alpha_1}>a_{\alpha_0}$ and hence $second(f(n_1))<second(f(n_0))$.

So it seems to me that when we define $\alpha_2=\min\{\alpha \in p \,|\, \exists x \in \mathbb{N}(first(f(x))=a_\alpha \, \wedge \,x>n_1)\}$ and $n_2$ as the "last" value for which $first(f(n_2))=a_{\alpha_2}$, then we should have similarly $second(f(n_2))<second(f(n_1))$. The last inequality is supposed to follow from $a_{\alpha_2}>a_{\alpha_1}$ (because $\alpha_2>\alpha_1$).

The previous paragraph seems to be suggestive of defining $\alpha_i$, $n_i$ generally for an arbitrary natural number $i$ and then creating an infinite descent for the second components:$......<second(f(n_3))<second(f(n_2))<second(f(n_1))<second(f(n_0))$. However, this descent goes against the assumption of $B$ being a well-ordered set.

---

Few clarification points:

(1) At some points comparison relation $<$ is used for real numbers and at some points it is used for ordinals.

(2) We can think of $first$ as a function $first:A+B \rightarrow A$. Similarly, we can think of $second$ as a function $second:A+B \rightarrow B$.

(3) If we have $first(f(i))=a_\alpha$ for some specific natural number $i$ and some specific ordinal $\alpha$, then there can't exist arbitrarily large natural numbers $j>i$ such that $first(f(j))=a_\alpha$.