Semiorder
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.
The original motivation for introducing semiorders was to model human preferences without assuming that incomparability is a transitive relation.
by the smallest amount that is perceptible as a difference, while
Then, a person who desires more of the material would prefer
are comparable, so incomparability does not obey the transitive law.
[1] 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
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
[2] 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.
[1] A semiorder, defined from a utility function as above, is a partially ordered set with the following two properties:[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.
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
(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.
Of the axioms that a partial order is required to obey, reflexivity (
defined in this way meets the three requirements of a partial order that it be reflexive, antisymmetric, and transitive.
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.
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
According to Amartya K. Sen,[9] semi-orders were examined by Dean T. Jamison and Lawrence J. Lau[10] and found to be a special case of quasitransitive relations.
[12] 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.
unlabeled items is given by the Catalan numbers[13]
labeled items is given by the sequence[14] 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
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.
