# Interval order

2020 Mathematics Subject Classification: Primary: 06A [MSN][ZBL]

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, [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, [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.

How to Cite This Entry:
Interval order. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Interval_order&oldid=54265
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article