Order theory

Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of mathematical order. This article provides a detailed introduction to this field and includes some of the basic definitions. For a quick lookup of an order-theoretical term, there is also an order-theory glossary. A list of issues on order collects the articles that exist in relation to this theory of order.

Background and Motivation

Order appears everywhere - at least, when it comes to mathematics and related areas such as computer science. The first order that one typically encounters in elementary school mathematics education is the ≤ order of the natural numbers. This intuitive concept is easily extended to other sets of numbers, such as integers and reals. In fact the idea of being greater or less than another number is one of the basic intuitions of number systems in general (that one is generally also interested in the real difference of two numbers, which is not given by the order). Another popular example of an order is the lexicographical order of words in a dictionary.

The above types of order have a special property: each element can be compared to any other element, ie it is either greater, or less, or equal. However, this is not always a desirable requirement. A well-known example is the order of the subsets of a set. If a set contains the elements of a certain other set, then it can be said to be greater than or equal to. However, there are sets that may not be comparable in this way, since each may contain some element that is not present in the other. Therefore, subset inclusion is a partial order, compared to the total orders given above.

Encouraged by the wide practical uses of orders, numerous special classes of ordered sets can be defined, some of which have become mathematical fields of their own. Furthermore, order theory is not restricted to the various kinds of order relations, but also considers appropriate functions between them. A simple example of an order-theoretical property comes from analysis where we frequently encounter monotonic functions.

Introduction to basic definitions

This section aims to give a first guide to the realm of ordered sets. It is intended for the reader who has a basic understanding of set theory and arithmetic and who knows what a binary relation is, but who is not familiar, as yet, with order-theoretical considerations.

Partially ordered sets

As already alluded to above, an order is a special binary relation. Therefore let us consider some set P and a binary relation ≤ on P. Then ≤ is a partial order if it is reflexive, antisymmetric, and transitive, that is, for all a, b and c in P, we have:

a ≤ a (reflexivity)

Yeah. a ≤ b and b ≤ c then. a ≤ c (transitivity)

Yeah. a ≤ b and b ≤ a then. a = b(antisymmetry).

A set with a partial order is called a partially ordered set, or poset for short partially ordered set). The term ordered set is sometimes used for posets as well, as long as it is clear from the context that no other class of commands is meant. Checking this property, it is immediately seen that the well-known orders of naturals, integers, rationals, and reals are all orders in the above sense. However, they have the additional property of being total, that is, for all a, b in X

a ≤ b or b ≤ a (totality)

This order can also be called a linear order or string. while many classical orders are linear, the order between subsets of a set provides an example where this is not the case. In fact, many advanced properties of posets are interesting primarily for nonlinear ordering.

Viewing orders

Before proceeding with more examples and definitions, it will be helpful to be able to display an order in a convenient graphical way, to provide a "picture" that one may have in mind (or on paper) when trying to access more abstract concepts. For this purpose, so-called Hasse diagrams have been introduced. These are graphs where the vertices are the elements of the poset and the ordering relationship is indicated by the edges and the relative position of the vertices. Orders are drawn from bottom to top: if an element x is less than y then there is a path from x to y which is directed upwards. It is often necessary for the connection between points to intersect, but points should never be placed in direct connection between two other points.

Even infinite sets can sometimes be illustrated by similar diagrams, using an ellipsis (...) after drawing a sufficiently instructive finite suborder. This works well for natural numbers, but fails for real numbers, where there is no immediate successor. However, insights related to diagrams of this type are often gained.

All of the above orders are very common in mathematics, however there are also examples that one does not often consider as orders. For example, the identity relationship "=" in a set is a partial order. Within this order, any two (i.e. distinct) elements are incomparable. It is also the only relation that is both a partial order and an equivalence relation. The Hasse diagram of such a discrete order is just a collection of labeled points, with no edges between them.

Another example is given by the divisibility relation "|". For two natural numbers n and m, we write n|m if n divides a m with no remainder. One easily sees that this really gives a partial order. An instructive exercise is to draw the Hasse diagram for the set of natural numbers that are less than or equal to, say, 13, ordered by |.

Special elements within an order

In a partially ordered set there are some elements that play a special role. The most basic example is given by the minimum of a poset. For example, 1 is the minimum of the natural numbers and the empty set is the minimum under the order of subsets. Formally, this can be described by the property:

