On better-quasi-ordering transfinite sequences

Source abstract

Abstract Let Q be a quasi-ordered set, i.e. a set on which a reflexive and transitive relation ≤ is defined. If, for every finite sequence q 1 , q 2 , … of elements of Q , there exist i and j such that i < j and q i ≤ q j then we call Q well-quasi-ordered. For any ordinal number α the set of all ordinal numbers less than α is called an initial set. A function from an initial set into Q is called a transfinite sequence on Q . If ƒ: I 1 → Q , g : I 2 → Q are transfinite sequences on Q , the statement ƒ ≤ g means that there is a one-to-one order-preserving function ø: I 1 → I 2 such that f (α) ≤ g (ø(α)) for every α ∈ I 1 . Milner has conjectured in (3) that, if Q is well ordered, then any set of transfinite sequences on Q is well-quasi-ordered under the quasi-ordering just defined. In this paper, we define so-called ‘better-quasi-ordered sets’, which are well-quasi-ordered sets of a particularly ‘well-behaved’ kind, and we prove that any set of transfinite sequences on a better-quasi-ordered set is better-quasi-ordered. Milner's conjecture follows a fortiori , since every well ordered set is better-quasi-ordered and every better-quasi-ordered set is well-quasi-ordered.