11
$\begingroup$

Motivated by a problem in factorization theory, I've recently proved the following:

Theorem. If $X$ is a non-empty finite alphabet and $\mathcal W$ an infinite subset of the free semigroup, $X^\ast$, over $X$, then there exists a sequence $(w_n)_{n \ge 1}$ with values in $\mathcal W$ such that $w_n$ is a proper subword of $w_{n+1}$ for every $n \in \mathbf N^+$.

The theorem implies at once Higman's lemma. The proof is elementary and self-contained (the most advanced thing one is using, is the pigeonhole principle), but I wouldn't call it trivial: The basic idea is to introduce a non-standard factorization of the elements of $X^\ast$ that is well suited to an induction on $|X|$, and then distinguish two cases depending on a certain invariant associated with this factorization.

Unfortunately, it turned out that the result is nothing new and comes down to a special case of Theorems 2.1 and 4.3 of G. Higman's paper Ordering by divisibility in abstract algebras [Proc. Lond. Math. Soc., III. Ser. 2 (1952), 326-336]. In particular, Theorem 2.1 in Higman's paper states that the following conditions are equivalent for a quasi-ordered set $(A, \preceq)$:

(a) Every sequence of elements of $A$ has a subsequence that is strictly increasing wrt $\preceq$.

(b) If $(a_n)_{n \ge 1}$ is a sequence of elements of $A$, there exist $i,j \in \mathbf N^+$ such that $i < j$ and $a_i \preceq a_j$.

For the proof of the equivalence, Higman cites an unpublished manuscript of P. Erdős and R. Rado.

Question. Which manuscript of Erdős and Rado does Higman refer to? Has the manuscript been eventually published? If not, is there a book, article, etc. with the details of a proof of the equivalence between (a) and (b)?

I browsed through the joint papers of Erdős and Rado listed at https://www.renyi.hu/~p_erdos/Erdos.html, but I couldn't find what I'm looking for.

$\endgroup$
  • $\begingroup$ Unless I've misunderstood something, this theorem of Higman is an immediate consequence of Ramsey's theorem (which might have been rediscovered by Erdös and Rado). $\endgroup$ – Andreas Blass Aug 25 at 19:34
  • 1
    $\begingroup$ @AndreasBlass Do you mean the infinite Ramsey thm (en.wikipedia.org/wiki/Ramsey's_theorem)? If so, could you explain in some detail how to use it to prove the equivalence between (a) and (b), if this is what you mean by "this thm of Higman"? $\endgroup$ – Salvo Tringali Aug 25 at 20:17
  • $\begingroup$ Yes, I mean the infinite Ramsey theorem. I've put the proof into an answer, since it's too long for a comment. $\endgroup$ – Andreas Blass Aug 25 at 22:00
  • $\begingroup$ It follows immediately from Dilworth theorem: every infinite poset contains either an infinite chain or an infinite antichain. This is an easy (high school level) statement. $\endgroup$ – Mark Sapir Aug 26 at 1:59
  • $\begingroup$ @MarkSapir I join bof in their request. I guess you refer to the extension of Dilworth's thm to infinite posets (en.wikipedia.org/wiki/…), don't you? $\endgroup$ – Salvo Tringali Aug 26 at 6:51
10
$\begingroup$

I didn't have much time when I wrote my initial answer, so here's an update.

It occurred to me that I ought to recommend Kruskal's classic paper "The theory of well-quasi-ordering: a frequently discovered concept" (JCTA (1972), 297–305), so I went to see if he had anything to say about the equivalence of (a) and (b). He doesn't seem to have anything to say about that, but he does have something to say about the reference you mention. On page 300, Kruskal writes that

Incidentally, Higman refers to an unpublished manuscript of Erdős and Rado which was probably an early version of [29] or of [4].

Kruskal's [4] is Erdős and Rado's solution to problem 4358 in the Monthly in 1952 (pp. 255–257).

Kruskal's [29] is Rado's paper "Partial well-ordering of sets of vectors" (Mathematika (1954), 89–95).

Another paper that Higman might have been referring to is Erdős and Rado's 1959 paper "A theorem on partial well-ordering of sets of vectors" (J. London Math. Soc. (1959), 222–224).

Anyway, that's only the first part of your question. The second part asks where to find the proof. Perspectives have changed since Higman, and condition (b) of your question is now often taken as the definition of a well-quasi-order (every infinite sequence has a good pair). To derive (a) from this definition, one typically appeals to Ramsey's theorem as Andreas Blass has done in his answer here. You can also find this proof in almost any text which includes an introduction to well-quasi-order. To mention one proof that is particularly succinct, you might look at the chapter of Diestel's Graph Theory that covers minors.

$\endgroup$
  • $\begingroup$ Thanks. Erdos and Rado's 1959 paper is freely available at renyi.hu/~p_erdos/1959-02.pdf, but I'm having some difficulty in understanding its relevance to the OP: In the paper, 𝑊𝑆(<𝜔) is the free monoid over 𝑆 (is it?), and assuming that (𝑆,≤) is a partial order, Erdős and Rado refer back to Higman's 1952 paper for a proof that, if 𝑆 is partially well-ordered wrt ≤, then so is 𝑊𝑆(<𝜔) wrt the "subword order" induced from ≤ (as defined in the 2nd paragraph of p. 222). But then Erdős and Rado move on to (settle a conjecture of Rado and) prove a generalization of [...] $\endgroup$ – Salvo Tringali Aug 25 at 17:38
  • $\begingroup$ [...] of Higman's result, where finite words are replaced with words of "length" smaller than $\omega^\omega$ which have only a finite number of distinct letters (Erdős and Rado use the term "vector" for "word" and "component" for "letter"); incidentally, they mention that the same result was also obtained by J. Kruskal in an unpublished manuscript. Am I missing anything? $\endgroup$ – Salvo Tringali Aug 25 at 17:44
  • $\begingroup$ As for Erdős and Rado's solution of Problem 4358 in the AMM, there is a note on partially-well-ordered posets on pp. 256-257: In particular, the note credits Higman and B.H. Neumann for having found, independently of each other, a proof that all words over a partially-well-ordered alphabet $S$, is partially well ordered wrt the "subword order" induced from $S$ (this is Thm 4.3 in Higman's paper). But, again, there is no reference to the equivalence of conditions (a) and (b) from the OP. $\endgroup$ – Salvo Tringali Aug 25 at 20:39
