Abstract
A quasi-order Q induces two natural quasi-orders on \({\mathcal{P}(Q)}\), but if Q is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq (Proceedings of the 22nd Annual IEEE Symposium 4 on Logic in Computer Science (LICS’07), pp. 453–462, 2007) showed that moving from a well-quasi-order Q to the quasi-orders on \({\mathcal{P}(Q)}\) preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on \({\mathcal{P}(Q)}\) are Noetherian, which means that they contain no infinite strictly descending sequences of closed sets. We analyze various theorems of the form “if Q is a well-quasi-order then a certain topology on (a subset of) \({\mathcal{P}(Q)}\) is Noetherian” in the style of reverse mathematics, proving that these theorems are equivalent to ACA 0 over RCA 0. To state these theorems in RCA 0 we introduce a new framework for dealing with second-countable topological spaces.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cholak P., Marcone A., Solomon R.: Reverse mathematics and the equivalence of definitions for well and better quasi-orders. J. Symb. Log. 69(3), 683–712 (2004)
Dekker J.C.E.: A theorem on hypersimple sets. Proc. Am. Math. Soc. 5, 791–796 (1954)
Dorais, F.G.: Reverse mathematics of compact countable second-countable spaces. arXiv:1110.6555v1 (2011)
Erdős P., Rado R.: Advanced problems and solutions: solutions: 4358. Am. Math. Mon. 59(4), 255–257 (1952)
Friedman, H.: Some systems of second order arithmetic and their use. In: Proceedings of the International Congress of Mathematicians, vol. 1, 1975, pp. 235–242. Vancouver, B.C. (1974)
Frittaion, E.: Reverse Mathematics and Partial Orders. Ph.D. Thesis, Università di Udine (2014)
Frittaion E., Marcone A.: Linear extensions of partial orders and reverse mathematics. Math. Log. Q. 58(6), 417–423 (2012)
Frittaion E., Marcone A.: Reverse mathematics and initial intervals. Ann. Pure Appl. Log. 165(3), 858–879 (2014)
Goubault-Larrecq, J.: On Noetherian spaces. In: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS’07), pp. 453–462 (2007)
Goubault-Larrecq, J.: Noetherian spaces in verification. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) Automata, Languages and Programming, Part II. Lecture Notes in Computer Science, vol. 6199, pp. 2–21. Springer, Berlin (2010)
Goubault-Larrecq, J.: Non-Hausdorff topology and domain theory. In: New Mathematical Monographs, vol. 22. Cambridge University Press, Cambridge (2013). [On the cover: Selected topics in point-set topology]
Hirst, J.: Combinatorics in Subsystems of Second Order Arithmetic. Ph.D. Thesis, The Pennsylvania State University (1987)
Jančar P.: A note on well quasi-orderings for powersets. Inf. Process. Lett. 72(5-6), 155–160 (1999)
Laver R.: On Fraïssé’s order type conjecture. Ann. Math. (2) 93, 89–111 (1971)
Lempp S., Mummert C.: Filters on computable posets. Notre Dame J. Form. Log. 47(4), 479–485 (2006)
Marcone A.: Fine analysis of the quasi-orderings on the power set. Order 18(4), 339–347 (2001)
Marcone, A.: Wqo and bqo theory in subsystems of second order arithmetic. In: Simpson, S.G. (ed.) Reverse Mathematics 2001. Lecture Notes in Logic, vol. 21, pp. 303–330. Association for Symbolic Logic, La Jolla, CA (2005)
Marcone A., Shore R.A.: The maximal linear extension theorem in second order arithmetic. Arch. Math. Log. 50(5-6), 543–564 (2011)
Mummert C: Reverse mathematics of MF spaces. J. Math. Log. 6(2), 203–232 (2006)
Mummert C., Stephan F.: Topological aspects of poset spaces. Mich. Math. J. 59(1), 3–24 (2010)
Nash-Williams C.St.J.A.: On better-quasi-ordering transfinite sequences. Proc. Camb. Philos. Soc. 64, 273–290 (1968)
Pouzet M.: Sur les prémeilleurordres. Ann. Inst. Fourier (Grenoble) 22(2), 1–19 (1972)
Rado R.: Partial well-ordering of sets of vectors. Mathematika 1, 89–95 (1954)
Rogers H. Jr: Theory of Recursive Functions and Effective Computability, 2nd edn. MIT Press, Cambridge (1987)
Shore, R.A.: On the strength of Fraïssé’s conjecture. In: Crossley, J.N., Remmel, J.B., Shore, R.A., Sweedler, M.E. (eds.) Logical Methods. Progress in Computer Science and Applied Logic, vol. 12, pp. 782–813. Birkhäuser Boston Inc., Boston (1993) (Papers from the conference in honor of Anil Nerode’s sixtieth birthday held at Cornell University, Ithaca, New York, June 1–3, 1992)
Simpson, S.G.: Subsystems of second order arithmetic. In: Perspectives in Logic, 2nd edn. Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY (2009)
Soare, R.I.: Recursively Enumerable Sets and Degrees: a Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic. Springer, Berlin (1987)
Winskel G.: On powerdomains and modality. Theor. Comput. Sci. 36(1), 127–137 (1985)
Author information
Authors and Affiliations
Corresponding author
Additional information
Emanuele Frittaion’s research is supported by the Japan Society for the Promotion of Science. Matthew Hendtlass’s research was supported by PRIN 2009 Grant “Modelli e Insiemi.” Alberto Marcone’s research was supported by PRIN 2009 Grant “Modelli e Insiemi” and PRIN 2012 Grant “Logica, Modelli e Insiemi.” Paul Shafer was an FWO Pegasus Long Postdoctoral Fellow. Jeroen Van der Meeren was an FWO Ph.D. Fellow.
Rights and permissions
About this article
Cite this article
Frittaion, E., Hendtlass, M., Marcone, A. et al. Reverse mathematics, well-quasi-orders, and Noetherian spaces. Arch. Math. Logic 55, 431–459 (2016). https://doi.org/10.1007/s00153-015-0473-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-015-0473-4