Return to Answer

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" (JCTA (1972), 297–305), so I went to see if he had anything to say about the equivalence you mention. He doesn't 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 in the Monthly in 1952 (pp. 255–257).

Kruskal's [29] is Rado's paper "Partial well-ordering of sets of vectors" (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" (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 that covers minors.

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" (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 in the Monthly in 1952 (pp. 255–257).

Kruskal's [29] is Rado's paper "Partial well-ordering of sets of vectors" (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" (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 that covers minors.

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" (JCTA, 1972, 297–305), so I went to see if he had anything to say about the equivalence you mention. He doesn't 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 in the Monthly in 1952 (pp. 255–257).

Kruskal's [29] is Rado's paper "Partial well-ordering of sets of vectors" (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" (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. 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 that covers minors.

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" (JCTA (1972), 297–305), so I went to see if he had anything to say about the equivalence you mention. He doesn't 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 in the Monthly in 1952 (pp. 255–257).

Kruskal's [29] is Rado's paper "Partial well-ordering of sets of vectors" (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" (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 that covers minors.

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

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" (JCTA, 1972, 297–305), so I went to see if he had anything to say about the equivalence you mention. He doesn't 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 in the Monthly in 1952 (pp. 255–257).

Kruskal's [29] is Rado's paper "Partial well-ordering of sets of vectors" (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" (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. 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 that covers minors.