Interval orders and reverse mathematics (Q2469435): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:58, 3 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Interval orders and reverse mathematics |
scientific article |
Statements
Interval orders and reverse mathematics (English)
0 references
5 February 2008
0 references
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.
0 references
reverse mathematics
0 references
interval orders
0 references
proper interval orders
0 references
relation of complete sequence
0 references
forbidden subordering
0 references