Linear extensions of partial orders and reverse mathematics

DOI10.1002/MALQ.201200025MaRDI QIDQ3144869zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Emanuele Frittaion, Alberto Marcone

Publication date 10 December 2012

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

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

zbMATH Keywords

\(\tau \)-likeACAembeddabilityfinite unionFUFinfinite pigeonhole principlelinear extensions of partial orderlinearizabilityreverse mathematics

Mathematics Subject Classification ID

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

Abstract: We introduce the notion of au-like partial order, where au is one of the linear order types omega, omega*, omega+omega*, and zeta. For example, being omega-like means that every element has finitely many predecessors, while being zeta-like means that every interval is finite. We consider statements of the form "any au-like partial order has a au-like linear extension" and "any au-like partial order is embeddable into au" (when au is zeta this result appears to be new). Working in the framework of reverse mathematics, we show that these statements are equivalent either to BSigma^0_2 or to ACA_0 over the usual base system RCA_0.

Recommendations

• Computability-theoretic and proof-theoretic aspects of partial and linear orderings
• The maximal linear extension theorem in second order arithmetic
• Infinite saturated orders
• Reverse mathematics and initial intervals
• Reverse mathematics and Ramsey properties of partial orderings

Cites work

• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Computability-theoretic and proof-theoretic aspects of partial and linear orderings
• Equivalence between Fraïssé's conjecture and Jullien's theorem
• Hilbert versus Hindman
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• On the strength of Ramsey's theorem for pairs
• Subsystems of second order arithmetic
• The maximal linear extension theorem in second order arithmetic
• Weak comparability of well orderings and reverse mathematics

Cited in

(13)

• Linear extensions of additive partial orders
• Computability-theoretic and proof-theoretic aspects of partial and linear orderings
• On the teaching complexity of linear sets
• Linearization of definable order relations
• The uniform content of partial and linear orders
• Interval orders and reverse mathematics
• Reverse mathematics, well-quasi-orders, and Noetherian spaces
• Reverse mathematics and initial intervals
• Linearisations and the Ershov hierarchy
• scientific article; zbMATH DE number 1421071 (Why is no real title available?)
• Reduction games, provability and compactness
• Reverse mathematics and order theoretic fixed point theorems
• Infinite saturated orders

This page was built for publication: Linear extensions of partial orders and reverse mathematics

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