From: Fred Galvin Subject: Re: Kruskal-tree-like theorem Date: Tue, 12 Oct 1999 14:38:20 -0500 Newsgroups: sci.math,sci.logic Keywords: better-quasi-ordering transfinite sequences On 12 Oct 1999 nospam@nospam.mit.edu wrote: > Diane Maclagan has recently proved a result that she feels might be known, > and is trying to ask as many experts as possible if they have seen it. > > Let N^d be the set of points in d dimensions whose coordinates are all > positive integers. Define a partial order on N^d by setting > > (a_1, a_2, ..., a_d) <= (b_1, b_2, ..., b_d) > > if a_i <= b_i for all i. A "finite order ideal" of N^d is a finite > subset S of N^d with the property that if P is in S and P' <= P then > P' must also be in S. Let J(N^d) be the set of all finite order ideals > of N^d, partially ordered by set inclusion. > > Theorem. J(N^d) has no infinite antichains. > > "Antichain" just means no two elements are comparable (as opposed to > "compatible," the concept that is more commonly used in forcing). > Has anyone seen this before? Is it a special case of a more general > theorem? For more information, see Maclagan's preprint at > > http://front.math.ucdavis.edu/math.CO/9909168 Yes and yes. There is a vast literature on this subject. Do a literature search on keywords like "well-quasi-ordering", "well-partial-ordering", and "wqo". Look for articles by Higman, Kruskal, Nash-Williams, Laver, ... To put the stated result in context: N is well-ordered; a fortiori, N is wqo; if P is wqo then P^d is wqo (Higman); if P is wqo then J(P) is wqo (Nash-Williams); "P is wqo" implies "no infinite antichains in P"; much more is true (Nash-Williams, Laver). DISCLAIMER: This is all strictly IIRC; don't take my word for anything; the results and attributions could be all wrong. ============================================================================== From: Fred Galvin Subject: Re: Kruskal-tree-like theorem Date: Wed, 13 Oct 1999 04:14:03 -0500 Newsgroups: sci.math,sci.logic On Tue, 12 Oct 1999, Fred Galvin babbled: [previous article quoted, with one amendation: --djr] > To put the stated result in context: > N is well-ordered; a fortiori, N is wqo; > if P is wqo then P^d is wqo (Higman); > if P is wqo then J(P) is wqo (Nash-Williams); <-----------WRONG > "P is wqo" implies "no infinite antichains in P"; > much more is true (Nash-Williams, Laver). > > DISCLAIMER: This is all strictly IIRC; don't take my word for anything; > the results and attributions could be all wrong. Well, I was right about the disclaimer. I seem to be mixing up wqo (well-quasi-ordering) with bqo (better-quasi-ordering). I now believe that the statements above are correct if you change all the wqos to bqos, and that all the results are due to Nash-Williams, the inventor of bqo theory, but I don't know anything; get the straight dope from C. St. J. A. Nash-Williams, On better-quasi-ordering transfinite sequences, Proc. Cambridge Philos. Soc. 64 (1968), 273-290.