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][1]. 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.


  [1]: https://en.wikipedia.org/wiki/Higman%27s_lemma