Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-26T07:46:06.544Z Has data issue: false hasContentIssue false
  • English
  • Français

THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE

Part of: Graph theory General logic Computability and recursion theory

Published online by Cambridge University Press:  01 February 2021

ALBERTO MARCONE  and
MANLIO VALENTI
ALBERTO MARCONE
Affiliation:
DEPARTMENT OF MATHEMATICS, COMPUTER SCIENCE AND PHYSICS UNIVERSITY OF UDINEUDINE, 33100, ITALYE-mail: [email protected]: [email protected]
MANLIO VALENTI
Affiliation:
DEPARTMENT OF MATHEMATICS, COMPUTER SCIENCE AND PHYSICS UNIVERSITY OF UDINEUDINE, 33100, ITALYE-mail: [email protected]: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around $\mathrm {ATR}_0$ .

Keywords

computable analysisWeihrauch degreeshomogeneous setsopen and clopen Ramsey theorem

MSC classification

Primary: 03D78: Computation over the reals
Secondary: 03D30: Other degrees and reducibilities 03B30: Foundations of classical theories (including reverse mathematics) 05C55: Generalized Ramsey theory
Type
Article
Information
The Journal of Symbolic Logic , Volume 86 , Issue 1 , March 2021 , pp. 316 - 351
Check for updates
Copyright
© The Association for Symbolic Logic 2021

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Anglès D’Auriac, P.-E. and Kihara, T., A comparison of various analytic choice principles. Preprint, 2019. arXiv:1907.02769v1.CrossRefGoogle Scholar
Avigad, J., An effective proof that open sets are Ramsey. Archive for Mathematical Logic, vol. 37 (1998), no. 4, pp. 235–240.CrossRefGoogle Scholar
Brattka, V., Effective Borel measurability and reducibility of functions. Mathematical Logic Quarterly, vol. 51 (2005), no. 1, pp. 19–44.CrossRefGoogle Scholar
Brattka, V., de Brecht, M., and Pauly, A., Closed choice and a uniform low basis theorem. Annals of Pure and Applied Logic, vol. 163 (2012), no. 8, pp. 986–1008.CrossRefGoogle Scholar
Brattka, V. and Gherardi, G., Weihrauch degrees, omniscience principles and weak computability, this Journal, vol. 76 (2011), no. 1, pp. 143–176.Google Scholar
Brattka, V. and Gherardi, G., Completion of choice. Annals of Pure and Applied Logic, vol. 172 (2021), no. 3, 102914.CrossRefGoogle Scholar
Brattka, V., Gherardi, G., and Pauly, A., Weihrauch complexity in computable analysis. Preprint, 2017. arXiv:1707.03202v1.Google Scholar
Brattka, V., Kawamura, A., Marcone, A., and Pauly, A., Measuring the complexity of computational content (Dagstuhl seminar 15392). Dagstuhl Reports, vol. 5 (2016), no. 9, pp. 77–104.Google Scholar
Brattka, V. and Pauly, A., On the algebraic structure of Weihrauch degrees. Logical Methods in Computer Science, vol. 14 (2018), no. 4, pp. 1–36.Google Scholar
Galvin, F. and Prikry, K., Borel sets and Ramsey’s theorem, this Journal, vol. 38 (1973), no. 2, pp. 193–198.Google Scholar
Gherardi, G. and Marcone, A., How incomputable is the separable Hahn–Banach theorem? Notre Dame Journal of Formal Logic, vol. 50 (2009), no. 4, pp. 393–425.CrossRefGoogle Scholar
Goh, J. L., Embeddings between well-orderings: Computability-theoretic reductions. Annals of Pure and Applied Logic, vol. 171 (2020), no. 6, p. 102789.CrossRefGoogle Scholar
Goh, J. L., Measuring the relative complexity of mathematical constructions and theorems, Ph.D. thesis, Cornell University, 2019.Google Scholar
Goh, J. L., Some computability-theoretic reductions between principles around $\mathrm{ATR}_0$. Preprint, 2019. arXiv:1905.06868.Google Scholar
Goh, J. L., Pauly, A., and Valenti, M., Finding descending sequences through ill-founded linear orders, this Journal, to appear. Preprint available from arXiv:2010.03840.Google Scholar
Higuchi, K. and Pauly, A., The degree structure of Weihrauch reducibility. Logical Methods in Computer Science, vol. 9 (2013), no. 2(02), pp. 1–17.CrossRefGoogle Scholar
Kastanas, I. G., On the Ramsey property for sets of reals, this Journal, vol. 48 (1983), no. 4, pp. 1035–1045.Google Scholar
Kihara, T., Marcone, A., and Pauly, A., Searching for an analogue of $\mathrm{ATR}_0$ in the Weihrauch lattice, this Journal, vol. 85 (2020), no. 3, pp. 1006–1043.Google Scholar
Mansfield, R., A footnote to a theorem of Solovay on recursive encodability, Logic Colloquium '77 (Macintyre, A., Pacholski, L., and Paris, J., editors), Studies in Logic and the Foundations of Mathematics, vol. 96, North-Holland, Amsterdam, 1978, pp. 195–198.CrossRefGoogle Scholar
Nash-Williams, C. S. J. A., On well-quasi-ordering transfinite sequences. Mathematical Proceedings of the Cambridge Philosophical Society, vol. 61 (1965), no. 1, pp. 33–39.CrossRefGoogle Scholar
Pauly, A., On the topological aspects of the theory of represented spaces. Computability, vol. 5 (2016), no. 2, pp. 159–180.CrossRefGoogle Scholar
Pauly, A., Computability on the space of countable ordinals. Preprint, 2017. arXiv:1501.00386.Google Scholar
Rogers, H., Theory of Recursive Functions and Effective Computability, first ed., McGraw-Hill, New York, 1967.Google Scholar
Sacks, G. E., Higher Recursion Theory, first ed., Springer Verlag, Berlin, 1990.CrossRefGoogle Scholar
Silver, J., Every analytic set is Ramsey, this Journal, vol. 35 (1970), no. 1, pp. 60–64.Google Scholar
Simpson, S. G., Subsystems of Second Order Arithmetic, second ed., Cambridge University Press, Cambridge, 2009.CrossRefGoogle Scholar
Solovay, R. M., Hyperarithmetically encodable sets. Transactions of the American Mathematical Society, vol. 239 (1978), pp. 99–122.CrossRefGoogle Scholar
Weihrauch, K., Computable Analysis: An Introduction, first ed., Springer, Berlin, 2000.CrossRefGoogle Scholar