Order theory

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

is a branch of mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 that studies various kinds of binary relation

Binary relation

In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

s that capture the intuitive notion of ordering, providing a framework for saying when one thing is "less than" or "precedes" another.

An alphabetical list of many notions of order theory can be found in the order theory glossary. See also inequality, extreme value and mathematical optimization.

Overview

• Partially ordered set
  Partially ordered set
  In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
  
  
• Preorder
  Preorder
  In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...
  
  
• Totally ordered set
  • Total preorder
  • Chain
  • Trichotomy
    Trichotomy
    In mathematics, the Law of Trichotomy states that every real number is either positive, negative, or zero. More generally, trichotomy is the property of an order relation...
    
    
  • Extended real number line
    Extended real number line
    In mathematics, the affinely extended real number system is obtained from the real number system R by adding two elements: +∞ and −∞ . The projective extended real number system adds a single object, ∞ and makes no distinction between "positive" or "negative" infinity...
    
    
• Antichain
  Antichain
  In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
  
  
• Strict order

• Hasse diagram
  Hasse diagram
  In order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction...
  
  
  • Directed acyclic graph
    Directed acyclic graph
    In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
    
    
• Duality (order theory)
  Duality (order theory)
  In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
  
  
• Product order
  Product order
  In mathematics, given two ordered sets A and B, one can induce a partial ordering on the Cartesian product A × B. Giventwo pairs and in A × B, one sets ≤...
  
  

Distinguished elements of partial orders

• Greatest element
  Greatest element
  In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
  
   (maximum, top, unit), Least element (minimum, bottom, zero)
• Maximal element
  Maximal element
  In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
  
  , minimal element
• Upper bound
  Upper bound
  In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
  
  
  • Least upper bound (supremum, join)
  • Greatest lower bound (infimum, meet)
  • Limit superior and limit inferior
    Limit superior and limit inferior
    In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting bounds on the sequence...
    
    
• Irreducible element
• Prime element
• Compact element
  Compact element
  In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
  
  

Subsets of partial orders

• Cofinal
  Cofinal (mathematics)
  In mathematics, let A be a set and let ≤ be a binary relation on A. Then a subset B of A is said to be cofinal if it satisfies the following condition:This definition is most commonly applied when A is a partially ordered set or directed set under the relation ≤. Also, the notion of cofinal...
  
   and coinitial
  Cofinal (mathematics)
  In mathematics, let A be a set and let ≤ be a binary relation on A. Then a subset B of A is said to be cofinal if it satisfies the following condition:This definition is most commonly applied when A is a partially ordered set or directed set under the relation ≤. Also, the notion of cofinal...
  
   set, sometimes also called dense
  Cofinal (mathematics)
  In mathematics, let A be a set and let ≤ be a binary relation on A. Then a subset B of A is said to be cofinal if it satisfies the following condition:This definition is most commonly applied when A is a partially ordered set or directed set under the relation ≤. Also, the notion of cofinal...
  
  
• Meet-dense set and join-dense set
• Linked set
  Linked set
  In mathematics, an upwards linked set A is a subset of a partially ordered set P, in which any two of elements A have a common upper bound in P. Similarly, every pair of elements of a downwards linked set has a lower bound. Note that every centered set is linked, which includes, in particular,...
  
   (upwards and downwards)
• Directed set
  Directed set
  In mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...
  
   (upwards and downwards)
• centered
  Centered set
  In mathematics, an upwards centered set A is a subset of a partially ordered set P, such that any finite subset of A has an upper bound in P. Similarly, any finite subset of a downwards centered set has a lower bound...
  
   and σ-centered set
  Centered set
  In mathematics, an upwards centered set A is a subset of a partially ordered set P, such that any finite subset of A has an upper bound in P. Similarly, any finite subset of a downwards centered set has a lower bound...
  
  
• Net (mathematics)
  Net (mathematics)
  In mathematics, more specifically in general topology and related branches, a net or Moore–Smith sequence is a generalization of the notion of a sequence. In essence, a sequence is a function with domain the natural numbers, and in the context of topology, the range of this function is...
  
  
• Upper set
  Upper set
  In mathematics, an upper set of a partially ordered set is a subset U with the property that x is in U and x≤y imply y is in U....
  
   and lower set
• Ideal
  Ideal (order theory)
  In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
  
   and filter
  Filter (mathematics)
  In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...
  
  
  • Ultrafilter
    Ultrafilter
    In the mathematical field of set theory, an ultrafilter on a set X is a collection of subsets of X that is a filter, that cannot be enlarged . An ultrafilter may be considered as a finitely additive measure. Then every subset of X is either considered "almost everything" or "almost nothing"...
    
    

Special types of partial orders

• Completeness (order theory)
  Completeness (order theory)
  In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set . A special use of the term refers to complete partial orders or complete lattices...
  
  
• Dense order
  Dense order
  In mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x In mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x...
  
  