0 ≤ afor every element a of the ordered set.

It is common to find the notation 0 for the minimum, even when it does not refer to numbers. However, in an order of a numeric set, this notation may be inappropriate or ambiguous, since the number 0 is not always the minimum. An example is the above divisibility order |, where 1 is the minimum since it divides all other numbers. On the other hand, 0 is a number that is divided by all the other numbers. Therefore it is the maximum of the order! Other common terms for these elements are bottom and top or zero and one. The "minimum" or "maximum", as the example of the real numbers demonstrates. On the other hand, if they exist they are always unique. In contrast, consider the divisibility relation | in the set {2, 3, 4, 5, 6}. Although this set has neither a top nor a bottom, elements 2, 3, and 5 do not have any elements below them, while 4, 5, and 6 do not have any other numbers above them. Such elements are called minimals and maximals, respectively. Formally, an m element is minimal if:

a ≤ m implies a = mfor every element a.

Exchanging ≤ with ≥ we get the definition of maximal. As the example demonstrates, there can be many minimal or maximal elements and some element can be both maximal and minimal (e.g. 5 above). However, if there is a minimal element, then it is the only minimal element of the order. (If the given definition is strictly followed. Unfortunately there is a mathematical tradition "on the contrary": consider the minimales and maximals in the set stripped of its maximum and its minimum, if any This must be remembered. N.T.). Again, in posets there are not always infinitely many maximal elements - the set of all finite subsets in 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 a partially ordered set inherit the order. We already applied this when considering the subset {2, 3, 4, 5, 6} of the natural numbers with the order of divisibility induced. 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 bound. Given a subset S of a certain poset P, an upper bound of S is an element b of P which is above every S element. Formally, this means that

s ≤ bFor everything s in S.

Lower bound is defined by reversing the order. For example, -5 is a lower bound on the natural numbers as a subset of the integers. Given a set of sets, an upper bound for these sets is given by their union. In fact, this upper bound is very special: it is the smallest set that contains all the given sets. Therefore, we find the smallest upper bound of a set of sets. This concept is also called supreme and for a set S we write sup S or VS for its lowest bound superior. Conversely, the lower largest bound is known as the intimate and is denoted inf S or ^S. This concept plays an important role in many uses of order theory. For two elements x and y, one also writes x v y y x ^ y for sup{x, y} and inf{x, y }, respectively.

Using Wikipedia TeX markup, one can also write ${displaystyle vee }$ and ${displaystyle wedge }$as well as big symbols ${displaystyle bigvee }$ and ${displaystyle bigwedge }$. Note, however, that all such symbols may not have a symbol of size corresponding to the source of the standard text and therefore prefer to use them on additional lines. Many of today's browsers are unable to represent. for v and ∧ for ^ on some platforms, and therefore it is avoided here.

Consider another example in the relation | for the natural numbers. The least upper bound of two numbers is the least number that is a multiple of both, that is, the least common multiple. Greatest lower bound is alternatively the greatest common divisor.

Duality

In previous definitions, we often see that a concept can be defined by simply reversing the order in a previous definition. This is the case for "minor" and "major", for "minimum" and "maximum", for "upper bound " and "lower bound", and so on. This is a general situation in order theory: A given order can be reversed simply by swapping its direction, pictorially turning the Hasse diagram upside down. This gives the so-called order dual, reverse or opposite.

Each theoretical order definition has its dual: it is the notion that is obtained by applying the definition to the reverse order. Given the symmetry of all concepts, this operation preserves the partial order theorems. For a given mathematical result, one can simply reverse the order and substitute its dual for all definitions and obtain another valid theorem. This is important and useful, since one gets two theorems for the price of one. More detail and examples can be found in the article on duality in order theory.

Building new orders

There are many ways to build commands or combine commands into a new one. The dual order is a prime example. Another important construction is the Cartesian product of two partially ordered sets, together with the product order on pairs of elements. This is defined by the original commands making (a, x) ≤ (b, y) if a ≤ b and x ≤ y. The disjoint union of two partially ordered sets is another typical construction, where the order is exactly the union of the original orders.

As in the case of the usual order of numbers, each partial order ≤ gives rise to a strict order <, by defining a < b if a ≤ b and not b ≤ a. This transformation can be reversed by making a ≤ b if a < b or a = b.

