![WeakOrder4Elements](https://upload.wikimedia.org/wikipedia/commons/b/b9/WeakOrder4Elements.png)
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, especially
order theory
Order theory is a branch of mathematics that investigates the 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 intr ...
, a weak ordering is a mathematical formalization of the intuitive notion of a
ranking
A ranking is a relationship between a set of items such that, for any two items, the first is either "ranked higher than", "ranked lower than" or "ranked equal to" the second.
In mathematics, this is known as a weak order or total preorder of o ...
of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
, some of whose members may be
tied with each other. Weak orders are a generalization of
totally ordered set
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
s (rankings without ties) and are in turn generalized by
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
s and
preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...
s.
[.]
There are several common ways of formalizing weak orderings, that are different from each other but
cryptomorphic (interconvertable with no loss of information): they may be axiomatized as strict weak orderings (partially ordered sets in which incomparability is a
transitive relation
In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive.
Definition
A hom ...
), as total preorders (transitive binary relations in which at least one of the two possible relations exists between every pair of elements), or as ordered partitions (
partitions
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of ...
of the elements into disjoint subsets, together with a total order on the subsets). In many cases another representation called a preferential arrangement based on a
utility function
As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosoph ...
is also possible.
Weak orderings are counted by the
ordered Bell number
In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of ''n'' elements (orderings of the elements into a sequence allowing ties, such as might arise as the outcome ...
s. They are used in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
as part of
partition refinement In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual t ...
algorithms, and in the
C++ Standard Library
The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard. ISO/IEC (2018). '' ISO/IEC 9899:2018(E): Programming Languages - C §7'' Starting from the original ANSI C standard, it was ...
.
[.]
Examples
In
horse racing
Horse racing is an equestrian performance sport, typically involving two or more horses ridden by jockeys (or sometimes driven without riders) over a set distance for competition. It is one of the most ancient of all sports, as its basic pr ...
, the use of
photo finish
A photo finish occurs in a sporting race when multiple competitors cross the finishing line at nearly the same time. As the naked eye may not be able to determine which of the competitors crossed the line first, a photo or video taken at the finis ...
es has eliminated some, but not all, ties or (as they are called in this context)
dead heat
A dead heat is a rare situation in various racing sports in which the performances of competitors are judged to be so close that no difference between them can be resolved. The result is declared a tie and the competitors are awarded a joint ra ...
s, so the outcome of a horse race may be modeled by a weak ordering. In an example from the
Maryland Hunt Cup
The Maryland Hunt Cup is a Timber race, which is an American Steeplechase. It was first run on May 26 1894 and won by Johnny Miller. Eight horses have won the race three times but no horse has won it four times. It is considered one of the most ...
steeplechase in 2007, The Bruce was the clear winner, but two horses Bug River and Lear Charm tied for second place, with the remaining horses farther back; three horses did not finish. In the weak ordering describing this outcome, The Bruce would be first, Bug River and Lear Charm would be ranked after The Bruce but before all the other horses that finished, and the three horses that did not finish would be placed last in the order but tied with each other.
The points of the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...
may be ordered by their
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
from the
origin
Origin(s) or The Origin may refer to:
Arts, entertainment, and media
Comics and manga
* Origin (comics), ''Origin'' (comics), a Wolverine comic book mini-series published by Marvel Comics in 2002
* The Origin (Buffy comic), ''The Origin'' (Bu ...
, giving another example of a weak ordering with infinitely many elements, infinitely many subsets of tied elements (the sets of points that belong to a common
circle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is cons ...
centered at the origin), and infinitely many points within these subsets. Although this ordering has a smallest element (the origin itself), it does not have any second-smallest elements, nor any largest element.
Opinion poll
An opinion poll, often simply referred to as a survey or a poll (although strictly a poll is an actual election) is a human research survey of public opinion from a particular sample. Opinion polls are usually designed to represent the opinion ...
ing in political elections provides an example of a type of ordering that resembles weak orderings, but is better modeled mathematically in other ways. In the results of a poll, one candidate may be clearly ahead of another, or the two candidates may be statistically tied, meaning not that their poll results are equal but rather that they are within the
margin of error
The margin of error is a statistic expressing the amount of random sampling error in the results of a survey. The larger the margin of error, the less confidence one should have that a poll result would reflect the result of a census of the e ...
of each other. However, if candidate
is statistically tied with
and
is statistically tied with
it might still be possible for
to be clearly better than
so being tied is not in this case a
transitive relation
In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive.
Definition
A hom ...
. Because of this possibility, rankings of this type are better modeled as
semiorders than as weak orderings.
Axiomatizations
Suppose throughout that
is a
homogeneous
Homogeneity and heterogeneity are concepts often used in the sciences and statistics relating to the uniformity of a substance or organism. A material or image that is homogeneous is uniform in composition or character (i.e. color, shape, siz ...
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
on a set
(that is,
is a subset of
) and as usual, write
and say that or if and only if
Strict weak orderings
Preliminaries on incomparability and transitivity of incomparability
Two elements
and
of
are said to be with respect to
if neither
is true.
Incomparability with respect to
is itself a homogeneous
symmetric relation
A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if:
:\forall a, b \in X ...
on
that is reflexive if and only if
is
irreflexive
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
(meaning that
is always false), which may be assumed so that
transitivity is the only property this "incomparability relation" needs in order to be an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
.
Define also an induced homogeneous relation
on
by declaring that
where importantly, this definition is necessarily the same as:
if and only if
Two elements
are incomparable with respect to
if and only if
are with respect to
(or less verbosely, ), which by definition means that both
are true.
The relation "are incomparable with respect to
" is thus identical to (that is, equal to) the relation "are
-equivalent" (so in particular, the former is transitive if and only if the latter is).
When
is irreflexive then the property known as "
transitivity of incomparability" (defined below) is the condition necessary and sufficient to guarantee that the relation "are
-equivalent" does indeed form an equivalence relation on
When this is the case, it allows any two elements
satisfying
to be identified as a single object (specifically, they are identified together in their common
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
).
Definition
A strict weak ordering on a set
is a
strict partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
on
for which the induced on
by
is a
transitive relation
In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive.
Definition
A hom ...
.
Explicitly, a strict weak order on
is a
homogeneous relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
on
that has all four of the following properties:
- : For all it is not true that
* This condition holds if and only if the induced relation on is reflexive, where is defined by declaring that is true if and only if is .
- : For all if then
- : For all if is true then is false.
- : For all if is incomparable with (meaning that neither nor is true) and if is incomparable with then is incomparable with
* Two elements are incomparable with respect to if and only if they are equivalent with respect to the induced relation (which by definition means that are both true), where as before, is declared to be true if and only if is false. Thus this condition holds if and only if the
symmetric relation
A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if:
:\forall a, b \in X ...
on defined by " are equivalent with respect to " is a transitive relation, meaning that whenever are -equivalent and also are -equivalent then necessarily are -equivalent. This can also be restated as: whenever and also then necessarily
Properties (1), (2), and (3) are the defining properties of a strict partial order, although there is some redundancy in this list as asymmetry (3) implies irreflexivity (1), and also because irreflexivity (1) and transitivity (2) together imply asymmetry (3). The incomparability relation is always
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
and it will be
reflexive if and only if
is an irreflexive relation (which is assumed by the above definition).
Consequently, a strict partial order
is a strict weak order if and only if its induced incomparability relation is an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
.
In this case, its
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
and moreover, the set
of these equivalence classes can be
strictly totally ordered by a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
, also denoted by
that is defined for all
by:
:
for some (or equivalently, for all) representatives
Conversely, any
strict total order on a
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of
gives rise to a strict weak ordering
on
defined by
if and only if there exists sets
in this partition such that
Not every partial order obeys the transitive law for incomparability. For instance, consider the partial order in the set
defined by the relationship
The pairs
are incomparable but
and
are related, so incomparability does not form an equivalence relation and this example is not a strict weak ordering.
Transitivity of incomparability (together with transitivity) can also be stated in the following forms:
* If
then for all
either
or both.
Or:
* If
is incomparable with
then for all
satisfying
either (
) or (
) or (
is incomparable with
and
is incomparable with
).
Total preorders
Strict weak orders are very closely related to total preorders or (non-strict) weak orders, and the same mathematical concepts that can be modeled with strict weak orderings can be modeled equally well with total preorders. A total preorder or weak order is a
preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...
in which any two elements are comparable. A total preorder
satisfies the following properties:
* : For all
if
then
* : For all
** Which implies : for all
A
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
is a total preorder which is antisymmetric, in other words, which is also a
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
. Total preorders are sometimes also called preference relations.
The
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
of a strict weak order is a total preorder, and vice versa, but it seems more natural to relate strict weak orders and total preorders in a way that preserves rather than reverses the order of the elements. Thus we take the
converse
Converse may refer to:
Mathematics and logic
* Converse (logic), the result of reversing the two parts of a definite or implicational statement
** Converse implication, the converse of a material implication
** Converse nonimplication, a logical c ...
of the complement: for a strict weak ordering
define a total preorder
by setting
whenever it is not the case that
In the other direction, to define a strict weak ordering < from a total preorder
set
whenever it is not the case that
In any preorder there is a
corresponding equivalence relation where two elements
and
are defined as equivalent if
In the case of a preorder the corresponding partial order on the set of equivalence classes is a total order. Two elements are equivalent in a total preorder if and only if they are incomparable in the corresponding strict weak ordering.
Ordered partitions
A
partition of a set
In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.
Every equivalence relation on a set defines a partition of this set, and every parti ...
is a family of non-empty disjoint subsets of
that have
as their union. A partition, together with a
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
on the sets of the partition, gives a structure called by
Richard P. Stanley
Richard Peter Stanley (born June 23, 1944) is an Emeritus Professor of Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. From 2000 to 2010, he was the Norman Levinson Professor of Applied Mathematics. He r ...
an ordered partition and by
Theodore Motzkin
Theodore Samuel Motzkin (26 March 1908 – 15 December 1970) was an Israeli-American mathematician.
Biography
Motzkin's father Leo Motzkin, a Ukrainian Jew, went to Berlin at the age of thirteen to study mathematics. He pursued university studi ...
a list of sets. An ordered partition of a finite set may be written as a
finite sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called th ...
of the sets in the partition: for instance, the three ordered partitions of the set
are
In a strict weak ordering, the equivalence classes of incomparability give a set partition, in which the sets inherit a total ordering from their elements, giving rise to an ordered partition. In the other direction, any ordered partition gives rise to a strict weak ordering in which two elements are incomparable when they belong to the same set in the partition, and otherwise inherit the order of the sets that contain them.
Representation by functions
For sets of sufficiently small
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
, a third axiomatization is possible, based on real-valued functions. If
is any set then a real-valued function
on
induces a strict weak order on
by setting
The associated total preorder is given by setting
and the associated equivalence by setting
The relations do not change when
is replaced by
(
composite function
In mathematics, function composition is an operation that takes two function (mathematics), functions and , and produces a function such that . In this operation, the function is function application, applied to the result of applying the ...
), where
is a
strictly increasing real-valued function defined on at least the range of
Thus for example, a
utility function
As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosopher ...
defines a
preference
In psychology, economics and philosophy, preference is a technical term usually used in relation to choosing between alternatives. For example, someone prefers A over B if they would rather choose A than B. Preferences are central to decision theo ...
relation. In this context, weak orderings are also known as preferential arrangements.
If
is finite or countable, every weak order on
can be represented by a function in this way.
[.] However, there exist strict weak orders that have no corresponding real function. For example, there is no such function for the
lexicographic order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
on
Thus, while in most preference relation models the relation defines a utility function
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' wi ...
order-preserving transformations, there is no such function for
lexicographic preferences In economics, lexicographic preferences or lexicographic orderings describe comparative preferences where an agent prefers any amount of one good (X) to any amount of another (Y). Specifically, if offered several bundles of goods, the agent will ch ...
.
More generally, if
is a set,
is a set with a strict weak ordering
and
is a function, then
induces a strict weak ordering on
by setting
As before, the associated total preorder is given by setting
and the associated equivalence by setting
It is not assumed here that
is an
injective function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
, so a class of two equivalent elements on
may induce a larger class of equivalent elements on
Also,
is not assumed to be a
surjective function
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
, so a class of equivalent elements on
may induce a smaller or empty class on
However, the function
induces an injective function that maps the partition on
to that on
Thus, in the case of finite partitions, the number of classes in
is less than or equal to the number of classes on
Related types of ordering
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 incompar ...
s generalize strict weak orderings, but do not assume transitivity of incomparability. A strict weak order that is
trichotomous is called a strict total order.
[.] The total preorder which is the inverse of its complement is in this case a
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
.
For a strict weak order
another associated reflexive relation is its
reflexive closure In mathematics, the reflexive closure of a binary relation ''R'' on a set ''X'' is the smallest reflexive relation on ''X'' that contains ''R''.
For example, if ''X'' is a set of distinct numbers and ''x R y'' means "''x'' is less than ''y''", the ...
, a (non-strict) partial order
The two associated reflexive relations differ with regard to different
and
for which neither
nor
: in the total preorder corresponding to a strict weak order we get
and
while in the partial order given by the reflexive closure we get neither
nor
For strict total orders these two associated reflexive relations are the same: the corresponding (non-strict) total order.
The reflexive closure of a strict weak ordering is a type of
series-parallel partial order
In order theory, order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations...
The series-parallel partial orders may be charact ...
.
All weak orders on a finite set
Combinatorial enumeration
The number of distinct weak orders (represented either as strict weak orders or as total preorders) on an
-element set is given by the following sequence :
These numbers are also called the Fubini numbers or ordered Bell numbers.
For example, for a set of three labeled items, there is one weak order in which all three items are tied. There are three ways of partitioning the items into one
singleton
Singleton may refer to:
Sciences, technology Mathematics
* Singleton (mathematics), a set with exactly one element
* Singleton field, used in conformal field theory Computing
* Singleton pattern, a design pattern that allows only one instance ...
set and one group of two tied items, and each of these partitions gives two weak orders (one in which the singleton is smaller than the group of two, and one in which this ordering is reversed), giving six weak orders of this type. And there is a single way of partitioning the set into three singletons, which can be totally ordered in six different ways. Thus, altogether, there are 13 different weak orders on three items.
Adjacency structure
![Permutohedron](https://upload.wikimedia.org/wikipedia/commons/3/3e/Permutohedron.svg)
Unlike for partial orders, the family of weak orderings on a given finite set is not in general connected by moves that add or remove a single order relation to or from a given ordering. For instance, for three elements, the ordering in which all three elements are tied differs by at least two pairs from any other weak ordering on the same set, in either the strict weak ordering or total preorder axiomatizations. However, a different kind of move is possible, in which the weak orderings on a set are more highly connected. Define a to be a weak ordering with two equivalence classes, and define a dichotomy to be with a given weak ordering if every two elements that are related in the ordering are either related in the same way or tied in the dichotomy. Alternatively, a dichotomy may be defined as a
Dedekind cut
In mathematics, Dedekind cuts, named after German mathematician Richard Dedekind but previously considered by Joseph Bertrand, are а method of construction of the real numbers from the rational numbers. A Dedekind cut is a partition of the rat ...
for a weak ordering. Then a weak ordering may be characterized by its set of compatible dichotomies. For a finite set of labeled items, every pair of weak orderings may be connected to each other by a sequence of moves that add or remove one dichotomy at a time to or from this set of dichotomies. Moreover, the
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
that has the weak orderings as its vertices, and these moves as its edges, forms a
partial cube
In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cu ...
.
Geometrically, the total orderings of a given finite set may be represented as the vertices of a
permutohedron
In mathematics, the permutohedron of order ''n'' is an (''n'' − 1)-dimensional polytope embedded in an ''n''-dimensional space. Its vertex coordinates (labels) are the permutations of the first ''n'' natural numbers. The edges ident ...
, and the dichotomies on this same set as the facets of the permutohedron. In this geometric representation, the weak orderings on the set correspond to the faces of all different dimensions of the permutohedron (including the permutohedron itself, but not the empty set, as a face). The
codimension
In mathematics, codimension is a basic geometric idea that applies to subspaces in vector spaces, to submanifolds in manifolds, and suitable subsets of algebraic varieties.
For affine and projective algebraic varieties, the codimension equals the ...
of a face gives the number of equivalence classes in the corresponding weak ordering. In this geometric representation the partial cube of moves on weak orderings is the graph describing the
covering relation
In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering relation is commonly used to graphically expres ...
of the
face lattice
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
of the permutohedron.
For instance, for
the permutohedron on three elements is just a regular hexagon. The face lattice of the hexagon (again, including the hexagon itself as a face, but not including the empty set) has thirteen elements: one hexagon, six edges, and six vertices, corresponding to the one completely tied weak ordering, six weak orderings with one tie, and six total orderings. The graph of moves on these 13 weak orderings is shown in the figure.
Applications
As mentioned above, weak orders have applications in utility theory.
In
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
and other types of
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
problem, the prioritization of solutions or of bases is often given by a weak order, determined by a real-valued
objective function
In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cos ...
; the phenomenon of ties in these orderings is called "degeneracy", and several types of tie-breaking rule have been used to refine this weak ordering into a total ordering in order to prevent problems caused by degeneracy.
Weak orders have also been used in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, in
partition refinement In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual t ...
based algorithms for
lexicographic breadth-first search
In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadt ...
and
lexicographic topological ordering. In these algorithms, a weak ordering on the vertices of a graph (represented as a family of sets that
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
the vertices, together with a
doubly linked list
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked record (computer science), records called node (computer science), nodes. Each node contains three field (computer science), fields: ...
providing a total order on the sets) is gradually refined over the course of the algorithm, eventually producing a total ordering that is the output of the algorithm.
[.]
In the
Standard Library
In computer programming, a standard library is the library made available across implementations of a programming language. These libraries are conventionally described in programming language specifications; however, contents of a language's as ...
for the
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
programming language, the
set and multiset data types sort their input by a comparison function that is specified at the time of template instantiation, and that is assumed to implement a strict weak ordering.
See also
*
*
* − the equivalent subsets in the finest weak ordering consistent with a given relation
References
{{Order theory
Binary relations
Integer sequences
Order theory