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
DOI: https://doi.org/10.1090/S0002-9947-1994-1219735-8
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?)

  • [1] M. Assous, Caractérisation du type d'ordre des barrières de Nash-Williams, Publ. Dep. Math. Nouvell Sér. 11 (1974), 89-106. MR 0366758 (51:3004)
  • [2] P. Clote, A recursion theoretic analysis of the clopen Ramsey theorem, J. Symbolic Logic 49 (1984), 376-400. MR 745367 (86b:03048)
  • [3] -, The metamathematics of Fraïssé's order type conjecture, Recursion Theory Week (K. Ambos-Spies, G. H. Müller, and G. E. Sacks, eds.), Lecture Notes in Math., vol. 1432, Springer-Verlag,, Berlin and New York, 1990, pp. 41-56.
  • [4] R. Fraïssé, Theory of relations, North-Holland, Amsterdam, 1986. MR 832435 (87f:03139)
  • [5] J. B. Kruskal, The theory of well-quasi-ordering: a frequently discovered concept, J. Combin. Theory Ser. A 13 (1972), 297-305. MR 0306057 (46:5184)
  • [6] R. Laver, On Fraïssé's order type conjecture, Ann. of Math. (2) 93 (1971), 89-111. MR 0279005 (43:4731)
  • [7] A. Louveau and J. Saint-Raymond, On the quasi-ordering of Borel linear orders under embeddability, J. Symbolic Logic 55 (1990), 537-560. MR 1056369 (91h:03067)
  • [8] R. Mansfield and G. Weitkamp, Recursive aspects of descriptive set theory, Oxford Univ. Press, New York, 1985. MR 786122 (86g:03003)
  • [9] A. Marcone, Foundations of bqo theory and subsystems of second order arithmetic, Ph.D. thesis, The Pennsylvania State Univ., 1993. MR 1219735 (95a:06003)
  • [10] E. C. Milner, Basic wqo- and bqo-theory, Graphs and Orders (I. Rival, ed.), Reidel, Boston, Mass., 1985, pp. 487-502. MR 818505 (87h:04004)
  • [11] Y. N. Moschovakis, Descriptive set theory, North-Holland, Amsterdam, 1980. MR 561709 (82e:03002)
  • [12] C. St. J. A. Nash-Williams, On well-quasi-ordering tranfinite sequences, Proc. Cambridge Philos. Soc. 61 (1965), 33-39. MR 0173640 (30:3850)
  • [13] -, On well-quasi-ordering infinite trees, Proc. Cambridge Philos. Soc. 61 (1965), 697-720. MR 0175814 (31:90)
  • [14] -, On better-quasi-ordering transfinite sequences, Proc. Camb. Philos. Soc. 64 (1968), 273-290. MR 0221949 (36:5001)
  • [15] M. Pouzet, Sur les prémeilleurordres, Ann. Inst. Fourier (Grenoble) 22 (1972), 1-20. MR 0342446 (49:7192)
  • [16] -, Applications of well quasi-ordering and better quasi-ordering, Graphs and Orders (I. Rival, ed.), Reidel, Boston, Mass., 1985, pp. 503-519. MR 818506 (87g:06014)
  • [17] -, Graphs and posets with no infinite independent set, Finite and Infinite Combinatorics in Sets and Logic, (N. W. Sauer et al., eds.), Kluwer, 1993, pp. 313-335. MR 1261214 (94k:05208)
  • [18] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 0224462 (37:61)
  • [19] J. G. Rosenstein, Linear orderings, Academic Press, New York, 1982. MR 662564 (84m:06001)
  • [20] S. Shelah, Better quasi-orders for uncountable cardinals, Israel J. Math. 42 (1982), 177-226. MR 687127 (85b:03085)
  • [21] R. A. Shore, On the strength of Fraïssé's conjecture, Logical Methods: In Honor of Anil Nerode's 60th Birthday (J. N. Crossley, J. B. Remmel, M. E. Sweedler, R. A. Shore, eds.), Birkhäuser, Cambridge, Mass., 1993, pp. 782-813. MR 1281145 (95a:03002)
  • [22] S. G. Simpson, Bqo-theory and Fraïssé's conjecture, [8], pp. 124-138.
  • [23] -, Subsystems of $ {Z_2}$ and reverse mathematics, appendix to G. Takeuti, Proof Theory, 2nd ed., North-Holland, Amsterdam, 1986.

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: https://doi.org/10.1090/S0002-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

American Mathematical Society