Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Transactions of the American Mathematical Society
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 Free Access

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

DOI: http://dx.doi.org/10.1090/S0002-9947-1994-1219735-8
PII: S 0002-9947(1994)1219735-8
Keywords: Well-quasi-ordering, better-quasi-ordering, transfinite sequences, barrier, $ \Pi _2^1$-completeness
Article copyright: © Copyright 1994 American Mathematical Society