Return to Question

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.

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.

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 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.

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.

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.

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 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.