Transitive binary relations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation be transitive: for all if and then Contents |
In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered sets (rankings without ties) and are in turn generalized by (strictly) partially ordered sets and preorders. [1]
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 (strictly partially ordered sets in which incomparability is a transitive relation), 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 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 is also possible.
Weak orderings are counted by the ordered Bell numbers. They are used in computer science as part of partition refinement algorithms, and in the C++ Standard Library. [2]
In horse racing, the use of photo finishes has eliminated some, but not all, ties or (as they are called in this context) dead heats, so the outcome of a horse race may be modeled by a weak ordering. [3] In an example from the Maryland Hunt Cup 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. [4] 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 may be ordered by their distance from the origin, 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 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 polling 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 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. Because of this possibility, rankings of this type are better modeled as semiorders than as weak orderings. [5]
Suppose throughout that is a homogeneous binary relation on a set (that is, is a subset of ) and as usual, write and say that holds or is true if and only if
Preliminaries on incomparability and transitivity of incomparability
Two elements and of are said to be incomparable with respect to if neither nor is true. [1] A strict partial order is a strict weak ordering if and only if incomparability with respect to is an equivalence relation. Incomparability with respect to is always a homogeneous symmetric relation on It is reflexive if and only if is irreflexive (meaning that is always false), which will be assumed so that transitivity is the only property this "incomparability relation" needs in order to be an equivalence relation.
Define also an induced homogeneous relation on by declaring that where importantly, this definition is not necessarily the same as: if and only if Two elements are incomparable with respect to if and only if are equivalent with respect to (or less verbosely, -equivalent), 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 exactly 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).
Definition
A strict weak ordering on a set is a strict partial order on for which the incomparability relation induced on by is a transitive relation. [1] Explicitly, a strict weak order on is a homogeneous relation on that has all four of the following properties:
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). [6] The incomparability relation is always symmetric 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 this case, its equivalence classes partition and moreover, the set of these equivalence classes can be strictly totally ordered by a binary relation, also denoted by that is defined for all by:
Conversely, any strict total order on a partition 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.
For transitivity of incomparability, each of the following conditions is necessary, and for strict partial orders also sufficient:
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 which any two elements are comparable. [7] A total preorder satisfies the following properties:
A total order is a total preorder which is antisymmetric, in other words, which is also a partial order. Total preorders are sometimes also called preference relations.
The complement 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 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 [8]
In any preorder there is a corresponding equivalence relation where two elements and are defined as equivalent if In the case of a total 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.
A partition of a set is a family of non-empty disjoint subsets of that have as their union. A partition, together with a total order on the sets of the partition, gives a structure called by Richard P. Stanley an ordered partition [9] and by Theodore Motzkin a list of sets. [10] An ordered partition of a finite set may be written as a finite sequence 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.
For sets of sufficiently small cardinality, a fourth 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), where is a strictly increasing real-valued function defined on at least the range of Thus for example, a utility function defines a preference relation. In this context, weak orderings are also known as preferential arrangements. [11]
If is finite or countable, every weak order on can be represented by a function in this way. [12] However, there exist strict weak orders that have no corresponding real function. For example, there is no such function for the lexicographic order on Thus, while in most preference relation models the relation defines a utility function up to order-preserving transformations, there is no such function for lexicographic preferences.
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, 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, 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
Semiorders generalize strict weak orderings, but do not assume transitivity of incomparability. [13] A strict weak order that is trichotomous is called a strict total order. [14] The total preorder which is the inverse of its complement is in this case a total order.
For a strict weak order another associated reflexive relation is its reflexive closure, 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. [14] The reflexive closure of a strict weak ordering is a type of series-parallel partial order.
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 (sequence A000670 in the OEIS ):
Elements | Any | Transitive | Reflexive | Symmetric | Preorder | Partial order | Total preorder | Total order | Equivalence relation |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65,536 | 3,994 | 4,096 | 1,024 | 355 | 219 | 75 | 24 | 15 |
n | 2n2 | 2n(n−1) | 2n(n+1)/2 | ∑n k=0k!S(n, k) | n! | ∑n k=0S(n, k) | |||
OEIS | A002416 | A006905 | A053763 | A006125 | A000798 | A001035 | A000670 | A000142 | A000110 |
Note that S(n, k) refers to Stirling numbers of the second kind.
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 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.
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 dichotomy to be a weak ordering with two equivalence classes, and define a dichotomy to be compatible 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 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 that has the weak orderings as its vertices, and these moves as its edges, forms a partial cube. [15]
Geometrically, the total orderings of a given finite set may be represented as the vertices of a permutohedron, 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 of a face gives the number of equivalence classes in the corresponding weak ordering. [16] In this geometric representation the partial cube of moves on weak orderings is the graph describing the covering relation of the face lattice 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.
As mentioned above, weak orders have applications in utility theory. [12] In linear programming and other types of combinatorial optimization problem, the prioritization of solutions or of bases is often given by a weak order, determined by a real-valued objective function; 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. [17]
Weak orders have also been used in computer science, in partition refinement based algorithms for lexicographic breadth-first search and lexicographic topological ordering. In these algorithms, a weak ordering on the vertices of a graph (represented as a family of sets that partition the vertices, together with a doubly linked list 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. [18]
In the Standard Library for the C++ 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. [2]
In mathematics, a binary relation associates elements of one set called the domain with elements of another set called the codomain. Precisely, a binary relation over sets and is a set of ordered pairs where is in and is in . It encodes the common concept of relation: an element is related to an element , if and only if the pair belongs to the set of ordered pairs that defines the binary 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. A simpler example is equality. Any number is equal to itself (reflexive). If , then (symmetric). If and , then (transitive).
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσοςisos "equal", and μορφήmorphe "form" or "shape".
In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. The name preorder is meant to suggest that preorders are almost partial orders, but not quite, as they are not necessarily antisymmetric.
In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation on some set , which satisfies the following for all and in :
In mathematics, equality is a relationship between two quantities or, more generally, two mathematical expressions, asserting that the quantities have the same value, or that the expressions represent the same mathematical object. Equality between A and B is written A = B, and pronounced "A equals B". In this equality, A and B are the members of the equality and are distinguished by calling them left-hand side or left member, and right-hand side or right member. Two objects that are not equal are said to be distinct.
In mathematics, a binary relation R on a set X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c.
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but not under subtraction: 1 − 2 is not a natural number, although both 1 and 2 are.
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 introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.
This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:
In set theory, a prewellordering on a set is a preorder on that is strongly connected and well-founded in the sense that the induced relation defined by is a well-founded relation.
In order theory, a branch of mathematics, a linear extension of a partial order is a total order that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order.
In mathematics, a homogeneous relation on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people.
In constructive mathematics, pseudo-order is a name given to certain binary relations appropriate for modeling continuous orderings.
In mathematics, a relation denotes some kind of relationship between two objects in a set, which may or may not hold. As an example, "is less than" is a relation on the set of natural numbers; it holds, for instance, between the values 1 and 3, and likewise between 3 and 4, but not between the values 3 and 1 nor between 4 and 4, that is, 3 < 1 and 4 < 4 both evaluate to false. As another example, "is sister of" is a relation on the set of all people, it holds e.g. between Marie Curie and Bronisława Dłuska, and likewise vice versa. Set members may not be in relation "to a certain degree" – either they are in relation or they are not.
In order theory, the Szpilrajn extension theorem, proved by Edward Szpilrajn in 1930, states that every partial order is contained in a total order. Intuitively, the theorem says that any method of comparing elements that leaves some pairs incomparable can be extended in such a way that every pair becomes comparable. The theorem is one of many examples of the use of the axiom of choice in the form of Zorn's lemma to find a maximal set with certain properties.
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 Duncan Luce 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.
In mathematics, a relation on a set is called connected or complete or total if it relates all distinct pairs of elements of the set in one direction or the other while it is called strongly connected if it relates all pairs of elements. As described in the terminology section below, the terminology for these properties is not uniform. This notion of "total" should not be confused with that of a total relation in the sense that for all there is a so that .
In economics, a utility representation theorem shows that, under certain conditions, a preference ordering can be represented by a real-valued utility function, such that option A is preferred to option B if and only if the utility of A is larger than that of B. The most famous example of a utility representation theorem is the Von Neumann–Morgenstern utility theorem, which shows that any rational agent has a utility function that measures their preferences over lotteries.