The maximal linear extension theorem in second order arithmetic

DOI10.1007/S00153-011-0231-1zbMATH Open1227.03076arXiv1009.1528OpenAlexW3098312506MaRDI QIDQ634769FDOQ634769

Alberto Marcone, Richard A. Shore

Publication date: 16 August 2011

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Abstract: We show that the maximal linear extension theorem for well partial orders is equivalent over RCA_0 to ATR_0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR_0 over RCA_0.

Full work available at URL: https://arxiv.org/abs/1009.1528

zbMATH Keywords

ATRMLEreverse mathematicsmaximal chainwell-quasi-ordermaximal linear extensionMCwqo

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

Cites Work

• Graph minors. XX: Wagner's conjecture
• On Fraissé's order type conjecture
• Reverse mathematics and the equivalence of definitions for well and better quasi-orders
• Theory of relations. Transl. from the French by P. Clote. With an appendix by Norbert Sauer.
• Ordered sets
• The theory of well-quasi-ordering: a frequently discovered concept
• On the strength of Ramsey's theorem for pairs
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Ordering by Divisibility in Abstract Algebras
• Weak comparability of well orderings and reverse mathematics
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Ordinal numbers and the Hilbert basis theorem
• Computable linearizations of well-partial-orderings
• On Chains and Antichains in well Founded Partially Ordered Sets
• Partially well ordered sets and partial ordinals
• Reverse mathematics and ordinal exponentiation
• On Fraïssé's conjecture for linear orders of finite Hausdorff rank
• Program termination and well partial orderings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (9)

• Reverse mathematics, well-quasi-orders, and Noetherian spaces
• Reverse mathematics and initial intervals
• The Reverse Mathematics of wqos and bqos
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Computing maximal chains
• (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE
• A computably enumerable partial ordering without computably enumerable maximal chains and antichains
• Linear extensions of partial orders and reverse mathematics
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The limits of determinacy in second-order arithmetic 👍 👎
• The maximal order of certain arithmetic functions 👍 👎
• Maximal extensions of ordered fields 👍 👎
• Linear extensions of semiorders: A maximization problem 👍 👎
• The mean value theorem in second order arithmetic 👍 👎
• Maximal extensions with simple multiplication for the algebra of matrices of the second order 👍 👎
• The Recursively Mahlo Property in Second Order Arithmetic 👍 👎

This page was built for publication: The maximal linear extension theorem in second order arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q634769)