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. Utility theory. The original motivation for introducing semiorders was to model human preferences without assuming that incomparability is a transitive relation. For instance, if formula_1, formula_2, and formula_3 represent three quantities of the same material, and formula_1 and formula_3 differ by the smallest amount that is perceptible as a difference, while formula_2 is halfway between the two of them, then it is reasonable for a preference to exist between formula_1 and formula_3 but not between the other two pairs, violating transitivity. To model this mathematically, suppose that objects are given numerical  utility values, by letting formula_9 be any utility function that maps the objects to be compared (a set formula_10) 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 formula_11 on the objects, by setting formula_12 whenever formula_13. Then formula_14 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. Axiomatics. 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. 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 formula_14 (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. supplies a precise characterization of the semiorders that may be defined numerically. Relation to other kinds of order. Partial orders. One may define a partial order ("X",≤) from a semiorder ("X",<) by declaring that whenever either or . Of the axioms that a partial order is required to obey, reflexivity ("x" ≤ "x") follows automatically from this definition, antisymmetry (if "x" ≤ "y" and "y" ≤ "x" then "x" = "y") follows from the first semiorder axiom, and transitivity (if "x" ≤ "y" and "y" ≤ "z" then "x" ≤ "z ) 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	Semiorder
25298377	, 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 formula_9 may equivalently be defined as the interval order defined by the intervals formula_35, so every semiorder is an example of an interval order. A relation is a semiorder if, and only if, it can be obtained 	Semiorder
25298378	as an interval order of unit length intervals formula_36. 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 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. Combinatorial enumeration. The number of 	Semiorder
25298379	distinct semiorders on formula_31 unlabeled items is given by the Catalan numbers formula_38 while the number of semiorders on formula_31 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 formula_1 and formula_2 such that formula_1 appears earlier 	Semiorder
25298380	than formula_2 in between 1/3 and 2/3 of the linear extensions of the semiorder. The set of semiorders on an formula_31-element set is well-graded": if two semiorders on the same set differ from each other by the addition or removal of formula_45 order relations, then it is possible to find a path of formula_45 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.