Mdthbs

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.

I too have come upon that statement in Higman's paper and wondered which manuscript he is referring to. There are two "papers" of Erdős and Rado that I think it might be.

First, it could be a reference to what became their solution to problem 4358 in the Monthly in 1952.

Second, it could instead be their 1959 paper "A theorem on partial well-ordering of sets of vectors" (J. London Math. Soc. (1959), 222–224).

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)_{iinmathbb 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_iprec 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_iprec a_j$. In other words, the subsequence $(a_i)_{iin 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_inotprec a_j$. But then the sequence $(a_i)_{iin H}$ violates our assumption (b).

(The last step is where I need that the sequence is one-to-one, because I need $a_inotpreceq 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_iprec a_j$, $a_i=a_j$ or $a_inotpreceq a_j$. If $H$ is an infinite homogeneous set as given by Ramsey's theorem, then the result is that $(a_i)_{iin 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$.)