Interval orders and reverse mathematics

DOI10.1305/NDJFL/1187031412MaRDI QIDQ2469435zbMATH OpenOpenAlexFDO

Authors Alberto Marcone

Publication date 5 February 2008

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

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

zbMATH Keywords

forbidden suborderinginterval ordersproper interval ordersrelation of complete sequencereverse mathematics

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35) Partial orders, general (06A06)

Abstract: We study the reverse mathematics of interval orders. We establish the logical strength of the implications between various definitions of the notion of interval order. We also consider the strength of different versions of the characterization theorem for interval orders: a partial order is an interval order if and only if it does not contain $2oplus2$. We also study proper interval orders and their characterization theorem: a partial order is a proper interval order if and only if it contains neither $2oplus2$ nor $3oplus1$.

Review text

In the terminology of [\textit{P. C. Fishburn}, Interval orders and interval graphs. A study of partially ordered sets. New York etc.: John Wiley \& Sons (1985; Zbl 0551.06001)], a partial order is an \textsl{interval order} if its elements can be mapped to nonempty intervals of a linear ordering in such a way that the partial order element \(p\) is less than the element \(q\) if and only if every element of the interval associated with \(p\) precedes every element of the interval associated with \(q\). The author presents several naïvely equivalent formalizations of this concept, and uses the tools of reverse mathematics to determine the exact logical strength of statements about the relationships between the formalizations. These results are also connected to a forbidden subordering characterization of interval orders. Similar theorems for proper interval orders are also stated and proved.

Recommendations

• Interval orders based on weak orders
• Reverse mathematics and initial intervals
• Interval orders and circle orders
• Interval orders and dimension
• Linear extensions of partial orders and reverse mathematics

Cited in

(12)

• Some remarks on a problem of J. D. Monk
• Interval orders based on weak orders
• Interval orders based on arbitrary ordered sets
• On admissible orders over closed subintervals of \([0, 1]\)
• Uniquely orderable interval graphs
• Well, better and in-between
• Reverse mathematics and initial intervals
• A partial order structure on interval orders
• A NOTE ON THE REVERSE MATHEMATICS OF THE SORITES
• scientific article; zbMATH DE number 2236640 (Why is no real title available?)
• Infinite saturated orders
• Linear orders and semiorders close to an interval order

This page was built for publication: Interval orders and reverse mathematics

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