Reverse mathematics, well-quasi-orders, and Noetherian spaces (Q283113): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
This paper uses techniques of reverse mathematics to analyze the logical strength of theorems related to work of \textit{J. Goubault-Larrecq} [``On Noetherian spaces'', in: Proceedings of the 22nd annual IEEE symposium on logic in computer science, LICS 2007. Los Alamitos, CA: IEEE Computer Society. 453--462 (2007; \url{doi:10.1109/LICS.2007.34})]. Given a quasi-order \(Q\), one can induce quasi-orders on the power set of \(Q\), for example, the Hoare quasi-order \(\mathcal P ^\flat (Q)\) and the Smyth quasi-order \(\mathcal P^\sharp (Q)\). Quasi-orders can be topologized using the Alexandroff topology \(\mathcal A ( Q)\) or the upper topology \(\mathcal U ( Q)\). If \(Q\) is wqo, then each of the following spaces are Noetherian: \(\mathcal A ({\mathcal {P}}^\flat_{\mathrm f} (Q))\), \(\mathcal U (\mathcal P ^\flat_{\mathrm f} (Q))\), \(\mathcal U (\mathcal P^\sharp_{\mathrm f} (Q))\), \(\mathcal U(\mathcal P^\flat (Q))\), and \(\mathcal U (\mathcal P^\sharp (Q))\). The main result of the paper shows that each of the five preceding assertions is equivalent to ACA\(_0\) over the base system RCA\(_0\). The development makes use of the framework for countable second-countable spaces introduced by \textit{F. G. Dorais} [``Reverse mathematics of compact countable second-countable spaces'', Preprint, \url{arXiv:1110.655}]. Since the arguments are formalized in second-order arithmetic, they provide proofs of Goulbault-Larrecq's results that do not rely on category theoretic methods. Related results on the preservation of wqos and bqos in the induced quasi-orders can be found in the work of \textit{A. Marcone} [in: Reverse mathematics 2001. Wellesley, MA: A K Peters; Urbana, IL: Association for Symbolic Logic (ASL). 303--330 (2005; Zbl 1083.03052)]. | |||
Property / review text: This paper uses techniques of reverse mathematics to analyze the logical strength of theorems related to work of \textit{J. Goubault-Larrecq} [``On Noetherian spaces'', in: Proceedings of the 22nd annual IEEE symposium on logic in computer science, LICS 2007. Los Alamitos, CA: IEEE Computer Society. 453--462 (2007; \url{doi:10.1109/LICS.2007.34})]. Given a quasi-order \(Q\), one can induce quasi-orders on the power set of \(Q\), for example, the Hoare quasi-order \(\mathcal P ^\flat (Q)\) and the Smyth quasi-order \(\mathcal P^\sharp (Q)\). Quasi-orders can be topologized using the Alexandroff topology \(\mathcal A ( Q)\) or the upper topology \(\mathcal U ( Q)\). If \(Q\) is wqo, then each of the following spaces are Noetherian: \(\mathcal A ({\mathcal {P}}^\flat_{\mathrm f} (Q))\), \(\mathcal U (\mathcal P ^\flat_{\mathrm f} (Q))\), \(\mathcal U (\mathcal P^\sharp_{\mathrm f} (Q))\), \(\mathcal U(\mathcal P^\flat (Q))\), and \(\mathcal U (\mathcal P^\sharp (Q))\). The main result of the paper shows that each of the five preceding assertions is equivalent to ACA\(_0\) over the base system RCA\(_0\). The development makes use of the framework for countable second-countable spaces introduced by \textit{F. G. Dorais} [``Reverse mathematics of compact countable second-countable spaces'', Preprint, \url{arXiv:1110.655}]. Since the arguments are formalized in second-order arithmetic, they provide proofs of Goulbault-Larrecq's results that do not rely on category theoretic methods. Related results on the preservation of wqos and bqos in the induced quasi-orders can be found in the work of \textit{A. Marcone} [in: Reverse mathematics 2001. Wellesley, MA: A K Peters; Urbana, IL: Association for Symbolic Logic (ASL). 303--330 (2005; Zbl 1083.03052)]. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jeffry L. Hirst / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03F35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03B30 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6580189 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
second-order arithmetic | |||
Property / zbMATH Keywords: second-order arithmetic / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
reverse mathematics | |||
Property / zbMATH Keywords: reverse mathematics / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
well-quasi-orders (wqo) | |||
Property / zbMATH Keywords: well-quasi-orders (wqo) / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Hoare quasi-order | |||
Property / zbMATH Keywords: Hoare quasi-order / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Smyth quasi-order | |||
Property / zbMATH Keywords: Smyth quasi-order / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1521384790 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q59894048 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1504.07452 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Reverse mathematics and the equivalence of definitions for well and better quasi-orders / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Theorem on Hypersimple Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: REVERSE MATHEMATICS OF MF SPACES / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4111536 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Reverse mathematics and initial intervals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Linear extensions of partial orders and reverse mathematics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topological aspects of poset spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Noetherian Spaces in Verification / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Non-Hausdorff Topology and Domain Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On powerdomains and modality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on well quasi-orderings for powersets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Fraissé's order type conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Filters on computable posets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fine analysis of the quasi-orderings on the power set / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5711893 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The maximal linear extension theorem in second order arithmetic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5537629 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sur les premeilleurs ordres. (On ''prémeilleurs'' orderings) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Partial well‐ordering of sets of vectors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5573961 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Logical methods. In honor of Anil Nerode's 60th birthday / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3395521 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3819052 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 00:10, 12 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reverse mathematics, well-quasi-orders, and Noetherian spaces |
scientific article |
Statements
Reverse mathematics, well-quasi-orders, and Noetherian spaces (English)
0 references
13 May 2016
0 references
This paper uses techniques of reverse mathematics to analyze the logical strength of theorems related to work of \textit{J. Goubault-Larrecq} [``On Noetherian spaces'', in: Proceedings of the 22nd annual IEEE symposium on logic in computer science, LICS 2007. Los Alamitos, CA: IEEE Computer Society. 453--462 (2007; \url{doi:10.1109/LICS.2007.34})]. Given a quasi-order \(Q\), one can induce quasi-orders on the power set of \(Q\), for example, the Hoare quasi-order \(\mathcal P ^\flat (Q)\) and the Smyth quasi-order \(\mathcal P^\sharp (Q)\). Quasi-orders can be topologized using the Alexandroff topology \(\mathcal A ( Q)\) or the upper topology \(\mathcal U ( Q)\). If \(Q\) is wqo, then each of the following spaces are Noetherian: \(\mathcal A ({\mathcal {P}}^\flat_{\mathrm f} (Q))\), \(\mathcal U (\mathcal P ^\flat_{\mathrm f} (Q))\), \(\mathcal U (\mathcal P^\sharp_{\mathrm f} (Q))\), \(\mathcal U(\mathcal P^\flat (Q))\), and \(\mathcal U (\mathcal P^\sharp (Q))\). The main result of the paper shows that each of the five preceding assertions is equivalent to ACA\(_0\) over the base system RCA\(_0\). The development makes use of the framework for countable second-countable spaces introduced by \textit{F. G. Dorais} [``Reverse mathematics of compact countable second-countable spaces'', Preprint, \url{arXiv:1110.655}]. Since the arguments are formalized in second-order arithmetic, they provide proofs of Goulbault-Larrecq's results that do not rely on category theoretic methods. Related results on the preservation of wqos and bqos in the induced quasi-orders can be found in the work of \textit{A. Marcone} [in: Reverse mathematics 2001. Wellesley, MA: A K Peters; Urbana, IL: Association for Symbolic Logic (ASL). 303--330 (2005; Zbl 1083.03052)].
0 references
second-order arithmetic
0 references
reverse mathematics
0 references
well-quasi-orders (wqo)
0 references
Hoare quasi-order
0 references
Smyth quasi-order
0 references
0 references