Glossary of order theory


This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:
In the following, partial orders will usually just be denoted by their carrier sets. As long as the intended meaning is clear from the context, will suffice to denote the corresponding relational symbol, even without prior introduction. Furthermore, < will denote the strict order induced by

A

  • Acyclic. A binary relation is acyclic if it contains no "cycles": equivalently, its transitive closure is antisymmetric.
  • Adjoint. See Galois connection.
  • Alexandrov topology. For a preordered set P, any upper set O is Alexandrov-open. Inversely, a topology is Alexandrov if any intersection of open sets is open.
  • Algebraic poset. A poset is algebraic if it has a base of compact elements.
  • Antichain. An antichain is a poset in which no two elements are comparable, i.e., there are no two distinct elements x and y such that x ≤ y. In other words, the order relation of an antichain is just the identity relation.
  • Approximates relation. See way-below relation.
  • Antisymmetric relation. A homogeneous relation R on a set X is antisymmetric, if x R y and y R x implies x = y, for all elements x, y in X.
  • Antitone. An antitone function f between posets P and Q is a function for which, for all elements x, y of P, x ≤ y implies f ≤ f. Another name for this property is order-reversing. In analysis, in the presence of total orders, such functions are often called monotonically decreasing, but this is not a very convenient description when dealing with non-total orders. The dual notion is called monotone or order-preserving.
  • Asymmetric relation. A homogeneous relation R on a set X is asymmetric, if x R y implies not y R x, for all elements x, y in X.
  • Atom. An atom in a poset P with least element 0, is an element that is minimal among all elements that are unequal to 0.
  • Atomic. An atomic poset P with least element 0 is one in which, for every non-zero element x of P, there is an atom a of P with a ≤ x.

    B

  • Base. See continuous poset.
  • Binary relation. A binary relation over two sets is a subset of their Cartesian product
  • Boolean algebra. A Boolean algebra is a distributive lattice with least element 0 and greatest element 1, in which every element x has a complement ¬x, such that x ∧ ¬x = 0 and x ∨ ¬x = 1.
  • Bounded poset. A bounded poset is one that has a least element and a greatest element.
  • Bounded complete. A poset is bounded complete if every of its subsets with some upper bound also has a least such upper bound. The dual notion is not common.

    C

  • Chain. A chain is a totally ordered set or a totally ordered subset of a poset. See also.
  • Chain complete. A partially ordered set in which every chain has a least upper bound.
  • Closure operator. A closure operator on the poset P is a function C : P → P that is monotone, idempotent, and satisfies C ≥ x for all x in P.
  • Compact. An element x of a poset is compact if it is way below itself, i.e. x<<x. One also says that such an x is.
  • Comparable. Two elements x and y of a poset P are comparable if either x ≤ y or y ≤ x.
  • Comparability graph. The comparability graph of a poset is the graph with vertex set P in which the edges are those pairs of distinct elements of P that are comparable under ≤.
  • Complete Boolean algebra. A Boolean algebra that is a complete lattice.
  • Complete Heyting algebra. A Heyting algebra that is a complete lattice is called a complete Heyting algebra. This notion coincides with the concepts frame and locale.
  • Complete lattice. A complete lattice is a poset in which arbitrary joins and meets exist.
  • Complete partial order. A complete partial order, or cpo, is a directed complete partial order with least element.
  • Complete relation. Synonym for Connected relation.
  • Complete semilattice. The notion of a complete semilattice is defined in different ways. As explained in the article on completeness, any poset for which either all suprema or all infima exist is already a complete lattice. Hence the notion of a complete semilattice is sometimes used to coincide with the one of a complete lattice. In other cases, complete semilattices are defined to be bounded complete cpos, which is arguably the most complete class of posets that are not already complete lattices.
  • Completely distributive lattice. A complete lattice is completely distributive if arbitrary joins distribute over arbitrary meets.
  • Completion. A completion of a poset is an order-embedding of the poset in a complete lattice.
  • Completion by cuts. Synonym of Dedekind–MacNeille completion.
  • Connected relation. A total or complete relation R on a set X has the property that for all elements x, y of X, at least one of x R y or y R x holds.
  • Continuous poset. A poset is continuous if it has a base, i.e. a subset B of P such that every element x of P is the supremum of a directed set contained in.
  • Continuous function. See Scott-continuous.
  • Converse. The converse <° of an order < is that in which x <° y whenever y < x.
  • Cover. An element y of a poset P is said to cover an element x of P if x < y and there is no element z of P such that x < z < y.
  • cpo. See complete partial order.

    D

  • dcpo. See directed complete partial order.
  • Dedekind–MacNeille completion. The Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it.
  • Dense order. A dense poset P is one in which, for all elements x and y in P with x < y, there is an element z in P, such that x < z < y. A subset Q of P is dense in P if for any elements x < y in P, there is an element z in Q such that x < z < y.
  • Derangement. A permutation of the elements of a set, such that no element appears in its original position.
  • Directed set. A non-empty subset X of a poset P is called directed, if, for all elements x and y of X, there is an element z of X such that x ≤ z and y ≤ z. The dual notion is called filtered.
  • Directed complete partial order. A poset D is said to be a directed complete poset, or dcpo, if every directed subset of D has a supremum.
  • Distributive. A lattice L is called distributive if, for all x, y, and z in L, we find that x ∧ = ∨. This condition is known to be equivalent to its order dual. A meet-semilattice is distributive if for all elements a, b and x, a ∧ b ≤ x implies the existence of elements a' ≥ a and b' ≥ b such that a' ∧ b' = x. See also completely distributive.
  • Domain. Domain is a general term for objects like those that are studied in domain theory. If used, it requires further definition.
  • Down-set. See lower set.
  • Dual. For a poset, the dual order Pd = is defined by setting x ≥ y if and only if y ≤ x. The dual order of P is sometimes denoted by Pop, and is also called opposite or converse order. Any order theoretic notion induces a dual notion, defined by applying the original statement to the order dual of a given set. This exchanges ≤ and ≥, meets and joins, zero and unit.

    E

  • Extension. For partial orders ≤ and ≤′ on a set X, ≤′ is an extension of ≤ provided that for all elements x and y of X, x ≤ y implies that x ≤′ y.

    F

  • Filter. A subset X of a poset P is called a filter if it is a filtered upper set. The dual notion is called ideal.
  • Filtered. A non-empty subset X of a poset P is called filtered, if, for all elements x and y of X, there is an element z of X such that z ≤ x and z ≤ y. The dual notion is called directed.
  • Finite element. See compact.
  • Frame. A frame F is a complete lattice, in which, for every x in F and every subset Y of F, the infinite distributive law x ∧ Y = holds. Frames are also known as locales and as complete Heyting algebras.