WELL-QUASI-ORDERS ON FINITE TREES AND TRANSFINITE SEQUENCES

Abstract

Abstract 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 ^\omega $ 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 $ alpha for some α < ω ω $\alpha < \omega ^\omega $ 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 ^\omega $ omega Superscript omega .