26
$\begingroup$

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?

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

4 Answers 4

45
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Beaten by 10 seconds! $\endgroup$
    – Wojowu
    Jan 18, 2021 at 13:36
  • 5
    $\begingroup$ Trust me, you've beaten me by more than 10 seconds many times ... $\endgroup$
    – Nik Weaver
    Jan 18, 2021 at 13:43
  • 1
    $\begingroup$ Great, thanks! Glad to see that it is not completely trivial — at least for a non-expert... $\endgroup$
    – abx
    Jan 18, 2021 at 13:58
  • 4
    $\begingroup$ Those kind of unexpected applications of Ramsey's theorem are really beautiful! $\endgroup$ Jan 18, 2021 at 14:57
  • 9
    $\begingroup$ 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. $\endgroup$ Jan 18, 2021 at 16:22
16
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ $G^+ := \{x \in G\;:\; x > 0\}$ $\endgroup$ Jan 18, 2021 at 16:12
  • 1
    $\begingroup$ 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$) $\endgroup$ Jan 18, 2021 at 18:27
  • 1
    $\begingroup$ @მამუკაჯიბლაძე I’m not sure what you mean by $m$, but note that any subset of a well-ordered set is well-ordered. $\endgroup$ Jan 18, 2021 at 19:38
  • 1
    $\begingroup$ (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$.) $\endgroup$
    – LSpice
    Jan 18, 2021 at 20:28
  • 1
    $\begingroup$ 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^+$. $\endgroup$ Jan 18, 2021 at 21:21
15
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Is your argument an elaboration of @ElliotGlazer's comment? $\endgroup$
    – LSpice
    Jan 18, 2021 at 17:12
  • 1
    $\begingroup$ @LSpice Not really, I had not read this comment. $\endgroup$
    – nombre
    Jan 18, 2021 at 18:58
-1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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) \}$. $\endgroup$
    – SSequence
    Jan 19, 2021 at 17:49
  • $\begingroup$ Is there a specific reason for the downvote? What is the specific issue (or a major mistake) in this answer? $\endgroup$
    – SSequence
    Jan 20, 2021 at 4:47
  • $\begingroup$ 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. $\endgroup$
    – SSequence
    Jan 20, 2021 at 21:44
  • $\begingroup$ 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$." $\endgroup$
    – SSequence
    Jan 20, 2021 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.