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](https://en.wikipedia.org/wiki/Higman%27s_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.



Higman's lemma and a manuscript of Erdős and Rado
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](https://doi.org/10.1016/0097-3165(72)90063-5)" (*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](https://doi.org/10.2307/2306526) in the *Monthly* in 1952 (pp. 255–257).


Kruskal's [29] is Rado's paper "[Partial well-ordering of sets of vectors](https://doi.org/10.1112/S0025579300000565)" (*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](http://jlms.oxfordjournals.org/cgi/reprint/s1-34/2/222)" (*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](http://diestel-graph-theory.com/) that covers minors.


