Well-Quasi-Orders on Finite Trees and Transfinite Sequences

We study the well-quasi-order (wqo) consisting of the set of finite trees with leaf labels coming from an arbitrary wqo Q , ordered by tree homomorphisms which respect the order on the labels. This is a variant of the usual Kruskal tree ordering without infima preservation. We calculate the precise maximal order types of this class of wqos as a function of the maximal order type of the labels Q . In the process, we sharpen some recent results of Friedman and Weiermann [7]. Furthermore, we show a correspondence with indecomposable transfinite sequences with finite range, over elements of the wqo Q , of length less than ω ω ω ^ω omega Superscript omega . Nash-Williams proved that arbitrary transfinite sequences with finite range are also well-quasi-ordered [17], but there are no known methods to extract bounds on the maximal order type from the proof. More concrete proofs for sequences of length less than α α alpha for some α < ω ω α < ω ^ω alpha less than omega Superscript omega were given by Erdös and Rado [5]. Using the correspondence, we obtain precise bounds for the entire collection of transfinite sequences with finite range of length less than ω ω ω ^ω omega Superscript omega .