OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Frittaion, E; Hendtlass, M; Marcone, A; Shafer, PE; Van Der Meeren, J (2016)
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

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok