# Dictionary Definition

ordering

### Noun

1 logical or comprehensible arrangement of
separate elements; "we shall consider these questions in the
inverse order of their presentation" [syn: order, ordination]

2 putting in order; "there were mistakes in the
ordering of items on the list" [syn: order]

# User Contributed Dictionary

## English

### Verb

ordering- present participle of order

### Noun

- Arrangement in a sequence.
- ''She gave the students' performances a rank ordering.

- Making an agreement for later pick up or delivery.
- Ordering has to be complete at least six weeks before expected delivery to get our best prices.

# Extensive Definition

Order theory is a branch of mathematics that studies
various kinds of binary
relations that capture the intuitive notion of ordering,
providing a framework for saying when one thing is "less than"
another. This article gives a detailed introduction to the field
and includes some of the most basic definitions. For a quick lookup
of order-theoretic terms, there is also an order
theory glossary. A list
of order topics collects the various articles in the vicinity
of order theory.

## Background and motivation

Orders appear everywhere - at least as far as mathematics and related areas, such as computer science, are concerned. The first order that one typically meets in primary school mathematical education is the order ≤ of natural numbers. This intuitive concept is easily extended to orderings of other sets of numbers, such as the integers and the reals. Indeed the idea of being greater or smaller 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). Another familiar example of an ordering is the lexicographic order of words in a dictionary.The above types of orders have a special
property: each element can be compared to any other element, i.e.
it is greater, smaller, or equal. However, this is not always a
desired requirement. For example, consider the subset ordering of sets. If a set A contains all the
elements of a set B, then B is said to be smaller than or equal to
A. Yet there are some sets that cannot be related in this fashion.
Whenever both contain some elements that are not in the other, the
two sets are not related by subset-inclusion. Hence,
subset-inclusion is only a partial
order, as opposed to the total orders
given before.

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
concrete applications.

Driven by the wide practical usage of orders,
numerous special kinds of ordered sets have been defined, some of
which have grown to 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 found frequently.

## 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, i.e., 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
an 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, they have the additional
property of being total, i.e.,
for all a and b in P, we have that:

- a ≤ b or b ≤ a (totality)

These orders can also be called linear orders or
chains. While many classical 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. The identity relation = on any set is also a partial order
in which every two elements are incomparable. It is also the only
relation that is both a partial order and an equivalence
relation. Many advanced properties of posets are mainly
interesting for non-linear orders.

### Visualizing a poset

Hasse diagrams 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 (precedes) 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 | (the divides relation).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:- m ≤ a, for all elements a of the order.

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. On the other hand, 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.

On the other hand, if they exist, least and
greatest elements 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 do not have any elements
below them, while 4, 5, and 6 have no other number above. Such
elements are called minimal and maximal, respectively. Formally, an
element m is minimal
if:

