Foundations of BQO theory

Marcone, Alberto

doi:10.1090/S0002-9947-1994-1219735-8

Foundations of BQO theory
HTML articles powered by AMS MathViewer

by Alberto Marcone PDF

Trans. Amer. Math. Soc. 345 (1994), 641-660 Request permission

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

Marc Assous, Caractérisation du type d’ordre des barrières de Nash-Williams, Publ. Dép. Math. (Lyon) 11 (1974), no. 4, 89–106 (French). MR 366758
Peter Clote, A recursion theoretic analysis of the clopen Ramsey theory, J. Symbolic Logic 49 (1984), no. 2, 376–400. MR 745367, DOI 10.2307/2274171

The metamathematics of Fraïssé’s order type conjecture

R. Fraïssé, Theory of relations, Studies in Logic and the Foundations of Mathematics, vol. 118, North-Holland Publishing Co., Amsterdam, 1986. Translated from the French. MR 832435
Joseph B. Kruskal, The theory of well-quasi-ordering: A frequently discovered concept, J. Combinatorial Theory Ser. A 13 (1972), 297–305. MR 306057, DOI 10.1016/0097-3165(72)90063-5
Richard Laver, On Fraïssé’s order type conjecture, Ann. of Math. (2) 93 (1971), 89–111. MR 279005, DOI 10.2307/1970754
Alain Louveau and Jean Saint-Raymond, On the quasi-ordering of Borel linear orders under embeddability, J. Symbolic Logic 55 (1990), no. 2, 537–560. MR 1056369, DOI 10.2307/2274645
Richard Mansfield and Galen Weitkamp, Recursive aspects of descriptive set theory, Oxford Logic Guides, vol. 11, The Clarendon Press, Oxford University Press, New York, 1985. With a chapter by Stephen Simpson. MR 786122
Alberto Marcone, Foundations of BQO theory, Trans. Amer. Math. Soc. 345 (1994), no. 2, 641–660. MR 1219735, DOI 10.1090/S0002-9947-1994-1219735-8
E. C. Milner, Basic wqo- and bqo-theory, Graphs and order (Banff, Alta., 1984) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 147, Reidel, Dordrecht, 1985, pp. 487–502. MR 818505
Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR 561709
C. St. J. A. Nash-Williams, On well-quasi-ordering transfinite sequences, Proc. Cambridge Philos. Soc. 61 (1965), 33–39. MR 173640, DOI 10.1017/s0305004100038603
C. St. J. A. Nash-Williams, On well-quasi-ordering infinite trees, Proc. Cambridge Philos. Soc. 61 (1965), 697–720. MR 175814, DOI 10.1017/s0305004100039062
C. St. J. A. Nash-Williams, On better-quasi-ordering transfinite sequences, Proc. Cambridge Philos. Soc. 64 (1968), 273–290. MR 221949, DOI 10.1017/s030500410004281x
Maurice Pouzet, Sur les prémeilleurordres, Ann. Inst. Fourier (Grenoble) 22 (1972), no. 2, 1–19 (French, with English summary). MR 342446
M. Pouzet, Applications of well quasi-ordering and better quasi-ordering, Graphs and order (Banff, Alta., 1984) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 147, Reidel, Dordrecht, 1985, pp. 503–519. MR 818506
Maurice Pouzet, Graphs and posets with no infinite independent set, Finite and infinite combinatorics in sets and logic (Banff, AB, 1991) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 411, Kluwer Acad. Publ., Dordrecht, 1993, pp. 313–335. MR 1261214
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662564
Saharon Shelah, Better quasi-orders for uncountable cardinals, Israel J. Math. 42 (1982), no. 3, 177–226. MR 687127, DOI 10.1007/BF02802723
John N. Crossley, Jeffrey B. Remmel, Richard A. Shore, and Moss E. Sweedler (eds.), Logical methods, Progress in Computer Science and Applied Logic, vol. 12, Birkhäuser Boston, Inc., Boston, MA, 1993. Papers from the conference in honor of Anil Nerode’s sixtieth birthday held at Cornell University, Ithaca, New York, June 1–3, 1992. MR 1281145, DOI 10.1007/978-1-4612-0325-4

Bqo-theory and Fraïssé’s conjecture

Subsystems of

and reverse mathematics