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

A quasi-order Q induces two natural quasi-orders on 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 )...

Full description

Saved in:
Bibliographic Details
Published in:Archive for mathematical logic 2016-05, Vol.55 (3-4), p.431-459
Main Authors: Frittaion, Emanuele, Hendtlass, Matthew, Marcone, Alberto, Shafer, Paul, Van der Meeren, Jeroen
Format: Article
Language:English
Subjects:
Algebra
Equivalence
Mathematical logic
Mathematical Logic and Foundations
Mathematical models
Mathematics
Mathematics and Statistics
Preserves
Texts
Theorem proving
Theorems
Topology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A quasi-order Q induces two natural quasi-orders on 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 ) preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on 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 ) 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.
ISSN:0933-5846
1432-0665
DOI:10.1007/s00153-015-0473-4