On well-quasi-ordering infinite trees

Abstract

Let A be the set of all ascending finite sequences (with at least one term) of positive integers. Let s, t ∈ A. Write s ⊲ t if there exist m, n, x1, …, xn such that m < n and x1 < … < xn and s is x1, …, xm and t is x2, x3, …, xn. Call a subset S of A a P-block if, for every infinite ascending sequence x1, x2, … of positive integers, there exists an m such that x1, …, xm belongs to S. A quasi-ordered set Q (i.e. a set on which a reflexive and transitive relation ≤ is defined) is better-quasi-ordered if, for every P-block S and every function f:S → Q, there exist s, t ∈ S such that s ⊲ t and f(s) ≤ f(t). It is proved that any set of (finite or infinite) trees is better-quasi-ordered if T1 ≤ T2 means that the tree T1 is homeomorphic to a subtree of the tree T2. This establishes a conjecture of J. B.Kruskal that, if T1, T2, … is an infinite sequence of trees, then there exist i, j such that i < j and Ti ≤ Tj.