From: Fred Galvin <galvin@math.ukans.edu>
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 <galvin@math.ukans.edu>
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.