World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0028771796
Reproduction Date:

Title: Semiorder  
Author: World Heritage Encyclopedia
Language: English
Subject: Indifference graph, List of order structures in mathematics, R. Duncan Luce, IT
Publisher: World Heritage Encyclopedia


An example of a semiorder, shown by its Hasse diagram. The horizontal blue lines indicate the spacing of the y-coordinates of the points; two points are comparable when their y coordinates differ by at least one unit.

In order theory, a branch of mathematics, a semiorder is a type of ordering that may be determined for a set of items with numerical scores by declaring two items to be incomparable when their scores are within a given margin of error of each other, and by using the numerical comparison of their scores when those scores are sufficiently far apart. Semiorders were introduced and applied in mathematical psychology by Luce (1956) as a model of human preference without the assumption that indifference is transitive. They generalize strict weak orderings, form a special case of partial orders and interval orders, and can be characterized among the partial orders by two forbidden four-item suborders.


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 (X,<) 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 irreflexive, antisymmetric relation
  • For all x, y, z, and w, if it is true that x < y, y ~ z, and z < w, then it must also be true that x < w.
  • For all x, y, z, and w, if it is true that x < y, y < z, and y ~ w, then it cannot also be true that x ~ w and z ~ w simultaneously.

It follows from the first axiom that x ~ x, and therefore the second axiom (with y = z) implies that < is a transitive relation.

One may define a partial order (X,≤) from a semiorder (X,<) by declaring that xy whenever either x < y or x = y. 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 x < y whenever xy and xy. 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.


The original motivation for introducing semiorders was to model human preferences without assuming (as strict weak orderings do) 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.[2]

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 (which may be normalized to 1) 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(x) ≤ u(y) − 1. Then (X,<) is a semiorder.[3] It may equivalently be defined as the interval order defined by the intervals [u(x),u(x) + 1].[4]

The converse is not necessarily true: for instance, if a semiorder (X,<) 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 in this way.[5] Fishburn (1973) supplies a precise characterization of the semiorders that may be defined numerically.

Other results

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

1, 1, 3, 19, 183, 2371, 38703, 763099, 17648823, ... (sequence A006531 in OEIS).[7]

Any finite semiorder has order dimension at most three.[8]

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.[9]

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.[10]

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.[11]

The incomparability graphs of semiorders are called indifference graphs, and are a special case of the interval graphs.[12]


  1. ^ Luce (1956) describes an equivalent set of four axioms, the first two of which combine the definition of incomparability and the first axiom listed here.
  2. ^ Luce (1956), p. 179.
  3. ^ Luce (1956), Theorem 3 describes a more general situation in which the threshold for comparability between two utilities is a function of the utility rather than being identically 1.
  4. ^ Fishburn (1970).
  5. ^ This result is typically credited to Scott & Suppes (1958); see, e.g., Rabinovitch (1977). However, Luce (1956), Theorem 2 proves a more general statement, that a finite semiorder can be defined from a utility function and a threshold function whenever a certain underlying weak order can be defined numerically. For finite semiorders, it is trivial that the weak order can be defined numerically with a unit threshold function.
  6. ^ Kim & Roush (1978).
  7. ^ Chandon, Lemaire & Pouget (1978).
  8. ^ Rabinovitch (1978).
  9. ^ Fishburn & Trotter (1992).
  10. ^ Brightwell (1989).
  11. ^ Doignon & Falmagne (1997).
  12. ^  .


Additional reading

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.