Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Frittaion, Emanuele; Hendtlass, Matt; Marcone, Alberto; Shafer, Paul; Van der Meeren, Jeroen (2015)
Publisher: Springer Verlag
Languages: English
Types: Article
Subjects: Mathematics - Logic
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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)
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article