Foundations of BQO Theory

Abstract

In this paper we study the notion of better-quasi-ordering (bqo) originally defined by Nash-WUliams [14].In particular we consider the approximation to this concept given by the notion of a -wqo, for a a countable indecomposable ordinal [15].We prove that if a quasi-ordering Q is a -wqo then Q<a is wqo, thereby obtaining a new proof of Nash-Williams' theorem that Q bqo implies Q (the set of all countable transfinite sequences of elements of Q) bqo.We show that for a < a', a' -wqo is properly stronger than a -wqo.We also show that the definition of a -wqo (and therefore also of bqo) can be modified by considering only barriers with a nice additional property.In the last part of the paper we establish a conjecture of Clote [3] by proving that the set of indices for recursive bqos is complete n^.