7
$\begingroup$

This is an answer not for the original question but for how to get the equivalence of (a) and (b) from the infinite Ramsey theorem (as requested in a comment). The implication from (a) to (b) is trivial. For the converse, I'm going to assume that "sequence" means one-to-one sequence (i.e., no repetitions), because otherwise a one-element set $A$ is a counterexample (because of the "strictly" in (a) and the non-strict $\preceq$ in (b)).

So assume (b) and let $(a_i)_{i\in\mathbb N}$ be a sequence of distinct elements of $A$. Partition the set $[\mathbb N]^2$ of $2$-element subsets $\{i<j\}$ of $\mathbb N$ into two parts by putting $\{i<j\}$ into the first part if $a_i\prec a_j$ and into the second part otherwise. By Ramsey's theorem, there is an infinite subset $H$ of $\mathbb N$ all of whose $2$-element subsets are in the same part.

If they're all in the first part, that means that, for all $i<j$ in $H$, we have $a_i\prec a_j$. In other words, the subsequence $(a_i)_{i\in H}$ of our original sequence is increasing with respect to $\prec$, as required for (a).

If they're all in the second part, that means that, for all $i<j$ in $H$, we have $a_i\not\prec a_j$. But then the sequence $(a_i)_{i\in H}$ violates our assumption (b).

(The last step is where I need that the sequence is one-to-one, because I need $a_i\not\preceq a_j$ in order to violate (b). If one allows sequences that are not one-to-one, then the best I can do is to partition $[\mathbb N]^2$ into three parts, according to whether $a_i\prec a_j$, $a_i=a_j$ or $a_i\not\preceq a_j$. If $H$ is an infinite homogeneous set as given by Ramsey's theorem, then the result is that $(a_i)_{i\in H}$ either is increasing as required for (a), or is constant, or violates (b). So what can go wrong in the not one-to-one case is essentially just the possibility of a constant sequence, as I indicated above in my remark about a one-element set $A$.)

$\endgroup$
  • $\begingroup$ @SalvoTringali OK. Now that "strictly" is gone, my argument works even when sequences are allowed to have repetitions. But I think I'll leave my answer as it is, since the last paragraph (in parentheses) might be useful for some readers. $\endgroup$ – Andreas Blass Aug 25 at 22:24
  • $\begingroup$ I see, many thanks for the details. The "strictly" in (a) is a mistake from my side, I'll edit the OP to fix it: Higman in his paper writes of "an infinite ascending subsequence." Edit. You posted your comment while I was editing mine (and I had to delete mine, since the edit came too late). $\endgroup$ – Salvo Tringali Aug 25 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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