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".
Background and motivation
Orders are everywhere in mathematics and related fields like computer science. The first order often discussed in primary school is the standard order on the natural numbers e.g. "2 is less than 3", "10 is greater than 5", or "Does Tom have fewer cookies than Sally?". This intuitive concept can be extended to orders on other sets of numbers, such as the integers and the reals. The idea of being greater than or less than another number is one of the basic intuitions of number systems in general. Other familiar examples of orderings are the alphabetical order of words in a dictionary and the genealogical property of lineal 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 the subset relation, e.g., "Pediatricians are physicians," and "Circles are merely special-case ellipses."
Some orders, like "less-than" on the natural numbers and alphabetical order on words, have a special property: each element can be compared to any other element, i.e. it is smaller than, larger than, or identical to. However, many other orders do not. Consider for example the subset order on a collection of sets: 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 which allow incomparable elements are called partial orders; orders for which every pair of elements is comparable are total 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 appropriate functions between them. A simple example of an order theoretic property for functions comes from analysis where monotone functions are frequently found.
Basic definitions
This section introduces ordered sets by building upon the concepts of set theory, arithmetic, and binary relations.Partially ordered sets
Orders are special binary relations. Suppose that P is a set and that ≤ is a relation on P. Then ≤ is a partial order if it is reflexive, antisymmetric, and transitive, that is, if for all a, b and c in P, we have that:A set with a partial order on it is called a partially ordered set, poset, or just ordered set if the intended meaning is clear. By checking these properties, one immediately sees that the well-known orders on natural numbers, integers, rational numbers and reals are all orders in the above sense. However, these examples have the additional property that any two elements are comparable, that is, for all a and b in P, we have that:
A partial order with this property is called a total order. These orders can also be called linear orders or chains. While many familiar orders are linear, the subset order on sets provides an example where this is not the case. Another example is given by the divisibility relation |. For two natural numbers n and m, we write n|''m if n'' divides m 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 an equivalence relation because it satisfies both the antisymmetry property of partial orders and the symmetry property of equivalence relations. Many advanced properties of posets are interesting mainly for non-linear orders.
Visualizing a poset
s can visually represent the elements and relations of a partial ordering. These are graph drawings where the vertices are the elements of the poset and the ordering relation is indicated by both the edges and the relative positioning of the vertices. Orders are drawn bottom-up: if an element x is smaller than y then there exists a path from x to y 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 |.Even some infinite sets can be diagrammed by superimposing an ellipsis 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.
Special elements within an order
In a partially ordered set there may be some elements that play a special role. The most basic example is given by the least element of a poset. For example, 1 is the least element of the positive integers and the empty set is the least set under the subset order. Formally, an element m 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 the greatest element of the order. Other frequent terms for the least and greatest elements is bottom and top or zero and unit.
Least and greatest 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. 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 called minimal and maximal, respectively. Formally, an element m is minimal if:
Exchanging ≤ with ≥ yields the definition of maximality. As the example shows, there can be many maximal elements and some elements may be both maximal and minimal. 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 all finite 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 is Zorn's Lemma.
Subsets of partially ordered sets inherit the order. We already applied this by considering the subset 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 of upper bounds. Given a subset S of some poset P, an upper bound of S is an element b of P that is above all elements of S. 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 their union. In fact, this upper bound is quite special: it is the smallest set that contains all of the sets. Hence, we have found the least upper bound of a set of sets. This concept is also called supremum or join, and for a set S one writes sup or for its least upper bound. Conversely, the greatest lower bound is known as infimum or meet and denoted inf or. These concepts play an important role in many applications of order theory. For two elements x and y, one also writes and for sup and inf, 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. the least common multiple of the numbers. Greatest lower bounds in turn are given by the greatest common divisor.
Duality
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-called dual, inverse, or opposite 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 on duality in order theory.