Order theory

The notion of order is very general, extending beyond contexts that have an immediate, intuitive feel of sequence or relative quantity.

Abstractly, this type of order amounts to the subset relation, e.g., "Pediatricians are physicians," and "Circles are merely special-case ellipses."

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.

The identity relation = on any set is also a partial order in which every two distinct elements are incomparable.

Hasse diagrams can visually represent the elements and relations of a partial ordering.

Orders are drawn bottom-up: if an element x is smaller than (precedes) y then there exists a path from x to y that is directed upwards.

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 | (the divides relation).

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].

An important tool to ensure the existence of maximal elements under certain conditions is Zorn's Lemma.

We already applied this by considering the subset {2,3,4,5,6} of the natural numbers with the induced divisibility ordering.

For a given mathematical result, one can just invert the order and replace all definitions by their duals and one obtains another valid theorem.

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 are closure operators, which are not only monotonic, but also idempotent, i.e. f(x) = f(f(x)), and extensive (or inflationary), i.e. x ≤ f(x).

Besides being compatible with the mere order relations, functions between posets may also behave well with respect to special elements and constructions.

An additional simple but useful property leads to so-called well-founded, for which all non-empty subsets have a minimal element.

Focusing on this aspect, usually referred to as completeness 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 of universal algebra.

Both structures play a role in mathematical logic and especially Boolean algebras have major applications in computer science.

The opposite notion, the antichain, is a subset that contains no two comparable elements; i.e. that is a discrete order.

Although most mathematical areas use orders in one or the other way, there are also a few theories that have relationships which go far beyond mere application.

As already mentioned, the methods and formalisms of universal algebra are an important tool for many order theoretic considerations.

Filters and nets are notions closely related to order theory and the closure operator of sets can be used to define a topology.

There are various ways to define subsets of an order which can be considered as open sets of a topology.

For example, a function preserves directed suprema if and only if it is continuous with respect to the Scott topology (for this reason this order theoretic property is also called Scott-continuity).

More generally, one can capture infima and suprema under the abstract notion of a categorical limit (or colimit, respectively).

Another place where categorical ideas occur is the concept of a (monotone) Galois connection, which is just the same as a pair of adjoint functors.

This line of research leads to various representation theorems, often collected under the label of Stone duality.

Moreover, works of Charles Sanders Peirce, Richard Dedekind, and Ernst Schröder also consider concepts of order theory.

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"[2] exploring the foundations of the idea through generation of series.

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.