- a ≤ m implies a = m, for all elements a of the order.

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 (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 all finite subsets of a given infinite set,
ordered by subset inclusion, provides one out 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

- s ≤ b, for all s in S.

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(S) or vS for its
least upper bound. Conversely, the greatest
lower bound is known as infimum or meet and denoted
inf(S) or ^S. These concepts play an important role in many
applications of order theory. For two elements x and y, one also
writes x v y and x ^ y for
sup() and inf(), respectively. (Using Wikipedia's
TeX markup, one can also write \vee and \wedge, as well as the
larger symbols \bigvee and \bigwedge. Note however, that all of
these symbols may fail to match the font size of the standard text
and should therefore preferably be used in extra lines. The
rendering of ∨ for v and ∧ for ^ is not supported by many of
today's web browsers
across all platforms and therefore avoided here.)

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 the symmetry of all concepts, 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.

### Constructing new orders

There are many ways to construct orders out of given orders. The dual order is one example. Another important construction is the cartesian product of two partially ordered sets, taken together with the product order on pairs of elements. The ordering is defined by (a, x) ≤ (b, y) if (and only if) a ≤ b and x ≤ y. (Notice carefully that there are three distinct meanings for the relation symbol ≤ in this definition.) The disjoint 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-called
strict
order <, by defining a < b if a ≤ b and not b ≤ a. This
transformation can be inverted by setting a ≤ b if a < b or a =
b. The two concepts are equivalent although in some circumstances
one can be more convenient to work with than the other.

## Functions between orders

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 is monotonicity. A function f from a poset P to a poset Q is monotone, or order-preserving, if a ≤ b in P implies f(a) ≤ f(b) in Q (Noting that, strictly, the two relations here are different since they apply to different sets.). The converse of this implication leads to functions that are order-reflecting, i.e. functions f as above for which f(a) ≤ f(b) implies a ≤ b. On the other hand, a function may also be order-reversing or antitone, if a ≤ b implies f(b) ≤ f(a).An order-embedding
is a function f 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. The set
complement on a powerset 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 monotone bijective function that has a
monotone inverse. This is equivalent to being a surjective order-embedding.
Hence, the image f(P) of an order-embedding is always isomorphic to
P, which justifies the term "embedding".

A more elaborate type of functions is given by
so-called Galois
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 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). 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 that f(x^y) =
f(x)^f(y), for all x and y. 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 from
functions of orders to orders of functions. Indeed, the functions
between two posets P and Q can be ordered via the pointwise
order. For two functions f and g, we have f ≤ g if f(x) ≤ g(x)
for all elements x of P. This occurs for example in domain
theory, where function
spaces play an important role.

## Special types of orders

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 a 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 b ≤ a. Preorders can be turned into orders by identifying all elements that are equivalent with respect to this relation.Basic types of special orders have already been
given in form of total orders. An additional simple but useful
property leads to so-called well-orders, for
which all non-empty subsets have a minimal element. Generalizing
well-orders from linear to partial orders, a set is well
partially ordered if all its non-empty subsets have a finite
number of minimal elements.

Many other types of orders arise when the
existence of infima and
suprema of certain sets
is guaranteed. Focusing on this aspect, usually referred to as
completeness of orders, one obtains:

- Bounded posets, i.e. posets with a least and greatest element (which are just the supremum and infimum of the empty subset),
- Lattices, in which every non-empty finite set has a supremum and infimum,
- Complete lattices, where every set has a supremum and infimum, and
- Directed complete partial orders (dcpos), that guarantee the existence of suprema of all directed subsets and that are studied in domain theory.

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. Hence, in a lattice, two operations ^ and v are
available, and one can define new properties by giving identities,
such as

- x ^ (y v z) = (x ^ y) v (x ^ z), for all x, y, and z.

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

- Heyting algebras and
- Boolean algebras,

which both introduce a new operation ~ called
negation. Both structures play a role in mathematical
logic and especially Boolean algebras have major applications
in computer
science. Finally, various structures in mathematics combine
orders with even more algebraic operations, as in the case of
quantales, that allow
for the definition of an addition operation.

Many other important properties of posets exist.
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 finite bounded posets.

## Subsets of ordered sets

In an ordered set, one can define many types of special subsets based on the given order. A simple example are upper sets; i.e. sets that contain all elements that are above them in the order. Formally, the upper closure of a set S in a poset P is given by the set . A set that is equal to its upper closure is called an upper set. Lower sets are defined dually.More complicated lower subsets are ideals,
which have the additional property that each two of their elements
have an upper bound within the ideal. Their duals are given by
filters.
A related concept is that of a directed
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 a chain. The opposite notion, the antichain, is
a subset that contains no two comparable elements; i.e. that is a
discrete order.

## Related mathematical areas

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. Together with their major touching points with order theory, some of these are to be presented below.### Universal algebra

As already mentioned, the methods and formalisms of universal algebra are an important tool for many order theoretic considerations. Beside formalizing orders in terms of algebraic structures that satisfy certain identities, one can also establish other connections to algebra. An example is given by the correspondence between Boolean algebras and Boolean rings. Other issues are concerned with the existence of free constructions, such as free lattices based on a given set of generators. Furthermore, closure operators are important in the study of universal algebra.### Topology

