Semiorder
Encyclopedia
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 some threshold of each other and otherwise using the numerical comparison of their scores. Semiorders were introduced and applied in mathematical psychology
by as a model of human preference without the assumption that indifference is transitive
. They generalize strict weak ordering
s, form a special case of partial orders and interval order
s, and can be characterized among the partial orders by two forbidden four-item suborders.
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:
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 whenever either or . 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 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.
. 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.
Thus, suppose that X is a set of items, and u is a utility function that maps the members of X to real number
s. 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. It may equivalently be defined as the interval order
defined by the intervals [u(x),u(x) + 1].
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. supplies a precise characterization of the semiorders that may be defined numerically.
s
while the number of semiorders on n labeled items is given by the sequence
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 extension
s 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 x and y such that x appears earlier than y in between 1/3 and 2/3 of the linear extensions of the semiorder.
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.
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, 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 some threshold of each other and otherwise using the numerical comparison of their scores. Semiorders were introduced and applied in mathematical psychology
Mathematical psychology
Mathematical psychology is an approach to psychological research that is based on mathematical modeling of perceptual, cognitive and motor processes, and on the establishment of law-like rules that relate quantifiable stimulus characteristics with quantifiable behavior...
by as a model of human preference without the assumption that indifference is transitive
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
. They generalize strict weak ordering
Strict weak ordering
In mathematics, especially order theory, a strict weak ordering is a binary relation In mathematics, especially order theory, a strict weak ordering is a binary relation ...
s, form a special case of partial orders and interval order
Interval order
In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.More formally, a...
s, and can be characterized among the partial orders by two forbidden four-item suborders.
Definition
Let X be a set of items, and let < be a binary relationBinary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
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:
- For all x and y, it is not possible for both x < y and y < x to be true. That is, < must be an asymmetric relationAsymmetric relationAsymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.That is,\lnot....
- 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 or z ~ w.
It follows from the first axiom that x ~ x, and therefore the second axiom (with y = z) implies that < is a transitive relation
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
.
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 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 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.
Utility
The original motivation for introducing semiorders was to model human preferences without assuming (as strict weak orderings do) that incomparability is a transitive relationTransitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
. 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.
Thus, suppose that X is a set of items, and u is a utility function that maps the members of X to real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. 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. It may equivalently be defined as the interval order
Interval order
In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.More formally, a...
defined by the intervals [u(x),u(x) + 1].
The converse is not necessarily true: for instance, if a semiorder (X,<) includes an uncountable totally ordered subset
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
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. 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 numberCatalan number
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involvingrecursively defined objects...
s
while the number of semiorders on n labeled items is given by the sequence
- 1, 1, 3, 19, 183, 2371, 38703, 763099, 17648823, ... .
Any finite semiorder has order dimension
Order dimension
In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
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 extension
Linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a linear order that is compatible with the partial order.-Definitions:...
s are semiorders.
Semiorders are known to obey the 1/3–2/3 conjecture
1/3–2/3 conjecture
In order theory, a branch of mathematics, the 1/3–2/3 conjecture states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible...
: 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.
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.