Semiorder


In order theory, a branch of mathematics, a semiorder is a type of ordering for items with numerical scores, where items with widely differing scores are compared by their scores and where scores within a given margin of error are deemed incomparable. Semiorders were introduced and applied in mathematical psychology by as a model of human preference. They generalize strict weak orderings, in which items with equal scores may be tied but there is no margin of error. They are a special case of partial orders and of interval orders, and can be characterized among the partial orders by additional axioms, or by two forbidden four-item suborders.

Definition

Let X be a set of items, and let < be a binary relation on X.
Items x and y are said to be incomparable, written here as x ~ y, if neither x < y nor y < x is true. Then the pair is a semiorder if it satisfies the following three axioms:
  1. For all x and y, it is not possible for both x < y and y < x to be true. That is, < must be an asymmetric relation
  2. For all x, y, z, and w, if x < y, y ~ z, and z < w, then x < w.
  3. For all x, y, z, and w, if x < y and y < z, then either x < w or w < z. Equivalently, with the same assumptions on x, y, z, every other item w must be comparable to at least one of x, y, or z.
It follows from the first axiom that x ~ x, and therefore the second axiom implies that < is a transitive relation.

Relation to other kinds of order

Partial orders

One may define a partial order from a semiorder by declaring that whenever either or. Of the axioms that a partial order is required to obey, reflexivity follows automatically from this definition, antisymmetry follows from the first semiorder axiom, and transitivity follows from the second semiorder axiom. Conversely, from a partial order defined in this way, the semiorder may be recovered by declaring that whenever and. The first of the semiorder axioms listed above follows automatically from the axioms defining a partial order, but the others do not. The second and third semiorder axioms forbid partial orders of four items forming two disjoint chains: the second axiom forbids two chains of two items each, while the third item forbids a three-item chain with one unrelated item.

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 vertice is incomparable to its two closest left neighbors, but they are comparable.

Interval orders

A relation is a semiorder if, and only if, it can be obtained as an interval order of unit length intervals.

Quasitransitive relations

According to Amartya K. Sen, semi-orders were examined by Dean T. Jamison and Lawrence J. Lau and found to be a special case of quasitransitive relations. In fact, every semiorder is a quasitransitive relation, since it is a transitive one. Moreover, adding to a given semiorder all its pairs of incomparable items keeps the resulting relation a quasitransitive one.

Utility theory

The original motivation for introducing semiorders was to model human preferences without assuming that incomparability is a transitive relation. For instance, if x, y, and z represent three quantities of the same material, and x and z differ by the smallest amount that is perceptible as a difference, while y is halfway between the two of them, then it is reasonable for a preference to exist between x and z but not between the other two pairs, violating transitivity.
Thus, suppose that X is a set of items, and u is a utility function that maps the members of X to real numbers. A strict weak ordering can be defined on x by declaring two items to be incomparable when they have equal utilities, and otherwise using the numerical comparison, but this necessarily leads to a transitive incomparability relation. Instead, if one sets a numerical threshold such that utilities within that threshold of each other are declared incomparable, then a semiorder arises.
Specifically, define a binary relation < from X and u by setting x < y whenever u ≤ u − 1. Then is a semiorder. It may equivalently be defined as the interval order defined by the intervals .
In the other direction, not every semiorder can be defined from numerical utilities in this way. For instance, if a semiorder includes an uncountable totally ordered subset then there do not exist sufficiently many sufficiently well-spaced real-numbers to represent this subset numerically. However, every finite semiorder can be defined from a utility function. supplies a precise characterization of the semiorders that may be defined numerically.
If a semiorder is given only in terms of the order relation between its pairs of elements, then it is possible to construct a utility function that represents the order in time, where is the number of elements in the semiorder.

Combinatorial enumeration

The number of distinct semiorders on n unlabeled items is given by the Catalan numbers
while the number of semiorders on n labeled items is given by the sequence

Other results

Any finite semiorder has order dimension at most three.
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.
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 x and y such that x appears earlier than y in between 1/3 and 2/3 of the linear extensions of the semiorder.
The set of semiorders on an n-element set is well-graded: if two semiorders on the same set differ from each other by the addition or removal of k order relations, then it is possible to find a path of 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.
The incomparability graphs of semiorders are called indifference graphs, and are a special case of the interval graphs.