Functions between commands

It is reasonable to require that functions between partially ordered sets have certain additional properties, which are related to the ordering relation of the two sets. The most fundamental condition that arises in this context is monotony. A function f from a poset P to a poset Q is monotone or preserving order, if a ≤ b in P implies f(a) ≤ f(b) in Q. The converse of this implication leads to a function that is reflective order, that is, a function f as above for which f( a) ≤ f(b) implies a ≤ b. On the other hand, a function can also be inverting order or antitone, if a ≤ b implies f(a) ≥ f(b).

An order immersion is a function f between orders that is order-preserving and order-reflecting. Examples for this definition are easily found. For example, a function that maps a natural number to its successor is clearly monotonic with respect to the natural order. Any function of a discrete order, that is, a set ordered by the identity order "=", is also monotonic. Mapping each natural number to the corresponding real number gives an example for an order immersion. The set complement in a set of parts is an example of an antitone function.

An important question is when two commands are "essentially the same," that is, when they are the same except for renaming elements. An order isomorphism is a function that defines such a renaming. An order isomorphism is a bijective monotone function that has a monotone inverse. This is equivalent to a surjective order immersion. Therefore, the image f(P) of an order immersion is always isomorphic to P, which justifies the term "immersion".

A more elaborate type of function is the so-called Galois connection. Monotonic Galois connections can be seen as a generalization of order isomorphisms, since they are constituted by two functions in inverse direction, which are not absolute inverses of each other, but are closely related.

Another special type of endofunction in a poset is the closure operator, which is not only monotonic, but also idempotent, ie. f(x) = f(f(x)), and < b>extensive, ie. x ≤ f(x). this has a lot of use in all kinds of "closures" that appear in mathematics.

In addition to supporting the mere ordering relation, a function between posets can also behave well with respect to special elements and constructs. For example, when talking about posets with least element, it seems reasonable to consider only a monotonic function that preserves this element, that is, that maps least element to least element. If the infinitesimal binary ^ exists, then a reasonable property may be to require that f(x^y) = f(x) ^ f(y), for all x and y. All of these properties, and in fact many more, can be grouped under the label limit-preserving function.

Finally, one can reverse the view, change order functions to order functions. In fact, the functions between two posets P and Q can be ordered via point-to-point ordering. For two functions f and g, we have f ≤ g if f(x) ≤ g(x) for every element x in P. This will happen for example in domain theory, where functional spaces play an important role.

Special Order Types

Many of the structures that are studied in order theory employ relations with additional properties. In fact, some relations that are not of partial order are of special interest. Mainly, the concept of preorder has to be mentioned. A preorder is a relation that is reflexive and transitive, but not necessarily antisymmetric. Each preorder induces an equivalence relation between elements, where a is equivalent to b, if a ≤ b and a ≥ b. Preorders can be converted to orders by identifying any equivalent elements with respect to this relationship.

Basic types of special orders have already been given in the form of a total order. A simple but useful additional property leads to the so-called good ordering, within which every non-empty subset has a least element (also called the first element). Many other types of order appear when the existence of infimal and supreme of certain sets is guaranteed. Focusing on this aspect, generally referred to as order completeness, one obtains:

• Posets tied, i.e. posets with lesser and greater elements (which are precisely supreme and tiny of the empty set),

• reticulates, in which every finite set is not empty has supreme and infimous,

• full reticulates, where each set has supreme and tiny, and

• Completely directed partial orders (dcpos), which guarantee the existence of supreme in every directed subset and are studied in domain theory.

However, one can go even further: if every non-empty finite infima exists, then ^ can be seen as a total binary operation in the sense of universal algebra. Thus, in a lattice, two operations ^ and v are available, and new properties can be defined by giving identities, such as

