Reverse mathematics, well-quasi-orders, and Noetherian spaces

Article, Preprint English OPEN
Frittaion, E ; Hendtlass, M ; Marcone, A ; Shafer, PE ; Van Der Meeren, J (2016)

A quasi-order Q induces two natural quasi-orders on P(Q) 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 P(Q) P(Q) preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on P(Q) 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) P(Q) P(Q) is Noetherian” in the style of reverse mathematics, proving that these theorems are equivalent to ACA0 over RCA0. To state these theorems in RCA0 we introduce a new framework for dealing with second-countable topological spaces.
  • References (11)
    11 references, page 1 of 2

    [CMS04] Peter Cholak, Alberto Marcone, and Reed Solomon, Reverse mathematics and the equivalence of definitions for well and better quasi-orders, J. Symbolic Logic 69 (2004), no. 3, 683-712. MR2078917 (2005e:03020)

    [Dek54] Jacob C. E. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791-796. MR0063995 (16,209b)

    [Mar01] Alberto Marcone, Fine analysis of the quasi-orderings on the power set, Order 18 (2001), no. 4, 339-347 (2002). MR1884426 (2003a:06003)

    [Mar05] , Wqo and bqo theory in subsystems of second order arithmetic, Reverse mathematics 2001, 2005, pp. 303-330. MR2185443 (2006g:03106) [MS10] Carl Mummert and Frank Stephan, Topological aspects of poset spaces, Michigan Math. J. 59 (2010), no. 1, 3-24. MR2654139 (2011k:06026) [MS11] Alberto Marcone and Richard A. Shore, The maximal linear extension theorem in second order arithmetic, Arch. Math. Logic 50 (2011), no. 5-6, 543-564. MR2805296 (2012g:03036)

    [Mum06] Carl Mummert, Reverse mathematics of MF spaces, J. Math. Log. 6 (2006), no. 2, 203-232. MR2317427 (2008d:03011)

    [NW68] Crispin St. J. A. Nash-Williams, On better-quasi-ordering transfinite sequences, Proc. Cambridge Philos. Soc. 64 (1968), 273-290. MR0221949 (36 #5001)

    [Pou72] Maurice Pouzet, Sur les pr´emeilleurordres, Ann. Inst. Fourier (Grenoble) 22 (1972), no. 2, 1-19. MR0342446 (49 #7192)

    [Rad54] Richard Rado, Partial well-ordering of sets of vectors, Mathematika 1 (1954), 89-95. MR0066441 (16,576b)

    [Rog87] Hartley Rogers Jr., Theory of recursive functions and effective computability, Second, MIT Press, Cambridge, MA, 1987. MR886890 (88b:03059) [Sho93] Richard A. Shore, On the strength of Fra¨ıss´e's conjecture, Logical methods (Ithaca, NY, 1992), 1993, pp. 782-813. MR1281172 (95e:03163)

    [Sim09] Stephen G. Simpson, Subsystems of second order arithmetic, Second, Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR2517689 (2010e:03073) [Soa87] Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1987. A study of computable functions and computably generated sets. MR882921 (88m:03003)

  • Metrics
    No metrics available
Share - Bookmark