HOME

TheInfoList




Order theory is a branch of
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
which investigates the intuitive notion of order using
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of elem ...
s. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the
order theory glossary This is a glossary of some terms used in various branches of mathematics that are related to the fields of order theory, order, lattice (order), lattice, and domain theory. Note that there is a structured list of order topics available as well. Othe ...
.


Background and motivation

Orders are everywhere in mathematics and related fields like
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of computation, automation, a ...
. The first order often discussed in
primary school A primary school (in Ireland, the United Kingdom, Australia, New Zealand, Jamaica, and South Africa), junior school (in Australia), elementary school or grade school (in North America and the Philippines) is a school A school is an ...

primary school
is the standard order on the
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...

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
number A number is a mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deduct ...

number
s, such as the
integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Roman Re ...
s and the reals. The idea of being greater than or less than another number is one of the basic intuitions of number systems (compare with
numeral systems A numeral system (or system of numeration) is a writing system A writing system is a method of visually representing verbal communication Communication (from Latin ''communicare'', meaning "to share") is the act of developing Semantics ...

numeral systems
) in general (although one usually is also interested in the actual
difference
difference
of two numbers, which is not given by the order). Other familiar examples of orderings are the
alphabetical order Alphabetical order is a system whereby character string In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a parti ...
of words in a dictionary and the
genealogical Genealogy (from el, γενεαλογία ' "the making of a pedigree") is the study of families, family history, and the tracing of their lineages. Genealogists use oral interviews, historical records, genetic analysis, and other records to ob ...

genealogical
property of
lineal descent A lineal descendant, in legal usage, is a blood relative in the direct line of descent – the children Biologically, a child (plural children) is a human being between the stages of childbirth, birth and puberty, or between the Development ...
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
subset relation
, e.g., "
Pediatricians Paediatrics ( also spelled pediatrics or pædiatrics) is the branch of medicine Medicine is the science Science (from the Latin word ''scientia'', meaning "knowledge") is a systematic enterprise that Scientific method, builds and Taxono ...
are
physicians A physician (American English American English (AmE, AE, AmEng, USEng, en-US), sometimes called United States English or U.S. English, is the set of varieties of the English language native to the United States. Currently, America ...

physicians
," and "
Circles A circle is a shape A shape or figure is the form of an object or its external boundary, outline, or external Surface (mathematics), surface, as opposed to other properties such as color, Surface texture, texture, or material type. A p ...

Circles
are merely special-case
ellipse In , an ellipse is a surrounding two , such that for all points on the curve, the sum of the two distances to the focal points is a constant. As such, it generalizes a , which is the special type of ellipse in which the two focal points are t ...

ellipse
s." 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 for which there exist ''incomparable'' elements are called ''
partial order In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s''; orders for which every pair of elements is comparable are ''
total order In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s''. 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 Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
between them. A simple example of an order theoretic property for functions comes from
analysis Analysis is the process of breaking a complex topic or substance Substance may refer to: * Substance (Jainism), a term in Jain ontology to denote the base or owner of attributes * Chemical substance, a material with a definite chemical composit ...
where monotone functions are frequently found.


Basic definitions

This section introduces ordered sets by building upon the concepts of
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, i ...
,
arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne', 'art' or 'cr ...
, and
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of elem ...
s.


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'). Then ≤ is a partial order if it is reflexive, antisymmetric, and
transitive Transitivity or transitive may refer to: Grammar * Transitivity (grammar), a property of verbs that relates to whether a verb can take direct objects * Transitive verb, a verb which takes an object * Transitive case, a grammatical case to mark arg ...
, 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
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 number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s,
integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Roman Re ...
s,
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
s 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
. These orders can also be called linear orders or chains. While many familiar orders are linear, the
subset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

subset
order on sets provides an example where this is not the case. Another example is given by the divisibility (or "is-a-
factor FACTOR (the Foundation to Assist Canadian Talent on Records) is a private non-profit organization "dedicated to providing assistance toward the growth and development of the Canadian music industry". FACTOR was founded in 1982 by radio broadcaste ...

factor
-of") relation , . For two natural numbers ''n'' and ''m'', we write ''n'', ''m'' if ''n''
divides In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
''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 distinct elements are incomparable. It is also the only relation that is both a partial order and an
equivalence relation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
. Many advanced properties of posets are interesting mainly for non-linear orders.


Visualizing a poset

Hasse diagram In order theory Order theory is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they ...
s can visually represent the elements and relations of a partial ordering. These are
graph drawing Graph drawing is an area of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical ...
s 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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

divides
'' relation). Even some infinite sets can be diagrammed by superimposing an
ellipsis The ellipsis , , or (as a single glyph The term glyph is used in typography File:metal movable type.jpg, 225px, Movable type being assembled on a composing stick using pieces that are stored in the type case shown below it Typography ...

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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
. For example, 1 is the
least element In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
of the positive integers and the
empty set #REDIRECT Empty set #REDIRECT Empty set#REDIRECT Empty set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry ...

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. 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 element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined duality (order theory), dually, t ...
s 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: : ''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 of many counterexamples. An important tool to ensure the existence of maximal elements under certain conditions is
Zorn's Lemma Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max August Zorn, Max Zorn and Kazimierz Kuratowski, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (ord ...
. 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 bound In mathematics, particularly in order theory Order theory is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), sh ...
s. 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
of a set of sets. This concept is also called supremum or join, and for a set ''S'' one writes sup(''S'') or \bigvee S for its least upper bound. Conversely, the
greatest lower bound are equal. Image:Supremum illustration.svg, 250px, A set ''A'' of real numbers (blue circles), a set of upper bounds of ''A'' (red diamond and circles), and the smallest such upper bound, that is, the supremum of ''A'' (red diamond). In mathematic ...
is known as
infimum In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to all elements of S, if such an element exists. Consequently, the term ''greatest low ...
or meet and denoted inf(''S'') or \bigwedge S. These concepts play an important role in many applications of order theory. For two elements ''x'' and ''y'', one also writes x\vee y and x\wedge y 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 In arithmetic Arithmetic (from the Ancient Greek, Greek wikt:en:ἀριθμός#Ancient Greek, ἀριθμός ''arithmos'', 'number' and wikt:en:τική#Ancient Greek, τική wikt:en:τέχνη#Ancient Greek, έχνη ''tiké échne', ...

least common multiple
of the numbers. Greatest lower bounds in turn are given by the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...

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.


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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
of two partially ordered sets, taken together with the
product order In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...

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 250px, The set of all subsets of a three-element set , ordered by inclusion. Distinct sets on the same horizontal level are incomparable with each other. Some other pairs, such as and , are also incomparable. In mathematics, especially order the ...
<, 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 Figure 3. A function that is not monotonic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus ...
. 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''(''a'') ≥ ''f''(''b''). 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 In , the complement of a , often denoted by (or ), are the not in . When all sets under consideration are considered to be s of a given set , the absolute complement of is the set of elements in that are not in . The relative complement of ...
on a
powerset Image:Hasse diagram of powerset of 3.svg, 250px, The elements of the power set of order theory, ordered with respect to Inclusion (set theory), inclusion. In mathematics, the power set (or powerset) of a Set (mathematics), set is the set of al ...

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 isomorphismIn the mathematical field of order theory Order theory is a branch of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (g ...
s are functions that define such a renaming. An order-isomorphism is a monotone
bijective In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
function that has a monotone inverse. This is equivalent to being a
surjective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
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 connection In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no genera ...
s. 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 operatorIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
s, which are not only monotonic, but also
idempotent Idempotence (, ) is the property of certain operations in mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), an ...
, 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 orderIn mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value f(x) of some function f. An important class of pointwise concepts are the ''pointwise operations'', that is, operations defined o ...
. 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 Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer s ...
, where
function space In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
s 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
has to be mentioned. A preorder is a relation that is reflexive and transitive, but not necessarily antisymmetric. Each preorder induces an
equivalence relation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
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. Several types of orders can be defined from numerical data on the items of the order: a
total order In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
results from attaching distinct real numbers to each item and using the numerical comparisons to order the items; instead, if distinct items are allowed to have equal numerical scores, one obtains a
strict weak ordering The 13 possible strict weak orderings on a set of three elements . The only total orders are shown in black. Two orderings are connected by an edge if they differ by a single dichotomy. In mathematics Mathematics (from Ancient Greek, Gre ...
. Requiring two scores to be separated by a fixed threshold before they may be compared leads to the concept of a
semiorder In order theory, a branch of mathematics, a semiorder is a type of ordering for items with numerical scores, where items with widely differing scores are compared by their scores and where scores within a given margin of error are deemed Comparabili ...

semiorder
, while allowing the threshold to vary on a per-item basis produces an
interval order upright=1.35, alt=The Hasse diagram for a partial order alongside an interval representation of the order., A partial order on the set illustrated by its Hasse diagram (left) and a collection of intervals that represents it (right). In mathematics ...
. An additional simple but useful property leads to so-called
well-founded In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a Class (set theory), class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an Element (mathematics), element ...
, 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
suprema
of certain sets is guaranteed. Focusing on this aspect, usually referred to as completeness of orders, one obtains: *
Bounded posetImage:Bounded unbounded.svg, An artist's impression of a bounded set (top) and of an unbounded set (bottom). The set at the bottom continues forever towards the right. :''"Bounded" and "boundary" are distinct concepts; for the latter see boundary (to ...
s, i.e. posets with a least and
greatest element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined duality (order theory), dually, t ...
(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 lattice In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
s, where every set has a supremum and infimum, and *
Directed complete partial orderIn mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness (order theory), completeness properties. Complete partia ...
s (dcpos), that guarantee the existence of suprema of all directed subsets and that are studied in
domain theory Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer s ...
. * Partial orders with complements, or ''poc sets'', are posets with a unique bottom element 0, as well as an order-reversing involution * such that a \leq a^ \implies a = 0. 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 Universal algebra (sometimes called general algebra) is the field of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spa ...
. Hence, in a lattice, two operations ∧ and ∨ are available, and one can define new properties by giving identities, such as : ''x'' ∧ (''y'' ∨ ''z'')  =  (''x'' ∧ ''y'') ∨ (''x'' ∧ ''z''), for all ''x'', ''y'', and ''z''. This condition is called distributivity and gives rise to
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice ope ...
s. 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 algebra __notoc__ Arend Heyting (; 9 May 1898 – 9 July 1980) was a Netherlands, Dutch mathematician and logician. Biography Heyting was a student of Luitzen Egbertus Jan Brouwer at the University of Amsterdam, and did much to put intuitionistic log ...
s and *
Boolean algebra In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
s, which both introduce a new operation ~ called negation. Both structures play a role in
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal sys ...
and especially Boolean algebras have major applications in
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of computation, automation, a ...
. 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 Finite is the opposite of Infinity, infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected ...
. Locally finite posets give rise to
incidence algebraIn order theory Order theory is a branch of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, cha ...
s which in turn can be used to define the
Euler characteristic#REDIRECT Euler characteristic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathema ...
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 Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considered ...
, which have the additional property that each two of their elements have an upper bound within the ideal. Their duals are given by
filters Filter, filtering or filters may refer to: Science and technology Device * Filter (chemistry), a device which separates solids from fluids (liquids or gases) by adding a medium through which only the fluid can pass ** Filter (aquarium), critical ...
. 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 A chain is a wikt:series#Noun, serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression (physics), compression but line (g ...
. The opposite notion, the
antichainIn mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are Incomparability, incomparable. The size of the largest antichain in a partially ordered set is kno ...
, 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 points of contact with order theory, some of these are to be presented below.


Universal algebra

As already mentioned, the methods and formalisms of
universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spa ...
are an important tool for many order theoretic considerations. Beside formalizing orders in terms of
algebraic structure In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s that satisfy certain identities, one can also establish other connections to algebra. An example is given by the correspondence between
Boolean algebra In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
s and
Boolean ringIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
s. Other issues are concerned with the existence of free constructions, such as
free latticeIn mathematics, in the area of order theory, a free lattice is the free object corresponding to a Lattice (order), lattice. As free objects, they have the universal property. Formal definition Any set (mathematics), set ''X'' may be used to generate ...
s based on a given set of generators. Furthermore, closure operators are important in the study of universal algebra.


Topology

In
topology In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities ...

topology
, orders play a very prominent role. In fact, the collection of
open set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s provides a classical example of a complete lattice, more precisely a complete
Heyting algebra __notoc__ Arend Heyting (; 9 May 1898 – 9 July 1980) was a Netherlands, Dutch mathematician and logician. Biography Heyting was a student of Luitzen Egbertus Jan Brouwer at the University of Amsterdam, and did much to put intuitionistic log ...
(or "frame" or "locale").
Filters Filter, filtering or filters may refer to: Science and technology Device * Filter (chemistry), a device which separates solids from fluids (liquids or gases) by adding a medium through which only the fluid can pass ** Filter (aquarium), critical ...
and nets are notions closely related to order theory and the closure operator of sets can be used to define a topology. Beyond these relations, topology can be looked at solely in terms of the open set lattices, which leads to the study of
pointless topologyIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
. 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. Considering topologies on a poset (''X'', ≤) that in turn induce ≤ as their specialization order, the finest such topology is the
Alexandrov topologyIn topology, an Alexandrov topology is a topological space, topology in which the intersection (set theory), intersection of any family of open sets is open. It is an axiom of topology that the intersection of any ''finite'' family of open sets is op ...
, given by taking all upper sets as opens. Conversely, the Comparison of topologies, coarsest topology that induces the specialization order is the upper topology, having the complements of ideal (order theory), principal ideals (i.e. sets of the form for some ''x'') as a subbase. Additionally, a topology with specialization order ≤ may be Specialization (pre)order#Important properties, 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 if and only if it is continuous function (topology), continuous with respect to the Scott topology (for this reason this order theoretic property is also called Scott-continuous, Scott-continuity).


Category theory

The visualization of orders with
Hasse diagram In order theory Order theory is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they ...
s 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 category theory, categories, where elements are objects and each set of morphisms between two elements is at most singleton. Functions between orders become functors between categories. Many ideas of order theory are just concepts of category theory in small. For example, an infimum is just a product (category theory), categorical product. More generally, one can capture infima and suprema under the abstract notion of a limit (category theory), categorical limit (or ''colimit'', respectively). Another place where categorical ideas occur is the concept of a (monotone)
Galois connection In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no genera ...
, 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 mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, in terms of categories. Further insights result when categories of orders are found equivalence of categories, 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 Sanders Peirce, Richard Dedekind, and Ernst Schröder (mathematician), Ernst Schröder also consider concepts of order theory. Contributors to ordered geometry were listed in a 1961 textbook: In 1901 Bertrand Russell wrote "On the notion of order" exploring the foundations of the idea through generation of serial relation, series. He returned to the topic in part IV of ''The Principles of Mathematics'' (1903). Russell noted that
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of elem ...
''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 was coined by Garrett Birkhoff in the second edition of his influential book ''Lattice Theory''.


See also

* Cyclic order * Hierarchy * Incidence algebra * Causal Sets


Notes


References

* * * *


External links


Orders at ProvenMath
partial order, linear order, well order, initial segment; formal definitions and proofs within the axioms of set theory. * Nagel, Felix (2013)
Set Theory and Topology. An Introduction to the Foundations of Analysis
{{Areas of mathematics , state=collapsed Order theory,