Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Foundations of BQO theory

Author: Alberto Marcone
Journal: Trans. Amer. Math. Soc. 345 (1994), 641-660
MSC: Primary 06A07; Secondary 04A20
MathSciNet review: 1219735
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we study the notion of better-quasi-ordering (bqo) originally defined by Nash-Williams [14]. In particular we consider the approximation to this concept given by the notion of $ \alpha $-wqo, for $ \alpha $ a countable indecomposable ordinal [15]. We prove that if a quasi-ordering Q is $ \alpha $-wqo then $ {Q^{ < \alpha }}$ is wqo, thereby obtaining a new proof of Nash-Williams' theorem that Q bqo implies $ \tilde Q$ (the set of all countable transfinite sequences of elements of Q) bqo. We show that for $ \alpha < \alpha \prime ,\alpha \prime $-wqo is properly stronger than $ \alpha $-wqo. We also show that the definition of $ \alpha $-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 $ \Pi _2^1$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 06A07, 04A20

Retrieve articles in all journals with MSC: 06A07, 04A20

Additional Information

Keywords: Well-quasi-ordering, better-quasi-ordering, transfinite sequences, barrier, $ \Pi _2^1$-completeness
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society