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 Duncan Luce (1956) 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.
The original motivation for introducing semiorders was to model human preferences without assuming that incomparability is a transitive relation. For instance, suppose that , , and represent three quantities of the same material, and that is larger than by the smallest amount that is perceptible as a difference, while is halfway between the two of them. Then, a person who desires more of the material would prefer to , but would not have a preference between the other two pairs. In this example, and are incomparable in the preference ordering, as are and , but and are comparable, so incomparability does not obey the transitive law.
To model this mathematically, suppose that objects are given numerical utility values, by letting be any utility function that maps the objects to be compared (a set ) 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 on the objects, by setting whenever . Then forms a semiorder. If, instead, objects are declared comparable whenever their utilities differ, the result would be a strict weak ordering, for which incomparability of objects (based on equality of numbers) would be transitive.
A semiorder, defined from a utility function as above, is a partially ordered set with the following two properties:
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.  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. If a semiorder on 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 , where the is an instance of big O notation.
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 (as defined by forbidden orders) includes an uncountable totally ordered subset then there do not exist sufficiently many sufficiently well-spaced real-numbers for it to be representable by a utility function. Fishburn (1973) supplies a precise characterization of the semiorders that may be defined numerically.
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 (if and then ) follows from the first semiorder axiom. Transitivity (if and then ) follows from the second semiorder axiom. Therefore, the binary relation defined in this way meets the three requirements of a partial order that it be reflexive, antisymmetric, and transitive.
Conversely, suppose that is a partial order that has been constructed in this way from a semiorder. Then the semiorder may be recovered by declaring that whenever and . 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 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).
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.
The semiorder defined from a utility function may equivalently be defined as the interval order defined by the intervals , 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 .
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 quasitransitive, and quasitransitivity is invariant to adding all pairs of incomparable items. 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.
The number of distinct semiorders on unlabeled items is given by the Catalan numbers
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 and such that appears earlier than in between 1/3 and 2/3 of the linear extensions of the semiorder.
The set of semiorders on an -element set is well-graded: if two semiorders on the same set differ from each other by the addition or removal of order relations, then it is possible to find a path of 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.