Semiorder

In

, or by two forbidden four-item suborders.

Utility theory

The original motivation for introducing semiorders was to model human preferences without assuming that incomparability is a transitive relation. For instance, suppose that ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$ represent three quantities of the same material, and that ${\displaystyle x}$ is larger than ${\displaystyle z}$ by the smallest amount that is perceptible as a difference, while ${\displaystyle y}$ is halfway between the two of them. Then, a person who desires more of the material would prefer ${\displaystyle x}$ to ${\displaystyle z}$, but would not have a preference between the other two pairs. In this example, ${\displaystyle x}$ and ${\displaystyle y}$ are incomparable in the preference ordering, as are ${\displaystyle y}$ and ${\displaystyle z}$, but ${\displaystyle x}$ and ${\displaystyle z}$ are comparable, so incomparability does not obey the transitive law.^[1]

To model this mathematically, suppose that objects are given numerical

, by letting ${\displaystyle u}$ be any that maps the objects to be compared (a set ${\displaystyle X}$) to real numbers. Set a numerical threshold (which may be normalized to 1) such that utilities within that threshold of each other are declared incomparable, and define a binary relation ${\displaystyle <}$ on the objects, by setting ${\displaystyle x<y}$ whenever ${\displaystyle u(x)\leq u(y)-1}$. Then ${\displaystyle (X,<)}$ forms a semiorder.^[2] If, instead, objects are declared comparable whenever their utilities differ, the result would be a

Axiomatics

A semiorder, defined from a utility function as above, is a partially ordered set with the following two properties:^[3]

• Whenever two disjoint pairs of elements are comparable, for instance as ${\displaystyle w<x}$ and ${\displaystyle y<z}$, there must be an additional comparison among these elements, because ${\displaystyle u(w)\leq u(y)}$ would imply ${\displaystyle w<z}$ while ${\displaystyle u(w)\geq u(y)}$ would imply ${\displaystyle y<x}$. Therefore, it is impossible to have two mutually incomparable two-point
  linear orders.^[3]
• If three elements form a linear ordering ${\displaystyle w<x<y}$, then every fourth point ${\displaystyle z}$ must be comparable to at least one of them, because ${\displaystyle u(z)\leq u(x)}$ would imply ${\displaystyle z<y}$ while ${\displaystyle u(z)\geq u(x)}$ would imply ${\displaystyle w<z}$, in either case showing that ${\displaystyle z}$ is comparable to ${\displaystyle w}$ or to ${\displaystyle y}$. So it is impossible to have a three-point linear order with a fourth incomparable point.[3]

Conversely, every finite partial order that avoids the two forbidden four-point orderings described above can be given utility values making it into a semiorder. ^[4] Therefore, rather than being a consequence of a definition in terms of utility, these forbidden orderings, or equivalent systems of axioms, can be taken as a combinatorial definition of semiorders.^[5] If a semiorder on ${\displaystyle n}$ elements is given only in terms of the order relation between its pairs of elements, obeying these axioms, then it is possible to construct a utility function that represents the order in time ${\displaystyle O(n^{2})}$, where the ${\displaystyle O}$ is an instance of big O notation.^[6]

For orderings on infinite sets of elements, the orderings that can be defined by utility functions and the orderings that can be defined by forbidden four-point orders differ from each other. For instance, if a semiorder ${\displaystyle (X,<)}$ (as defined by forbidden orders) includes an

Relation to other kinds of order

Partial orders

One may define a

partial order

${\displaystyle (X,\leq )}$ from a semiorder ${\displaystyle (X,<)}$ by declaring that ${\displaystyle x\leq y}$ whenever either ${\displaystyle x<y}$ or ${\displaystyle x=y}$. Of the axioms that a partial order is required to obey, reflexivity (${\displaystyle x\leq x}$) follows automatically from this definition. Antisymmetry (if ${\displaystyle x\leq y}$ and ${\displaystyle y\leq x}$ then ${\displaystyle x=y}$) follows from the first semiorder axiom. Transitivity (if ${\displaystyle x\leq y}$ and ${\displaystyle y\leq z}$ then ${\displaystyle x\leq z}$) follows from the second semiorder axiom. Therefore, the binary relation ${\displaystyle (X,\leq )}$ defined in this way meets the three requirements of a partial order that it be reflexive, antisymmetric, and transitive.

Conversely, suppose that ${\displaystyle (X,\leq )}$ is a partial order that has been constructed in this way from a semiorder. Then the semiorder may be recovered by declaring that ${\displaystyle x<y}$ whenever ${\displaystyle x\leq y}$ and ${\displaystyle x\neq y}$. Not every partial order leads to a semiorder in this way, however: The first of the semiorder axioms listed above follows automatically from the axioms defining a partial order, but the others do not. A partial order that includes four elements forming two two-element chains would lead to a relation ${\displaystyle (X,<)}$ that violates the second semiorder axiom, and a partial order that includes four elements forming a three-element chain and an unrelated item would violate the third semiorder axiom (cf. pictures in section #Axiomatics).

Weak orders

Every strict weak ordering < is also a semi-order. More particularly, transitivity of < and transitivity of incomparability with respect to < together imply the above axiom 2, while transitivity of incomparability alone implies axiom 3. The semiorder shown in the top image is not a strict weak ordering, since the rightmost vertex is incomparable to its two closest left neighbors, but they are comparable.

Interval orders

The semiorder defined from a utility function ${\displaystyle u}$ may equivalently be defined as the interval order defined by the intervals ${\displaystyle [u(x),u(x)+1]}$,^[8] so every semiorder is an example of an interval order. A relation is a semiorder if, and only if, it can be obtained as an interval order of unit length intervals ${\displaystyle (\ell _{i},\ell _{i}+1)}$.

Quasitransitive relations

According to

Removing all non-vertical red lines from the topmost image results in a Hasse diagram for a relation that is still quasitransitive, but violates both axiom 2 and 3; this relation might no longer be useful as a preference ordering.

Combinatorial enumeration

The number of distinct semiorders on ${\displaystyle n}$ unlabeled items is given by the Catalan numbers^[13]

while the number of semiorders on ${\displaystyle n}$ labeled items is given by the sequence^[14]

Other results

Any finite semiorder has order dimension at most three.^[15]

Among all partial orders with a fixed number of elements and a fixed number of comparable pairs, the partial orders that have the largest number of linear extensions are semiorders.^[16]

Semiorders are known to obey the 1/3–2/3 conjecture: in any finite semiorder that is not a total order, there exists a pair of elements ${\displaystyle x}$ and ${\displaystyle y}$ such that ${\displaystyle x}$ appears earlier than ${\displaystyle y}$ in between 1/3 and 2/3 of the linear extensions of the semiorder.^[3]

The set of semiorders on an ${\displaystyle n}$-element set is well-graded: if two semiorders on the same set differ from each other by the addition or removal of ${\displaystyle k}$ order relations, then it is possible to find a path of ${\displaystyle k}$ steps from the first semiorder to the second one, in such a way that each step of the path adds or removes a single order relation and each intermediate state in the path is itself a semiorder.^[17]

The incomparability graphs of semiorders are called indifference graphs, and are a special case of the interval graphs.^[18]

Notes

References

Further reading

• Pirlot, M.; Vincke, Ph. (1997), Semiorders: Properties, representations, applications, Theory and Decision Library. Series B: Mathematical and Statistical Methods, vol. 36, Dordrecht: Kluwer Academic Publishers Group,
  MR 1472236
  .