In topology orders play a very prominent role. In fact, the set of open sets provides a classical example of a complete lattice, more precisely a complete Heyting algebra (or "frame" or "locale"). Filters and nets are notions closely related to order theory and the closure operator of sets can be used to define topology. Beyond these relations, topology can be looked at solely in terms of the open set lattices, 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, that is actually a partial order if the topology is T0.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.
Especially, it is interesting to consider topologies on a poset (X,
≤) that in turn induce ≤ as their specialization order. The finest
such topology is the Alexandrov
topology, given by taking all upper sets as opens. Conversely,
the coarsest topology that induces the specialization order is the
upper
topology, having the complements of principal
ideals (i.e. sets of the form for some x) as a subbase. Additionally, a
topology with specialization order ≤ may be order
consistent, meaning that their open sets are "inaccessible by
directed suprema" (with respect to ≤). The finest order consistent
topology is the Scott
topology, which is coarser than the Alexandrov topology. A
third important topology in this spirit is the Lawson
topology. There are close connections between these topologies
and the concepts of order theory. For example, a function preserves
directed suprema iff it is
continuous with respect to the Scott topology (for this reason
this order theoretic property is also called Scott-continuity).

### Category theory

The visualization of orders with Hasse diagrams has a straightforward generalization: instead of displaying lesser elements below 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 a directed acyclic 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. Dropping the requirement of being acyclic, one can also obtain all preorders.When equipped with all transitive edges, these
graphs in turn are just special categories,
where elements are objects and each set of morphisms between two
elements is at most singleton. Functions between orders become
functors between categories. Interestingly, many ideas of order
theory are just concepts of category theory in small. For example,
an infimum is just a categorical
product. More generally, one can capture suprema and infima
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.

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 the product
order, in terms of categories. Further insights result when
categories of orders are found categorically
equivalent to other categories, for example of topological
spaces. This line of research leads to various representation
theorems, often collected under the label of Stone
duality.

## History

As explained before, orders are ubiquitous in mathematics. However, 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 S. Peirce, Richard Dedekind, and Ernst Schröder also consider concepts of order theory. Certainly, there are others to be named in this context and surely there exists more detailed material on the history of order theory. Please contribute if any further knowledge is available to you.The term poset as an abbreviation for partially
ordered set was coined by Garrett
Birkhoff in the second edition of his influential book Lattice
Theory.

## See also

## Notes

## References

- Lattice Theory, volume 25
- Introduction to Lattices and Order

- A good contemporary introduction to the subject. Suitable for undergraduates.

- G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott (2003). "Continuous Lattices and Domains," in Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press. ISBN 0-521-80338-1

- The comprehensive new version of the famous "Compendium" of continuous lattices. Assumes some advanced mathematical background.

## External links

- Orders at ProvenMath partial order, linear order, well order, initial segment; formal definitions and proofs within the axioms of set theory.

ordering in Arabic: نظرية الترتيب

ordering in German: Ordnungsrelation

ordering in Spanish: Teoría del orden

ordering in Estonian: Järjestus

ordering in French: Relation d'ordre

ordering in Ido: Relaciono di rango

ordering in Italian: Teoria degli ordini

ordering in Hebrew: סדר חלקי

ordering in Polish: Częściowy porządek

ordering in Turkish: Sıralamalar

ordering in Chinese: 序理论

# Synonyms, Antonyms and Related Words

allocation, allotment, apportionment, arrangement, array, arraying, authority, collation, collocation, command, conduct, constitution, control, deployment, direction, disposal, disposition, distribution, form, formation, formulation, governance, government, guidance, handling, husbandry, lead, leading, management, managery, managing, manipulation, marshaling, order, pilotage, placement, regimentation, regulation, running, sequence, steerage, steering, structuring, syntax, the conn, the helm, the
wheel