Skip to main content
1 of 4
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64

Higman's lemma and a manuscript of Erdős and Rado

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 monoid 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^+$.

Unfortunately, it turned out that the result is nothing new and comes down to a special case of Theorems 1.1 and 2.1 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 makes reference to an unpublished manuscript of P. Erdős and R. Rado. So my questions are:

Question. Do you know which manuscript of Erdős and Rado does Higman refer to? Has the manuscript been eventually published? If not, do you know of a book, article, etc. with 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.

Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64