×

zbMATH — the first resource for mathematics

Computability-theoretic and proof-theoretic aspects of partial and linear orderings. (English) Zbl 1044.03043
The authors examine the reverse mathematics and effective content of several variations of Szpilrajn’s Theorem [E. Szpilrajn, Fundam. Math. 16, 386–389 (1930; JFM 56.0843.02)]. A linear order type \(\tau\) is called extendible if every partial order containing no subchains of type \(\tau\) can be extended to a linear ordering containing no subchains of type \(\tau\). The main results of the paper are: (1) “\(\omega ^*\) is extendible” is provable in ACA\(_0\) and strictly stronger than WKL\(_0\); (2) “\(\eta\) is extendible” is provable in \(\Pi^1_1\)-CA\(_0\), but not in WKL\(_0\); and (3) “\(\zeta\) is extendible” is equivalent to ATR\(_0\). Here \(\omega^*\) is \(\omega\) with the reverse order, \(\eta\) is the order type of the rationals, and \(\zeta\) is the order type of the integers.
For a survey of linear extensions of partial orderings, see R. Bonnet and M. Pouzet’s paper “Linear extensions of ordered sets” [in: I. Rival (ed.), Ordered sets, Proc. NATO Adv. Study Inst., Banff/Can. 1981, 125–170 (1982; Zbl 0499.06002)]. For background on computability-theoretic aspects of linear orderings, see R. G. Downey’s paper “Computability theory and linear orderings” [in: Yu. L. Ershov et al. (eds.), Handbook of recursive mathematics. Vol. 2. Recursive algebra, analysis and combinatorics. Amsterdam: Elsevier. Stud. Logic Found. Math. 139, 823–976 (1998; Zbl 0941.03045)].

MSC:
03F35 Second- and higher-order arithmetic and fragments
03D45 Theory of numerations, effectively presented structures
03B30 Foundations of classical theories (including reverse mathematics)
06A05 Total orders
06A06 Partial orders, general
06A07 Combinatorics of partially ordered sets
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. Bonnet,Stratifications et extension des genres de chaînes dénombrables, Comptes Rendus de l’Académie des Sciences, Paris, Série A-B269 (1969), A880-A882. · Zbl 0206.28001
[2] R. Bonnet and M. Pouzet,Extension et stratification d’ensembles dispersés, Comptes Rendus de l’Académie des Sciences, Paris, Série A-B268 (1969), A1512-A1515. · Zbl 0188.04203
[3] R. Bonnet and M. Pouzet,Linear extensions of ordered sets, inOrdered Sets (I. Rival, ed.), Proceedings of a NATO Advanced Study Institute held in Banff, Alta., August 28–September 12, 1981, D. Reidel Publishing Co., Dordrecht-Boston, Mass., 1982, pp. 125–170.
[4] M. Dehn,Über unendliche diskontinuierliche Gruppen, Mathematische Annalen71 (1912), 116–144. · JFM 42.0508.03 · doi:10.1007/BF01456932
[5] R. G. Downey,Computability theory and linear orderings, inHandbook of Recursive Mathematics, Vol. 2, North-Holland, Amsterdam, 1998, pp. 823–976. · Zbl 0941.03045
[6] Yu. L. Ershov, S. S. Goncharov, A. Nerode and J. Remmel (eds.),Handbook of Recursive Mathematics, Vols. 1 and 2, North-Holland, Amsterdam, 1998. · Zbl 0930.03037
[7] H. Friedman,Some systems of second order arithmetic and their uses, inProceedings of the International Congress of Mathematicians, Vancouver, 1974, Canadian Mathematical Congress, Montreal, Que., 1975, pp. 235–242.
[8] H. Friedman, N. Robertson and P. Seymour,The metamathematics of the graph minor theorem, inLogic and Combinatorics (S. G. Simpson, ed.), American Mathematical Society, Providence, R.I., 1987, pp. 229–261. · Zbl 0635.03060
[9] H. Friedman, S. G. Simpson and R. L. Smith,Countable algebra and set existence axioms, Annals of Pure and Applied Logic25 (1983), 141–181. · Zbl 0575.03038 · doi:10.1016/0168-0072(83)90012-X
[10] A. Fröhlich and J. C. Shepherdson,Effective procedures in field theory, Transactions of the Royal Society of London, Series A248 (1956), 407–432. · Zbl 0070.03502
[11] C. G. Jockusch, Jr.,Ramsey’s theorem and recursion theory, Journal of Symbolic Logic37 (1972), 268–280. · Zbl 0262.02042 · doi:10.2307/2272972
[12] C. G. Jockusch, Jr. and R. I. Soare, \(\Pi\) 1 0 classes and degrees of theories, Transactions of the American Mathematical Society173 (1972), 33–56.
[13] P. Jullien,Contribution à l’étude des types d’ordre dispersés, Thèse, Marseille, 1969.
[14] G. Metakides and A. Nerode,Effective content of field theory, Annals of Mathematical Logic17 (1979), 289–320. · Zbl 0469.03028 · doi:10.1016/0003-4843(79)90011-1
[15] J. Paris and L. Harrington,A mathematical incompleteness in Peano arithmetic, inHandbook of Mathematical Logic (J. Barwise, ed.), North-Holland, Amsterdam, 1977, pp. 1133–1142.
[16] M. O. Rabin,Computable algebra, general theory and theory of computable fields, Transactions of the American Mathematical Society95 (1960), 341–360. · Zbl 0156.01201
[17] H. G. Rogers, Jr.,Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967. · Zbl 0183.01401
[18] J. G. Rosenstein,Linear Orderings, Academic Press, New York-London, 1982.
[19] J. G. Rosenstein,Recursive linear orderings, inOrders: Description and Roles (Proceedings of the Fourth Conference on Ordered Sets and Their Applications held in L’Arbresle, July 5–11, 1982) (M. Pouzet and D. Richard, eds.), North-Holland, Amsterdam-New York, 1984, pp. 465–475.
[20] S. G. Simpson,Subsystems of Second Order Arithmetic, Springer-Verlag, Berlin, 1999. · Zbl 0909.03048
[21] T. A. Slaman and W. H. Woodin,Extending partial orders to dense linear orders, Annals of Pure and Applied Logic94 (1998), 253–261. · Zbl 0924.03094 · doi:10.1016/S0168-0072(97)00075-4
[22] R. I. Soare,Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin-New York, 1987. · Zbl 0667.03030
[23] R. Solomon,Ordered groups: a case study in reverse mathematics, Bulletin of Symbolic Logic5 (1999), 45–58. · Zbl 0922.03078 · doi:10.2307/421140
[24] E. Szpilrajn,Sur l’extension de l’ordre partiel, Fundamenta Mathematicae16 (1930), 386–389. · JFM 56.0843.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.