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

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?

• As I recall, this is true but not trivial to prove. If no one answers, I will try to find a reference later today. Jan 18, 2021 at 13:31

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.

• Beaten by 10 seconds! Jan 18, 2021 at 13:36
• Trust me, you've beaten me by more than 10 seconds many times ... Jan 18, 2021 at 13:43
• Great, thanks! Glad to see that it is not completely trivial — at least for a non-expert...
– abx
Jan 18, 2021 at 13:58
• Those kind of unexpected applications of Ramsey's theorem are really beautiful! Jan 18, 2021 at 14:57
• It's also worth mentioning that, while some amount of choice is needed to prove that every ill-founded ordering has a descending sequence, this argument requires no choice since $A + B$ has an induced well-ordering from $A$ and $B,$ so this descending sequence can be canonically constructed. Jan 18, 2021 at 16:22

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.

• $G^+ := \{x \in G\;:\; x > 0\}$ Jan 18, 2021 at 16:12
• Is it easy to see that the theorem you cite implies what one needs? A priori it only says that $(A+m)\cup(B+m)\cup(A+A+2m)\cup(A+B+2m)\cup(B+B+2m)\cup(A+A+A+3m)\cup(A+A+B+3m)\cup(A+B+B+3m)\cup\cdots$ is well-ordered (where $m$ is something below $A\cup B$) Jan 18, 2021 at 18:27
• @მამუკაჯიბლაძე I’m not sure what you mean by $m$, but note that any subset of a well-ordered set is well-ordered. Jan 18, 2021 at 19:38
• (I think that "$m$ is something below $A \cup B$" means to mean that $m$ is the element by which we translate $A \cup B$ to ensure that it's positive. Perhaps it's also worth remarking that a translate of a well ordered set is well ordered, so from the well ordering of a set containing $A + B + 2m$ we can conclude, as @EmilJeřábek says, the well ordering of $A + B + 2m$, and thence that of $A + B$.) Jan 18, 2021 at 20:28
• Correct. If $A,B\subset G^+$, then $A+B \subseteq (A\cup B)^*$ and a subset of a well ordered set is well ordered. So (as LSpace said) in general, translate $A,B$ to get them inside $G^+$. Jan 18, 2021 at 21:21

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".

• Is your argument an elaboration of @ElliotGlazer's comment? Jan 18, 2021 at 17:12
• @LSpice Not really, I had not read this comment. Jan 18, 2021 at 18:58

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) to denote the $$i$$-th element of $$A$$. We have $$a_i whenever $$i. Similarly, we use $$b_i$$ ($$i) 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 and $$j) (ii) $$f$$ is a 1-1 function (iii) For all $$i,j \in \mathbb{N}$$ (with $$j>i$$) we must have $$f(j).

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)).

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)). 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:$$....... 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$$.

• It seems that instead of writing $\alpha_1=min\{\alpha \in Ord:first(f(x))=a_{\alpha} \wedge x \in \mathbb{N} \wedge x>n_0 \}$ it would probably be better to write something like: $\alpha_1=min\{\alpha \in Ord: \exists x \in \mathbb{N} (first(f(x))=a_{\alpha} \wedge x>n_0) \}$. Jan 19, 2021 at 17:49
• Is there a specific reason for the downvote? What is the specific issue (or a major mistake) in this answer? Jan 20, 2021 at 4:47
• Sorry for too much bumping, but I think I see the mistake made (and hence reason for downvote). The definition for first, second was too loose/incorrect. Jan 20, 2021 at 21:44
• I guess another alternative definition for $first(r)$ could go like: "Find the smallest value $\alpha<p$ such that $a_\alpha+y=r$ (where $y \in B$). Then $first(r)=a_\alpha$." Jan 20, 2021 at 22:37