Theorems of hyperarithmetic analysis and almost theorems of hyperarithmetic analysis. (English) Zbl 1505.03025
The authors provide an overview of their recent work on theorems of hyperarithmetic analysis and almost theorems of hyperarithmetic analysis. Details will appear in the authors’ article [“Halin’s infinite ray theorems: Complexity and reverse mathematics” (submitted)] and the third author’s article [“Almost theorems of hyperarithmetic analysis”, J. Symb. Log. (to appear)]. The ray theorems, which are graph theoretic theorems of hyperarithmetic analysis, are stronger than \(\mathsf{ACA}_0\) plus fixed recursive iterations of the jump, but weaker than \(\mathsf{ATR}_0\). The almost hyperarithmetic theorems constitute a new zoo-like class of results outside the usual linear reverse mathematics hierarchy. Taken alone, they are weak statements, but in combination with \(\mathsf{ACA}_0\) they become theorems of hyperarithmetic analysis. The weakness of the statements is demonstrated via conservation results based on uniform effective tree forcing.
Reviewer: Jeffry L. Hirst (Boone)
MSC:
| 03B30 | Foundations of classical theories (including reverse mathematics) |
| 03D55 | Hierarchies of computability and definability |
| 03F35 | Second- and higher-order arithmetic and fragments |
| 05C63 | Infinite graphs |
| 03D80 | Applications of computability and recursion theory |
Keywords:
hyperarithmetic analysis; conservative; Halin type theorems; ubiquity; hyperjump; reverse mathematicsReferences:
| [1] | Barnes, J., Goh, J. L., and Shore, R. A., Halin’s infinite ray theorems: Complexity and reverse mathematics, to appear. |
| [2] | Bowler, N., Carmesin, J., and Pott, J., Edge disjoint double rays in infinite graphs: A Halin type result. Journal of Combinatorial Theory, Series B, vol. 111 (2015), pp. 1-16. · Zbl 1307.05163 |
| [3] | Conidis, C. J., Comparing theorems of hyperarithmetic analysis with the arithmetic Bolzano-Weierstrass theorem. Transactions of the American Mathematical Society, vol. 364 (2012), pp. 4465-4494. · Zbl 1287.03030 |
| [4] | Diestel, R., Graph Theory, fifth ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. · Zbl 1375.05002 |
| [5] | Friedman, H. M., Subsystems of set theory and analysis, Ph. D. thesis, Massachusetts Institute of Technology, 1967. |
| [6] | Friedman, H. M., Higher set theory and mathematical practice. Annals of Mathematical Logic, vol. 2 (1971), pp. 325-357. · Zbl 0215.32702 |
| [7] | Friedman, H. M., Some systems of second order arithmetic and their use, Proceedings of the International Congress of Mathematicians, Vancouver 1974,vol. 1, Canadian Mathematical Congress, 1975, pp. 235-242. · Zbl 0344.02022 |
| [8] | Goh, J. L., The strength of an axiom of finite choice for branches in trees, to appear. · Zbl 07781906 |
| [9] | Halin, R., Uber die Maximalzahl fremder unendlicher Wege. Graphen Mathematische Nachrichten, vol. 30 (1965), pp. 63-85. · Zbl 0131.20904 |
| [10] | Halin, R., Die Maximalzahl fremder zweiseitig undendlicher Wege in Graphen. Mathematische Nachrichten, vol. 44 (1970), pp. 119-127. · Zbl 0159.25303 |
| [11] | Hirschfeldt, D. R., Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles (C. Chong, Q. Feng, T. A. Slaman, W. Hugh Woodin, and Y. Yang, editors), Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 28, World Scientific, Singapore, 2014. · Zbl 1304.03001 |
| [12] | Hirschfeldt, D. R., Shore, R. A., and Slaman, T. A., The atomic model theorem and type omitting. Transactions of the American Mathematical Society, vol. 361 (2009), pp. 5805-5837. · Zbl 1184.03005 |
| [13] | Jullien, P., Contribution à l’Étude des Types d’Ordre Dispersés, Ph.D. thesis, Marseille, 1969. |
| [14] | Kihara, T., Degree structures of mass problems & formal systems of Ramsey-type theorems, Master’s thesis, Tohoku University, 2009. |
| [15] | Kreisel, G., The axiom of choice and the class of hyperarithmetic functions. Indagationes Mathematicae, vol. 24 (1962), pp. 307-319. · Zbl 0108.00802 |
| [16] | Lerman, M., Degrees of Unsolvability, Springer, Berlin, 1983. · Zbl 0542.03023 |
| [17] | Montalbán, A., Indecomposable linear orderings and hyperarithmetic analysis. Journal of Mathematical Logic, vol. 6 (2006), pp. 89-120. · Zbl 1105.03061 |
| [18] | Montalbán, A., On the \(\ {\varPi}_1^1\) -separation principle. Mathematical Logic Quarterly, vol. 54 (2008), pp. 563-578. · Zbl 1155.03042 |
| [19] | Montalbán, A., Open questions in reverse mathematics, this Journal, vol. 17 (2011), pp. 431-454. · Zbl 1233.03023 |
| [20] | Neeman, I., The strength of Jullien’s indecomposability theorem. Journal of Mathematical Logic, vol. 8 (2008), pp. 93-119. · Zbl 1186.03071 |
| [21] | Neeman, I., Necessary uses of \({\varSigma}_1^1\ {}\) induction in a reversal. The Journal of Symbolic Logic, vol. 76 (2011), pp. 561-574. · Zbl 1218.03005 |
| [22] | Rogers, H. Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, second ed., 1987. |
| [23] | Rosenstein, J. G., Linear Orderings, Pure and Applied Mathematics, vol. 98, Academic Press, New York-London, 1982. · Zbl 0488.04002 |
| [24] | Sacks, G. E., Higher Recursion Theory, Perspectives in Mathematical Logic, Springer, Berlin, 1990. · Zbl 0716.03043 |
| [25] | Shore, R. A., Almost theorems of hyperarithmetic analysis, to appear. · Zbl 1525.03056 |
| [26] | Simpson, S. G., Subsystems of Second Order Arithmetic, second ed., Perspectives in Logic, ASL and Cambridge University Press, New York, 2009. · Zbl 1181.03001 |
| [27] | Simpson, S. G., Tanaka, K., and Yamazaki, T., Some conservation results on weak König’s lemma. Annals of Pure and Applied Logic, vol. 118 (2002), pp. 87-114. · Zbl 1016.03064 |
| [28] | Steel, J., Forcing with tagged trees, Annals of Mathematical Logic, vol. 15 (1978), pp. 55-74. · Zbl 0404.03020 |
| [29] | Van Wesep, R. A., Subsystems of second-order arithmetic, and descriptive set theory under the axiom of determinateness, Ph.D. thesis, University of California, Berkeley, 1977. |
| [30] | Yamazaki, T., Some more conservation results on the Baire category theorem. Mathematical Logic Quarterly, vol. 46 (2000), pp. 105-110. · Zbl 0942.03061 |
| [31] | Yamazaki, T., Topics on conservation results, unpublished slides for seminar talk in Sendai Logic and Philosophy Seminar, February 22-24, 2009, Matsushima, Miyagi, Japan, 2009. |
| [32] | Yokoyama, K., On \({\varPi}_1^1\) conservativity for \({\varPi}_2^1\) theories in second-order arithmetic, Proceedings of the 10th Asian Logic Conference, (T. Arai, C. T. Chong, R. Downey, Q. Feng and H. Ono, editors) World Scientific, Singapore, 2009, pp. 375-386. |
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.
