View source for Interval order

{{TEX|done}}{{MSC|06A}}

''interval ordering, interval partially ordered set, interval poset''

A partial order on the set $S$ of closed intervals of the real line $\mathbb{R}$, defined by
$$
I_1 \le I_2 \Leftrightarrow x \le y\ \text{in}\ \mathbb{R}\ \text{for all}\ x\in I_1,\,y \in I_2\ .
$$

Such a [[partially ordered set]] (more precisely, one isomorphic to it) is called an interval order.

A linear order, also called a [[totally ordered set]], is an interval order (but an interval order need not be total, of course).

There is the following forbidden sub-poset characterization of interval orders (the Fishburn theorem, [[#References|[a1]]]): A poset $P$ is an interval order if and only if $P$ does not contain the disjoint sum $\mathbf{2} + \mathbf{2}$ as a sub-poset (cf. also [[Disjoint sum of partially ordered sets]]). Here, $\mathbf{2}$ is the totally ordered set $\{1,2\}$, $1<2$, so that $\mathbf{2} + \mathbf{2} = \{a_1,a_2,b_1,b_2\}$ with $a_1 < a_2$, $b_1 < b_2$ and no other comparable pairs of distinct elements.

A poset is called a semi-order if there is a function $f : P \rightarrow \mathbf{R}$ such that $x < y$ in $P$ if and only if $f(y) > f(x)+1$. Clearly, a semi-order is isomorphic to a ''unit interval order'': an interval order with all intervals of length $1$. Here too, a forbidden sub-poset characterization holds (the Scott–Suppes theorem, [[#References|[a2]]]): A poset $P$ is a semi-order if and only if it does not contain either $\mathbf{2} + \mathbf{2}$ or $\mathbf{3} + \mathbf{1}$ as a sub-poset.

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  P.C. Fishburn, "Intransitive indifference with unequal indifference intervals"  ''J. Math. Psychol.'' , '''7'''  (1970)  pp. 144–149 {{ZBL|0191.31501}}</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Scott,   P. Suppes, "Foundational aspects of the theories of measurement"  ''J. Symbolic Logic'' , '''23'''  (1958)  pp. 113–128</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  W.T. Trotter, "Partially ordered sets"  R.L. Graham (ed.)  M. Grötschel (ed.)  L. Lovász (ed.) , ''Handbook of Combinatorics'' , '''I''' , North-Holland  (1995)  pp. 433–480</TD></TR>
<TR><TD valign="top">[b1]</TD> <TD valign="top">  Martin Charles Golumbic, Ann N. Trenk, "Tolerance Graphs", Cambridge Studies in Advanced Mathematics '''89''' Cambridge University Press (2004) {{ISBN|0-521-82758-2}}</TD></TR>
</table>