 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(December 2015) (Learn how and when to remove this message) |
Order theory is a branch ofmathematics that investigates the intuitive notion of order usingbinary relations. It provides a formal framework for describing statements such as "this isless 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 theorder theory glossary.
Orders are everywhere in mathematics and related fields likecomputer science. The first order often discussed inprimary school is the standard order on thenatural numbers e.g. "2 is less than 3", "10 isgreater than 5", or "Does Tom have fewer cookies than Sally?". This intuitive concept can be extended to orders on other sets ofnumbers, such as theintegers and thereals. The idea of being greater than or less than another number is one of the basic intuitions ofnumber systems (compare withnumeral systems) in general (although one usually is also interested in the actualdifference of two numbers, which is not given by the order). Other familiar examples of orderings are thealphabetical order of words in a dictionary and thegenealogical property oflineal descent within a group of people.
The notion of order is very general, extending beyond contexts that have an immediate, intuitive feel of sequence or relative quantity. In other contexts orders may capture notions of containment or specialization. Abstractly, this type of order amounts to thesubset relation, e.g., "Pediatricians arephysicians," and "Circles are merely special-caseellipses."
Some orders, like "less-than" on the natural numbers and alphabetical order on words, have a special property: each element can becompared to any other element, i.e. it is smaller (earlier) than, larger (later) than, or identical to. However, many other orders do not. Consider for example the subset order on a collection ofsets: though the set of birds and the set of dogs are both subsets of the set of animals, neither the birds nor the dogs constitutes a subset of the other. Those orders like the "subset-of" relation for which there existincomparable elements are calledpartial orders; orders for which every pair of elements is comparable aretotal orders.
Order theory captures the intuition of orders that arises from such examples in a general setting. This is achieved by specifying properties that a relation ≤ must have to be a mathematical order. This more abstract approach makes much sense, because one can derive numerous theorems in the general setting, without focusing on the details of any particular order. These insights can then be readily transferred to many less abstract applications.
Driven by the wide practical usage of orders, numerous special kinds of ordered sets have been defined, some of which have grown into mathematical fields of their own. In addition, order theory does not restrict itself to the various classes of ordering relations, but also considers appropriatefunctions between them. A simple example of an order theoretic property for functions comes fromanalysis wheremonotone functions are frequently found.
This section introduces ordered sets by building upon the concepts ofset theory,arithmetic, andbinary relations.
Orders are special binary relations. Suppose thatP is a set and that ≤ is a relation onP ('relationon a set' is taken to mean 'relationamongst its inhabitants', i.e. ≤ is a subset of the cartesian productP xP). Then ≤ is apartial order if it isreflexive,antisymmetric, andtransitive, that is, if for alla,b andc inP, we have that:
A set with apartial order on it is called apartially ordered set,poset, or justordered set if the intended meaning is clear. By checking these properties, one immediately sees that the well-known orders onnatural numbers,integers,rational numbers andreals are all orders in the above sense. However, these examples have the additional property that any two elements are comparable, that is, for alla andb inP, we have that:
A partial order with this property is called atotal order. These orders can also be calledlinear orders orchains. While many familiar orders are linear, thesubset order on sets provides an example where this is not the case. Another example is given by the divisibility (or "is-a-factor-of") relation |. For two natural numbersn andm, we writen|m ifndividesm without remainder. One easily sees that this yields a partial order. For example neither 3 divides 13 nor 13 divides 3, so 3 and 13 are not comparable elements of the divisibility relation on the set of integers.The identity relation = on any set is also a partial order in which every two distinct elements are incomparable. It is also the only relation that is both a partial order and anequivalence relation because it satisfies both the antisymmetry property of partial orders and thesymmetry property of equivalence relations. Many advanced properties of posets are interesting mainly for non-linear orders.
Hasse diagrams can visually represent the elements and relations of a partial ordering. These aregraph drawings where thevertices are the elements of the poset and the ordering relation is indicated by both theedges and the relative positioning of the vertices. Orders are drawn bottom-up: if an elementx is smaller than (precedes)y then there exists a path fromx toy that is directed upwards. It is often necessary for the edges connecting elements to cross each other, but elements must never be located within an edge. An instructive exercise is to draw the Hasse diagram for the set of natural numbers that are smaller than or equal to 13, ordered by | (thedivides relation).
Even some infinite sets can be diagrammed by superimposing anellipsis (...) on a finite sub-order. This works well for the natural numbers, but it fails for the reals, where there is no immediate successor above 0; however, quite often one can obtain an intuition related to diagrams of a similar kind[vague].
In a partially ordered set there may be some elements that play a special role. The most basic example is given by theleast element of aposet. For example, 1 is theleast element of the positive integers and theempty set is the least set under the subset order. Formally, an elementm is a least element if:
The notation 0 is frequently found for the least element, even when no numbers are concerned. However, in orders on sets of numbers, this notation might be inappropriate or ambiguous, since the number 0 is not always least. An example is given by the above divisibility order |, where 1 is the least element since it divides all other numbers. In contrast, 0 is the number that is divided by all other numbers. Hence it is thegreatest element of the order. Other frequent terms for the least and greatest elements isbottom andtop orzero andunit.
Least andgreatest elements may fail to exist, as the example of the real numbers shows. But if they exist, they are always unique. In contrast, consider the divisibility relation | on the set {2,3,4,5,6}. Although this set has neither top nor bottom, the elements 2, 3, and 5 have no elements below them, while 4, 5 and 6 have none above. Such elements are calledminimal andmaximal, respectively. Formally, an elementm isminimal if:
Exchanging ≤ with ≥ yields the definition ofmaximality. As the example shows, there can be many maximal elements and some elements may be both maximal and minimal (e.g. 5 above). However, if there is a least element, then it is the only minimal element of the order. Again, in infinite posets maximal elements do not always exist - the set of allfinite subsets of a given infinite set, ordered by subset inclusion, provides one of many counterexamples. An important tool to ensure the existence of maximal elements under certain conditions isZorn's Lemma.
Subsets of partially ordered sets inherit the order. We already applied this by considering the subset {2,3,4,5,6} of the natural numbers with the induced divisibility ordering. Now there are also elements of a poset that are special with respect to some subset of the order. This leads to the definition ofupper bounds. Given a subsetS of some posetP, an upper bound ofS is an elementb ofP that is above all elements ofS. Formally, this means that
Lower bounds again are defined by inverting the order. For example, -5 is a lower bound of the natural numbers as a subset of the integers. Given a set of sets, an upper bound for these sets under the subset ordering is given by theirunion. In fact, this upper bound is quite special: it is the smallest set that contains all of the sets. Hence, we have found theleast upper bound of a set of sets. This concept is also calledsupremum orjoin, and for a setS one writes sup(S) or for its least upper bound. Conversely, thegreatest lower bound is known asinfimum ormeet and denoted inf(S) or. These concepts play an important role in many applications of order theory. For two elementsx andy, one also writes and for sup({x,y}) and inf({x,y}), respectively.
For example, 1 is the infimum of the positive integers as a subset of integers.
For another example, consider again the relation | on natural numbers. The least upper bound of two numbers is the smallest number that is divided by both of them, i.e. theleast common multiple of the numbers. Greatest lower bounds in turn are given by thegreatest common divisor.
In the previous definitions, we often noted that a concept can be defined by just inverting the ordering in a former definition. This is the case for "least" and "greatest", for "minimal" and "maximal", for "upper bound" and "lower bound", and so on. This is a general situation in order theory: A given order can be inverted by just exchanging its direction, pictorially flipping the Hasse diagram top-down. This yields the so-calleddual,inverse, oropposite order.
Every order theoretic definition has its dual: it is the notion one obtains by applying the definition to the inverse order. Since all concepts are symmetric, this operation preserves the theorems of partial orders. For a given mathematical result, one can just invert the order and replace all definitions by their duals and one obtains another valid theorem. This is important and useful, since one obtains two theorems for the price of one. Some more details and examples can be found in the article onduality in order theory.
There are many ways to construct orders out of given orders. The dual order is one example. Another important construction is thecartesian product of two partially ordered sets, taken together with theproduct order on pairs of elements. The ordering is defined by (a,x) ≤ (b,y) if (and only if)a ≤b andx ≤y. (Notice carefully that there are three distinct meanings for the relation symbol ≤ in this definition.) Thedisjoint union of two posets is another typical example of order construction, where the order is just the (disjoint) union of the original orders.
Every partial order ≤ gives rise to a so-calledstrict order <, by defininga <b ifa ≤b and notb ≤a. This transformation can be inverted by settinga ≤b ifa <b ora =b. The two concepts are equivalent although in some circumstances one can be more convenient to work with than the other.
It is reasonable to consider functions between partially ordered sets having certain additional properties that are related to the ordering relations of the two sets. The most fundamental condition that occurs in this context ismonotonicity. A functionf from a posetP to a posetQ ismonotone, ororder-preserving, ifa ≤b inP impliesf(a) ≤f(b) inQ (Noting that, strictly, the two relations here are different since they apply to different sets.). The converse of this implication leads to functions that areorder-reflecting, i.e. functionsf as above for whichf(a) ≤f(b) impliesa ≤b. On the other hand, a function may also beorder-reversing orantitone, ifa ≤b impliesf(a) ≥f(b).
Anorder-embedding is a functionf between orders that is both order-preserving and order-reflecting. Examples for these definitions are found easily. For instance, the function that maps a natural number to its successor is clearly monotone with respect to the natural order. Any function from a discrete order, i.e. from a set ordered by the identity order "=", is also monotone. Mapping each natural number to the corresponding real number gives an example for an order embedding. Theset complement on apowerset is an example of an antitone function.
An important question is when two orders are "essentially equal", i.e. when they are the same up to renaming of elements.Order isomorphisms are functions that define such a renaming. An order-isomorphism is a monotonebijective function that has a monotone inverse. This is equivalent to being asurjective order-embedding. Hence, the imagef(P) of an order-embedding is always isomorphic toP, which justifies the term "embedding".
A more elaborate type of functions is given by so-calledGalois connections. Monotone Galois connections can be viewed as a generalization of order-isomorphisms, since they constitute of a pair of two functions in converse directions, which are "not quite" inverse to each other, but that still have close relationships.
Another special type of self-maps on a poset areclosure operators, which are not only monotonic, but alsoidempotent, i.e.f(x) =f(f(x)), andextensive (orinflationary), i.e.x ≤f(x). These have many applications in all kinds of "closures" that appear in mathematics.
Besides being compatible with the mere order relations, functions between posets may also behave well with respect to special elements and constructions. For example, when talking about posets with least element, it may seem reasonable to consider only monotonic functions that preserve this element, i.e. which map least elements to least elements. If binary infima ∧ exist, then a reasonable property might be to require thatf(x ∧y) =f(x) ∧f(y), for allx andy. All of these properties, and indeed many more, may be compiled under the label of limit-preserving functions.
Finally, one can invert the view, switching fromfunctions of orders toorders of functions. Indeed, the functions between two posetsP andQ can be ordered via thepointwise order. For two functionsf andg, we havef ≤g iff(x) ≤g(x) for all elementsx ofP. This occurs for example indomain theory, wherefunction spaces play an important role.
Many of the structures that are studied in order theory employ order relations with further properties. In fact, even some relations that are not partial orders are of special interest. Mainly the concept of apreorder has to be mentioned. A preorder is a relation that is reflexive and transitive, but not necessarily antisymmetric. Each preorder induces anequivalence relation between elements, wherea is equivalent tob, ifa ≤b andb ≤a. Preorders can be turned into orders by identifying all elements that are equivalent with respect to this relation.
Several types of orders can be defined from numerical data on the items of the order: atotal order results from attaching distinct real numbers to each item and using the numerical comparisons to order the items; instead, if distinct items are allowed to have equal numerical scores, one obtains astrict weak ordering. Requiring two scores to be separated by a fixed threshold before they may be compared leads to the concept of asemiorder, while allowing the threshold to vary on a per-item basis produces aninterval order.
An additional simple but useful property leads to so-calledwell-founded, for which all non-empty subsets have a minimal element. Generalizing well-orders from linear to partial orders, a set iswell partially ordered if all its non-empty subsets have a finite number of minimal elements.
Many other types of orders arise when the existence ofinfima andsuprema of certain sets is guaranteed. Focusing on this aspect, usually referred to ascompleteness of orders, one obtains:
However, one can go even further: if all finite non-empty infima exist, then ∧ can be viewed as a total binary operation in the sense ofuniversal algebra. Hence, in a lattice, two operations ∧ and ∨ are available, and one can define new properties by giving identities, such as
This condition is calleddistributivity and gives rise todistributive lattices. There are some other important distributivity laws which are discussed in the article ondistributivity in order theory. Some additional order structures that are often specified via algebraic operations and defining identities are
which both introduce a new operation ~ callednegation. Both structures play a role inmathematical logic and especially Boolean algebras have major applications incomputer science.Finally, various structures in mathematics combine orders with even more algebraic operations, as in the case ofquantales, that allow for the definition of an addition operation.
Many other important properties of posets exist. For example, a poset islocally finite if every closedinterval [a,b] in it isfinite. Locally finite posets give rise toincidence algebras which in turn can be used to define theEuler characteristic of finite bounded posets.
In an ordered set, one can define many types of special subsets based on the given order. A simple example areupper sets; i.e. sets that contain all elements that are above them in the order. Formally, theupper closure of a setS in a posetP is given by the set {x inP | there is somey inS withy ≤x}. A set that is equal to its upper closure is called an upper set.Lower sets are defined dually.
More complicated lower subsets areideals, which have the additional property that each two of their elements have an upper bound within the ideal. Their duals are given byfilters. A related concept is that of adirected subset, which like an ideal contains upper bounds of finite subsets, but does not have to be a lower set. Furthermore, it is often generalized to preordered sets.
A subset which is - as a sub-poset - linearly ordered, is called achain. The opposite notion, theantichain, is a subset that contains no two comparable elements; i.e. that is a discrete order.
Although most mathematical areasuse orders in one or the other way, there are also a few theories that have relationships which go far beyond mere application. Together with their major points of contact with order theory, some of these are to be presented below.
As already mentioned, the methods and formalisms ofuniversal algebra are an important tool for many order theoretic considerations. Beside formalizing orders in terms ofalgebraic structures that satisfy certain identities, one can also establish other connections to algebra. An example is given by the correspondence betweenBoolean algebras andBoolean rings. Other issues are concerned with the existence offree constructions, such asfree lattices based on a given set of generators. Furthermore, closure operators are important in the study of universal algebra.
Intopology, orders play a very prominent role. In fact, the collection ofopen sets provides a classical example of a complete lattice, more precisely a completeHeyting algebra (or "frame" or "locale").Filters andnets are notions closely related to order theory and theclosure operator of sets can be used to define a topology. Beyond these relations, topology can be looked at solely in terms of the open set lattices, which leads to the study ofpointless topology. Furthermore, a natural preorder of elements of the underlying set of a topology is given by the so-calledspecialization order, that is actually a partial order if the topology isT0.
Conversely, in order theory, one often makes use of topological results. There are various ways to define subsets of an order which can be considered as open sets of a topology. Considering topologies on a poset (X, ≤) that in turn induce ≤ as their specialization order, thefinest such topology is theAlexandrov topology, given by taking all upper sets as opens. Conversely, thecoarsest topology that induces the specialization order is theupper topology, having the complements ofprincipal ideals (i.e. sets of the form {y inX |y ≤x} for somex) as asubbase. Additionally, a topology with specialization order ≤ may beorder consistent, meaning that their open sets are "inaccessible by directed suprema" (with respect to ≤). The finest order consistent topology is theScott topology, which is coarser than the Alexandrov topology. A third important topology in this spirit is theLawson topology. There are close connections between these topologies and the concepts of order theory. For example, a function preserves directed suprema if and only if it iscontinuous with respect to the Scott topology (for this reason this order theoretic property is also calledScott-continuity).
The visualization of orders withHasse diagrams has a straightforward generalization: instead of displaying lesser elementsbelow greater ones, the direction of the order can also be depicted by giving directions to the edges of a graph. In this way, each order is seen to be equivalent to adirected acyclic graph, where the nodes are the elements of the poset and there is a directed path froma tob if and only ifa ≤b. Dropping the requirement of being acyclic, one can also obtain all preorders.
When equipped with all transitive edges, these graphs in turn are just specialcategories, where elements are objects and each set of morphisms between two elements is at most singleton. Functions between orders become functors between categories. Many ideas of order theory are just concepts of category theory in small. For example, an infimum is just acategorical product. More generally, one can capture infima and suprema under the abstract notion of acategorical limit (orcolimit, respectively). Another place where categorical ideas occur is the concept of a (monotone)Galois connection, which is just the same as a pair ofadjoint functors.
But category theory also has its impact on order theory on a larger scale. Classes of posets with appropriate functions as discussed above form interesting categories. Often one can also state constructions of orders, like theproduct order, in terms of categories. Further insights result when categories of orders are foundcategorically equivalent to other categories, for example of topological spaces. This line of research leads to variousrepresentation theorems, often collected under the label ofStone duality.
As explained before, orders are ubiquitous in mathematics. However, the earliest explicit mentionings of partial orders are probably to be found not before the 19th century. In this context the works ofGeorge Boole are of great importance. Moreover, works ofCharles Sanders Peirce,Richard Dedekind, andErnst Schröder also consider concepts of order theory.
Contributors toordered geometry were listed in a 1961textbook:
It wasPasch in 1882, who first pointed out that a geometry of order could be developed without reference to measurement. His system of axioms was gradually improved byPeano (1889),Hilbert (1899), andVeblen (1904).
— H. S. M. Coxeter, Introduction to Geometry
In 1901Bertrand Russell wrote "On the Notion of Order"[2] exploring the foundations of the idea through generation ofseries. He returned to the topic in part IV ofThe Principles of Mathematics (1903). Russell noted thatbinary relationaRb has a sense proceeding froma tob with theconverse relation having an opposite sense, and sense "is the source of order and series." (p 95) He acknowledgesImmanuel Kant[3] was "aware of the difference between logical opposition and the opposition of positive and negative". He wrote that Kant deserves credit as he "first called attention to the logical importance of asymmetric relations."
The termposet as an abbreviation for partially ordered set is attributed toGarrett Birkhoff in the second edition of his influential bookLattice Theory.[4][5]
