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 (although one usually is also interested in the actual difference of two numbers, which is not given by the order). 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 (earlier) than, larger (later) 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.
History The earliest explicit mentionings of partial orders are probably to be found not before the 19th century. In this context the works of George Boole are of great importance. Moreover, works of Charles Sanders Peirce, Richard Dedekind, and Ernst Schröder also consider concepts of order theory. Contributors to ordered geometry were listed in a 1961 textbook:
It was Pasch 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 by Peano (1889), Hilbert (1899), and Veblen (1904). In 1901 Bertrand Russell wrote "On the Notion of Order" exploring the foundations of the idea through generation of series. He returned to the topic in part IV of The Principles of Mathematics (1903). Russell noted that binary relation aRb has a sense proceeding from a to b with the converse relation having an opposite sense, and sense "is the source of order and series." (p 95) He acknowledges Immanuel Kant 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 term poset as an abbreviation for partially ordered set is attributed to Garrett Birkhoff in the second edition of his influential book Lattice Theory.
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 ('relation on a set' is taken to mean 'relation amongst its inhabitants', i.e. ≤ is a subset of the cartesian product P × 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 ≤ a (reflexivity) if a ≤ b and b ≤ a then a = b (antisymmetry) if a ≤ b and b ≤ c then a ≤ c (transitivity). 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 ≤ b or b ≤ a. 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 (or "is-a-factor-of") 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
… excerpt ends here. Continue reading the full article.