• Distributivity (order theory)
  Distributivity (order theory)
  In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima...
  
  
  • modular lattice
    Modular lattice
    In the branch of mathematics called order theory, a modular lattice is a lattice that satisfies the following self-dual condition:Modular law: x ≤ b implies x ∨  =  ∧ b,where  ≤  is the partial order, and  ∨  and  ∧  are...
    
    
  • distributive lattice
    Distributive lattice
    In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
    
    
  • completely distributive lattice
    Completely distributive lattice
    In the mathematical area of order theory, a completely distributive lattice is a complete lattice in which arbitrary joins distribute over arbitrary meets....
    
    
• Ascending chain condition
  Ascending chain condition
  The ascending chain condition and descending chain condition are finiteness properties satisfied by some algebraic structures, most importantly, ideals in certain commutative rings...
  
  
  • Infinite descending chain
    Infinite descending chain
    Given a set S with a partial order ≤, an infinite descending chain is a chain V that is a subset of S upon which ≤ defines a total order such that V has no least element, that is, an element m such that for all elements n in V it holds that m ≤ n.As an example, in the set of integers, the chain...
    
    
• Countable chain condition
  Countable chain condition
  In order theory, a partially ordered set X is said to satisfy the countable chain condition, or to be ccc, if every strong antichain in X is countable. There are really two conditions: the upwards and downwards countable chain conditions. These are not equivalent...
  
  , often abbreviated as ccc
• Knaster's condition
  Knaster's condition
  In mathematics, a partially ordered set P is said to have Knaster's condition upwards if any uncountable subset A of P has an upwards-linked uncountable subset...
  
  , sometimes denoted property (K)

Completeness properties

Completeness (order theory)

In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set . A special use of the term refers to complete partial orders or complete lattices...

• Semilattice
  Semilattice
  In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...
  
  
• Lattice
  Lattice (order)
  In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
  
  
• (Directed) complete partial order
  Complete partial order
  In mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties...
  
  , (d)cpo
• Bounded complete
• Complete lattice
  Complete lattice
  In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
  
  
  • Knaster–Tarski theorem
• Infinite divisibility
  Infinite divisibility
  The concept of infinite divisibility arises in different ways in philosophy, physics, economics, order theory , and probability theory...
  
  

Orders with further algebraic

Abstract algebra

Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...

 operations

• Heyting algebra
  Heyting algebra
  In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
  
  
  • Relatively complemented lattice
• Complete Heyting algebra
  Complete Heyting algebra
  In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames...
  
  
  • Pointless topology
    Pointless topology
    In mathematics, pointless topology is an approach to topology that avoids mentioning points. The name 'pointless topology' is due to John von Neumann...
    
    
• Boolean algebra (structure)
  • Boolean ring
    Boolean ring
    In mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists only of idempotent elements....
    
    
  • Kleene algebra
    Kleene algebra
    In mathematics, a Kleene algebra is either of two different things:* A bounded distributive lattice with an involution satisfying De Morgan's laws , additionally satisfying the inequality x∧−x ≤ y∨−y. Kleene algebras are subclasses of Ockham algebras...
    
    
• Complete Boolean algebra
  Complete Boolean algebra
  In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
  
  
• Orthocomplemented lattice
• Quantale
  Quantale
  In mathematics, quantales are certain partially ordered algebraic structures that generalize locales as well as various multiplicative lattices of ideals from ring theory and functional analysis...
  
  

Orders in abstract algebra

Abstract algebra

Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...

• Partially ordered monoid
• Ordered group
  Ordered group
  In abstract algebra, a partially-ordered group is a group equipped with a partial order "≤" that is translation-invariant; in other words, "≤" has the property that, for all a, b, and g in G, if a ≤ b then a+g ≤ b+g and g+a ≤ g+b.An element x of G is called positive element if 0 ≤ x...
  
  
  • Archimedean property
    Archimedean property
    In abstract algebra and analysis, the Archimedean property, named after the ancient Greek mathematician Archimedes of Syracuse, is a property held by some ordered or normed groups, fields, and other algebraic structures. Roughly speaking, it is the property of having no infinitely large or...
    
    
• Ordered ring
  Ordered ring
  In abstract algebra, an ordered ring is a commutative ring R with a total order ≤ such that for all a, b, and c in R:* if a ≤ b then a + c ≤ b + c.* if 0 ≤ a and 0 ≤ b then 0 ≤ ab....
  
  
• Ordered field
  Ordered field
  In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Historically, the axiomatization of an ordered field was abstracted gradually from the real numbers, by mathematicians including David Hilbert, Otto Hölder and...
  
  
• Artinian
  Artinian
  In mathematics, Artinian, named for Emil Artin, is an adjective that describes objects that satisfy particular cases of the descending chain condition.*A ring is an Artinian ring if it satisfies the descending chain condition on ideals...
  
  
• Noetherian
  Noetherian
  In mathematics, the adjective Noetherian is used to describe objects that satisfy an ascending or descending chain condition on certain kinds of subobjects; in particular,* Noetherian group, a group that satisfies the ascending chain condition on subgroups...
  
  
