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)].
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)].
Reviewer: Jeffry L. Hirst (Boone)
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 |
Keywords:
reverse mathematics; proof theory; effective content; Szpilrajn’s theorem; linear ordering; partial ordering; combinatoricsReferences:
| [1] | Bonnet, R., Stratifications et extension des genres de chaînes dénombrables, Comptes Rendus de l’Académie des Sciences, Paris, 269, A880-A882 (1969) · Zbl 0206.28001 |
| [2] | Bonnet, R.; Pouzet, M., Extension et stratification d’ensembles dispersés, Comptes Rendus de l’Académie des Sciences, Paris, 268, A1512-A1515 (1969) · Zbl 0188.04203 |
| [3] | Bonnet, R.; Pouzet, M.; Rival, I., Linear extensions of ordered sets, Ordered Sets, 125-170 (1982), Dordrecht-Boston, Mass.: D. Reidel Publishing Co., Dordrecht-Boston, Mass. · Zbl 0499.06002 |
| [4] | Dehn, M., Über unendliche diskontinuierliche Gruppen, Mathematische Annalen, 71, 116-144 (1912) · JFM 42.0508.03 · doi:10.1007/BF01456932 |
| [5] | Downey, R. G., Computability theory and linear orderings, Handbook of Recursive Mathematics, Vol. 2, 823-976 (1998), Amsterdam: North-Holland, Amsterdam · Zbl 0941.03045 |
| [6] | Ershov, Yu. L.; Goncharov, S. S.; Nerode, A.; Remmel, J., Handbook of Recursive Mathematics, Vols. 1 and 2 (1998), Amsterdam: North-Holland, Amsterdam · Zbl 0930.03037 |
| [7] | Friedman, H., Some systems of second order arithmetic and their uses, Proceedings of the International Congress of Mathematicians, Vancouver, 1974, 235-242 (1975), Montreal, Que.: Canadian Mathematical Congress, Montreal, Que. · Zbl 0344.02022 |
| [8] | Friedman, H.; Robertson, N.; Seymour, P.; Simpson, S. G., The metamathematics of the graph minor theorem, Logic and Combinatorics, 229-261 (1987), Providence, R.I.: American Mathematical Society, Providence, R.I. · Zbl 0635.03060 |
| [9] | Friedman, H.; Simpson, S. G.; Smith, R. L., Countable algebra and set existence axioms, Annals of Pure and Applied Logic, 25, 141-181 (1983) · Zbl 0575.03038 · doi:10.1016/0168-0072(83)90012-X |
| [10] | Fröhlich, A.; Shepherdson, J. C., Effective procedures in field theory, Transactions of the Royal Society of London, 248, 407-432 (1956) · Zbl 0070.03502 · doi:10.1098/rsta.1956.0003 |
| [11] | Jockusch, C. G., Ramsey’s theorem and recursion theory, Journal of Symbolic Logic, 37, 268-280 (1972) · Zbl 0262.02042 · doi:10.2307/2272972 |
| [12] | Jockusch, C. G.; Soare, R. I., Π_1^0classes and degrees of theories, Transactions of the American Mathematical Society, 173, 33-56 (1972) · Zbl 0262.02041 · doi:10.2307/1996261 |
| [13] | P. Jullien,Contribution à l’étude des types d’ordre dispersés, Thèse, Marseille, 1969. |
| [14] | Metakides, G.; Nerode, A., Effective content of field theory, Annals of Mathematical Logic, 17, 289-320 (1979) · Zbl 0469.03028 · doi:10.1016/0003-4843(79)90011-1 |
| [15] | Paris, J.; Harrington, L.; Barwise, J., A mathematical incompleteness in Peano arithmetic, Handbook of Mathematical Logic, 1133-1142 (1977), Amsterdam: North-Holland, Amsterdam |
| [16] | Rabin, M. O., Computable algebra, general theory and theory of computable fields, Transactions of the American Mathematical Society, 95, 341-360 (1960) · Zbl 0156.01201 · doi:10.2307/1993295 |
| [17] | Rogers, H. G., Theory of Recursive Functions and Effective Computability (1967), New York: McGraw-Hill, New York · Zbl 0183.01401 |
| [18] | Rosenstein, J. G., Linear Orderings (1982), New York-London: Academic Press, New York-London · Zbl 0488.04002 |
| [19] | Rosenstein, J. G.; Pouzet, M.; Richard, D., Recursive linear orderings, Orders: Description and Roles, 465-475 (1984), Amsterdam-New York: North-Holland, Amsterdam-New York · Zbl 0554.06001 |
| [20] | Simpson, S. G., Subsystems of Second Order Arithmetic (1999), Berlin: Springer-Verlag, Berlin · Zbl 0909.03048 |
| [21] | Slaman, T. A.; Woodin, W. H., Extending partial orders to dense linear orders, Annals of Pure and Applied Logic, 94, 253-261 (1998) · Zbl 0924.03094 · doi:10.1016/S0168-0072(97)00075-4 |
| [22] | Soare, R. I., Recursively Enumerable Sets and Degrees (1987), Berlin-New York: Springer-Verlag, Berlin-New York · Zbl 0623.03042 |
| [23] | Solomon, R., Ordered groups: a case study in reverse mathematics, Bulletin of Symbolic Logic, 5, 45-58 (1999) · Zbl 0922.03078 · doi:10.2307/421140 |
| [24] | Szpilrajn, E., Sur l’extension de l’ordre partiel, Fundamenta Mathematicae, 16, 386-389 (1930) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
