Timeline for Higman's lemma and a manuscript of Erdős and Rado
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 26, 2019 at 15:29 | history | edited | Vince Vatter | CC BY-SA 4.0 |
added 11 characters in body
|
| Aug 26, 2019 at 15:13 | vote | accept | Salvo Tringali | ||
| Aug 26, 2019 at 13:39 | history | edited | Vince Vatter | CC BY-SA 4.0 |
added 49 characters in body
|
| Aug 26, 2019 at 11:54 | history | edited | Vince Vatter | CC BY-SA 4.0 |
Major expansion of answer
|
| Aug 25, 2019 at 20:39 | comment | added | Salvo Tringali | As for Erdős and Rado's solution of Problem 4358 in the AMM, there is a note on partially-well-ordered posets on pp. 256-257: In particular, the note credits Higman and B.H. Neumann for having found, independently of each other, a proof that all words over a partially-well-ordered alphabet $S$, is partially well ordered wrt the "subword order" induced from $S$ (this is Thm 4.3 in Higman's paper). But, again, there is no reference to the equivalence of conditions (a) and (b) from the OP. | |
| Aug 25, 2019 at 17:44 | comment | added | Salvo Tringali | [...] of Higman's result, where finite words are replaced with words of "length" smaller than $\omega^\omega$ which have only a finite number of distinct letters (Erdős and Rado use the term "vector" for "word" and "component" for "letter"); incidentally, they mention that the same result was also obtained by J. Kruskal in an unpublished manuscript. Am I missing anything? | |
| Aug 25, 2019 at 17:38 | comment | added | Salvo Tringali | Thanks. Erdos and Rado's 1959 paper is freely available at renyi.hu/~p_erdos/1959-02.pdf, but I'm having some difficulty in understanding its relevance to the OP: In the paper, 𝑊𝑆(<𝜔) is the free monoid over 𝑆 (is it?), and assuming that (𝑆,≤) is a partial order, Erdős and Rado refer back to Higman's 1952 paper for a proof that, if 𝑆 is partially well-ordered wrt ≤, then so is 𝑊𝑆(<𝜔) wrt the "subword order" induced from ≤ (as defined in the 2nd paragraph of p. 222). But then Erdős and Rado move on to (settle a conjecture of Rado and) prove a generalization of [...] | |
| Aug 25, 2019 at 17:04 | history | answered | Vince Vatter | CC BY-SA 4.0 |