---
tag: 2N4Z69K7V6
kind: definition
name: Interval order
msc: [06A06, 91B08]
defines: VSNQV29KFJ
uses: [0QV2JS9RJ3, 0Q1D85B8G6]
sources:
  - url: https://en.wikipedia.org/wiki/Interval_order
---

## Definition

Let $(P, \le)$ be a [[partially ordered set|0QV2JS9RJ3]], with strict order $<$.
The poset $P$ is an *interval order* if there are real numbers $l_x \le r_x$ for each $x \in P$ such that, for all $x, y \in P$,
$$x < y \iff r_x < l_y.$$
The closed [[interval|0Q1D85B8G6]] $[l_x, r_x]$ is said to represent $x$.

## Remarks

Example: the poset on $\set{a, b, c}$ with $a < b$ as the only strict relation is an interval order.
The intervals $[0, 1]$, $[2, 3]$ and $[0.5, 2.5]$ for $a$, $b$, $c$ work: $1 < 2$ gives $a < b$, and the interval of $c$ meets both others.
Non-example: the poset $\mathbf{2} + \mathbf{2}$ with $a < b$, $c < d$ and no other strict relation is not an interval order.
Intervals would give $r_a < l_b$ and $r_c < l_d$, and also $l_d \le r_a$ and $l_b \le r_c$, so $r_a < l_b \le r_c < l_d \le r_a$, which is impossible.
Fishburn's theorem says that a finite poset is an interval order if and only if it has no subposet isomorphic to $\mathbf{2} + \mathbf{2}$.
Every total order is an interval order: on a finite total order, use the points $[i, i]$.