• Linearly ordered group
  Linearly ordered group
  In abstract algebra a linearly ordered or totally ordered group is an ordered group G such that the order relation "≤" is total...
  
  
• Monomial order
• Weak order of permutations
• Incidence algebra
  Incidence algebra
  In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for any locally finite partially ordered setand commutative ring with unity.-Definition:...
  
  

Functions

Function (mathematics)

In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 between partial orders

• Monotonic
• Pointwise order of functions
• Galois connection
  Galois connection
  In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...
  
  
• Order embedding
• Order isomorphism
  Order isomorphism
  In the mathematical field of order theory an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets . Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that one of...
  
  
• Closure operator
  Closure operator
  In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....
  
  
• Functions that preserve
  Limit-preserving function (order theory)
  In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i.e. certain suprema or infima. Roughly speaking, these functions map the supremum/infimum of a set to the supremum/infimum of the image of the set...
  
   suprema/infima

Completions and free constructions

Free object

In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure . It also has a formulation in terms of category theory, although this is in yet more abstract terms....

• Dedekind completion
• Ideal completion

Domain theory

• Way-below relation
• Continuous poset
  • Continuous lattice
• Algebraic poset
  • Scott domain
    Scott domain
    In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded complete cpo. It has been named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory...
    
    
  • Algebraic lattice
• Scott information system
  Scott information system
  In domain theory, a branch of mathematics and computer science, a Scott information system is a primitive kind of logical deductive system often used as an alternative way of presenting Scott domains.-Definition:...
  
  
• Powerdomain
• Scott topology
• Scott continuity
  Scott continuity
  In mathematics, given two partially ordered sets P and Q a function f : P \rightarrow Q between them is Scott-continuous if it preserves all directed suprema, i.e...
  
  

Orders in mathematical logic

Mathematical logic

Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

• Lindenbaum algebra
• Zorn's lemma
  Zorn's lemma
  Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Suppose a partially ordered set P has the property that every chain has an upper bound in P...
  
  
  • Hausdorff maximality theorem
• Boolean prime ideal theorem
  Boolean prime ideal theorem
  In mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...
  
  
• Ultrafilter
  Ultrafilter
  In the mathematical field of set theory, an ultrafilter on a set X is a collection of subsets of X that is a filter, that cannot be enlarged . An ultrafilter may be considered as a finitely additive measure. Then every subset of X is either considered "almost everything" or "almost nothing"...
  
  
• Ultrafilter lemma
• Tree (set theory)
  Tree (set theory)
  In set theory, a tree is a partially ordered set In set theory, a tree is a partially ordered set (poset) In set theory, a tree is a partially ordered set (poset) (T, In set theory, a tree is a partially ordered set (poset) (T, ...
  
  
• Tree (descriptive set theory)
• Suslin's problem
  Suslin's problem
  In mathematics, Suslin's problem is a question about totally ordered sets posed by Mikhail Yakovlevich Suslin in a work published posthumously in 1920....
  
  
• Absorption law
  Absorption law
  In algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.Two binary operations, say ¤ and *, are said to be connected by the absorption law if:...
  
  
• Canonical order
  Canonical order
  Canonical order may refer to:* in the context of sorting, a standard order, typically a total order, obeying certain rules, e.g. lexicographic order for strings* a monastic order of regular canon...
  
  
• Prewellordering
  Prewellordering
  In set theory, a prewellordering is a binary relation that is transitive, wellfounded, and total. In other words, if \leq is a prewellordering on a set X, and if we define \sim byx\sim y\iff x\leq y \land y\leq x...
  
  

Orders in topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

• Stone duality
  Stone duality
  In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they form a natural generalization of Stone's representation...
  
  
  • Stone's representation theorem for Boolean algebras
    Stone's representation theorem for Boolean algebras
    In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...
    
    
• Specialization (pre)order
  Specialization (pre)order
  In the branch of mathematics known as topology, the specialization preorder is a natural preorder on the set of the points of a topological space. For most spaces that are considered in practice, namely for all those that satisfy the T0 separation axiom, this preorder is even a partial order...
  
  
• Order topology
  Order topology
  In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets...
  
   of a total order (open interval topology)
• Alexandrov topology
  Alexandrov topology
  In topology, an Alexandrov space is a topological space in which the 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 open...
  
  
• Upper topology
• Scott topology
  • Scott continuity
    Scott continuity
    In mathematics, given two partially ordered sets P and Q a function f : P \rightarrow Q between them is Scott-continuous if it preserves all directed suprema, i.e...
    
    
• Lawson topology
  Lawson topology
  In mathematics and theoretical computer science the Lawson topology, named after J. D. Lawson, is a topology on partially ordered sets used in the study of domain theory. The lower topology on a poset P is generated by the subbasis consisting of all complements of principal filters on P...
  
  
• Finer topology