x ^ (and v z) = (x ^ andv (x ^ zFor everything x, andand z.

This condition is called distributivity and gives rise to the distributive lattices. There are some other important laws of distributivity that are discussed in the article on distributivity in order theories. Some additional order structures that are often specified via algebraic operation and by defining identities are

• Heyting algebras and

• Boole algebras,

in which they both introduce a new ~ operation called negate. Both structures play a role in mathematical logic and especially Boolean algebras have important use in computing. Finally, several structures in mathematics combine order with even more algebraic operations, such as the case of quantals, which allows the definition of an addition operation.

There are many other important properties of posets. For example, a poset is locally finite if every closed interval [a, b] in it is finite. Locally finite posets give rise to incidence algebras which in turn can be used to define the Euler characteristic of bounded finite posets.

Subsets of ordered sets

In an ordered set, one can define many special types of subsets based on the given order. A simple example is the top arrays, ie arrays that contain every element above them in the order. Formally, the upper closure of a set S in a poset P is given by the set {x in P | there is some y in S with y ≤ x}. A set that is equal to its superior closure is called a superior set. lower set is dually defined.

More complicated lower subsets are ideals, which have the additional property that each two of their elements have an upper bound within the ideal. His dual notion is filters. A related concept is that of a directed subset, which as an ideal contains an upper bound of a finite subset, but does not have to be a lower set. Also, it is often generalized to preordered sets.

A subset that is - like sub-poset - linearly ordered, is called a string. The opposite notion, antichain, is a subset that does not contain any pair of comparable elements, that is, it is a discrete order.

Related Mathematical Areas

Although most areas of mathematics use order in one way or another, there are also some theories that have a relationship that goes far beyond mere utilization. Along with their important point of contact with order theory, some will be presented below.

Universal Algebra

As already mentioned, the methods and formalism of universal algebra are an important tool for many order-theoretical considerations. Apart from formalizing orders in terms of algebraic structures that satisfy certain identities, other connections with algebra can also be established. An example is the correspondence between Boolean algebras and Boolean rings. Other aspects have to do with the existence of free constructions, such as free lattices based on a set of generators. Furthermore, the closure operators are important in the study of universal algebra.

Topology

In topology order plays a very prominent role. In fact, the set of open ones provides a classic example of a complete lattice, more exactly a complete Heyting algebra (or "framework" or " locale"). Filters and networks are notions related to order theory and the set closure operator can be used to define a topology. Beyond this relationship, topology can be viewed solely in terms of the lattice of open sets, which leads to the study of pointless topology. Furthermore, a natural preorder of elements of the underlying set of a topology is given by the so-called specialization order, which is really a partial order if the topology is T0.

Conversely, in order theory, one often makes use of topological results. There are several ways to define subsets of an order that can be considered as open sets of a topology. Especially, it is interesting to consider topologies on a poset (X, ≤) that returns ≤ as its specialization order. The finest of such topologies is the Alexandrov topology, given by taking all "upper" sets as open. Conversely, the thicker topology that induces the order of specialization is the upper topology, which has the complements of principal ideals (i.e. sets of the form { y in X|y ≤ x} for each x) as a subbase. Additionally, a topology with specialization order ≤ can be order consistent, meaning that its open sets are "inaccessible by directed supremum" (with respect ≤). The thinnest topology of a consistent order is the Scott topology, which is coarser than the Alexandrov topology. A third important topology along these lines is the Lawson topology. There are close connections between these topologies and the concepts of order theory. For example, a function preserves directed supra if and only if it is continuous with respect to the Scott topology (for this reason this order-theoretical property is also called Scott continuity).

Category Theory

The visualization of orders with Hasse diagrams has a direct generalization: instead of displaying smaller elements under the larger ones, the direction of the order can also be represented by giving the direction of the edges of the graph. In this way, each order is seen as equivalent to an acyclic directed graph, where the nodes are the elements of the poset and there is a directed path from a to b if and only if a ≤ b. By removing the acyclic requirement, one can also get all preorders.

When equipped with all transitive edges, these graphs are only special categories, where the elements are the objects and each set of maps between two elements is at most a singleton. Functions between orders become functors between categories. Interestingly, many order-theoretic ideas are simply small versions of category-theoretic concepts. For example, an infimal is precisely a categorical product. More generally, one can subsume suprema and infima under the abstract notion of a categorical limit (or colimit, respectively). Another place where categorical ideas arise is the concept of a (monotonic) Galois connection, which is precisely equal to a pair of adjoint functors.

But category theory also has an impact on larger-scale order theory. Classes of posets with appropriate functions as discussed above form interesting categories. Often one can also set construction orders, such as product order, in terms of category. Other intuitions result when categories of order are categorically equivalent to another category, for example of topological spaces. This line of research leads to several representation theorems, often collected under the label Stone's duality.

Outline of related topics

• Algebra of incidence
• Möbius function