Inorder theory, a branch of mathematics, asemiorder 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 givenmargin of error are deemedincomparable. Semiorders were introduced and applied inmathematical psychology byDuncan Luce (1956) as a model of human preference. They generalizestrict weak orderings, in which items with equal scores may be tied but there is no margin of error. They are a special case ofpartial orders and ofinterval orders, and can be characterized among the partial orders by additionalaxioms, or by two forbidden four-item suborders.

The original motivation for introducing semiorders was to model human preferences without assuming that incomparability is atransitive 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 numericalutility values, by letting${\displaystyle u}$ be anyutility function that maps the objects to be compared (a set${\displaystyle X}$) toreal 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${\displaystyle u(x)\le u(y)-1}$. Then forms a semiorder.^[2]If, instead, objects are declared comparable whenever their utilities differ, the result would be astrict weak ordering, for which incomparability of objects (based on equality of numbers) would be transitive.^[1]

Forbidden: two mutually incomparable two-pointlinear orders

Forbidden: three linearly ordered points and a fourth incomparable point

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

• Whenever two disjoint pairs of elements are comparable, for instance as and, there must be an additional comparison among these elements, because${\displaystyle u(w)\le u(y)}$ would imply while${\displaystyle u(w)\ge u(y)}$ would imply. Therefore, it is impossible to have two mutually incomparable two-pointlinear orders.^[3]
• If three elements form a linear ordering, then every fourth point${\displaystyle z}$ must be comparable to at least one of them, because${\displaystyle u(z)\le u(x)}$ would imply while${\displaystyle u(z)\ge u(x)}$ would imply, 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 ofaxioms, 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 ofbig 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 (as defined by forbidden orders) includes anuncountabletotally 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.^[7]

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

Conversely, suppose that${\displaystyle (X,\le )}$ is a partial order that has been constructed in this way from a semiorder. Then the semiorder may be recovered by declaring that whenever${\displaystyle x\le y}$ and${\displaystyle x\ne 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 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${\displaystyle u}$ may equivalently be defined as theinterval 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 aninterval order of unit length intervals${\displaystyle ({\ell }_i,{\ell }_i+1)}$.

According toAmartya K. Sen,^[9] semi-orders were examined byDean T. Jamison andLawrence J. Lau^[10] and found to be a special case ofquasitransitive relations. In fact, every semiorder is quasitransitive,^[11] and quasitransitivity is invariant to adding all pairs of incomparable items.^[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.

The number of distinct semiorders on${\displaystyle n}$ unlabeled items is given by theCatalan numbers^[13]$${\displaystyle \frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n}),}$$while the number of semiorders on${\displaystyle n}$ labeled items is given by the sequence^[14]

Any finite semiorder hasorder 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 oflinear extensions are semiorders.^[16]

Semiorders are known to obey the1/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 iswell-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]

Theincomparability graphs of semiorders are calledindifference graphs, and are a special case of theinterval graphs.^[18]

• 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,ISBN 0-7923-4617-3,MR 1472236.

• Properties of binary relations
• Order theory

• Articles with short description
• Short description matches Wikidata
• Pages using multiple image with auto scaled images