# 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

• 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 xy. In other words, the order relation of an antichain is just the identity relation.
• Approximates relation. See way-below relation.
• An antitone function f between posets P and Q is a function for which, for all elements x, y of P, xy (in P) implies f(y) ≤ f(x) (in Q). 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.
• An asymmetric relation R is a relation that is not symmetric.
• An atom in a poset P with least element 0, is an element that is minimal among all elements that are unequal to 0.
• A 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 ax.

## B

• Base. See continuous poset.
• 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 v ¬x = 1.
• A bounded poset is one that has a least element 0 and a greatest element 1.
• 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 total order.
• Closure operator. A closure operator on the poset P is a function C : PP that is monotone, idempotent, and satisfies C(x) ≥ 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 finite.
• Comparable. Two elements x and y of a poset P are comparable if either xy or yx.
• Complete lattice. A complete lattice is a poset in which arbitrary (possibly infinite) joins (suprema) and meets (infima) exist.
• Complete semilattice. The notion of a complete semilattice is defined in different ways. As explained in the article on completeness (order theory), 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 (meet-) 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. A complete lattice is completely distributive if arbitrary joins distribute over arbitrary meets. For the formal statement see the article on distributivity (order theory). The concept of complete distributivity is self-dual.
• 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 {y in B | y<<x}.
• Continuous function. See Scott-continuous.
• cpo. See complete partial order.

## D

• dcpo. See directed complete partial 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.
• Directed. 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 xz and yz. The dual notion is called filtered.
• Distributive. A lattice L is called distributive if, for all x, y, and z in L, we find that x ^ (y v z) = (x ^ y) v (x ^ z). 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 ^ bx 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 (P, ≤), the dual order (P, ≥) is defined by setting x ≥ y iff 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.

## 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 zx and zy. 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 ^ VY = V{x ^ y | y in Y} holds. Frames are also known as locales and as complete Heyting algebras.

## G

• Galois connection. Given two posets P and Q, a pair of monotone functions F:PQ and G:QP is called a Galois connection, if F(x) ≤ y is equivalent to xG(y), for all x in P and y in Q. F is called the lower adjoint of G and G is called the upper adjoint of F.
• Greatest element. For a subset X of a poset P, an element a of X is called the greatest element of X, if xa for every element x in X. The dual notion is called least element.

## H

• Heyting algebra. A Heyting algebra H is a bounded lattice in which the function fa: HH, given by fa(x) = a ^ x is the lower adjoint of a Galois connection, for every element a of H. The upper adjoint of fa is then denoted by ga, with ga(x) = a => x. Every Boolean algebra is a Heyting algebra.

## I

• An ideal is a subset X of a poset P that is a directed lower set. The dual notion is called filter.
• Infimum. For a poset P and a subset X of P, the greatest element in the set of lower bounds of X (if it exists, which it may not) is called the infimum, meet, or greatest lower bound of X. It is denoted by inf X or ^X. The infimum of two elements may be written as inf{x,y} or x ^ y. If the set X is finite, one speaks of a finite infimum. The dual notion is called supremum.
• Interval. For two elements a, b of a partially ordered set P, the interval [a,b] is the subset {x in P | axb} of P. If ab does not hold the interval will be empty.
• Irreflexive. A relation R on a set X is irreflexive, if there is no element x in X such that x R x.

## J

• Join. See supremum.

## L

• Lattice. A lattice is a poset in which all non-empty finite joins (suprema) and meets (infima) exist.
• Least element. For a subset X of a poset P, an element a of X is called the least element of X, if ax for every element x in X. The dual notion is called greatest element.
• Linear. See total order.
• Locally finite poset. A partially ordered set P is locally finite if every interval [a, b] = {x in P | axb} is a finite set.
• Lower bound. A lower bound of a subset X of a poset P is an element b of P, such that bx, for all x in X. The dual notion is called upper bound.
• Lower set. A subset X of a poset P is called a lower set if, for all elements x in X and p in P, px implies that p is contained in X. The dual notion is called upper set.

## M

• Maximal element. A maximal element of a subset X of a poset P is an element m of X, such that mx implies m = x, for all x in X. The dual notion is called minimal element.
• Meet. See infimum.
• Minimal element. A minimal element of a subset X of a poset P is an element m of X, such that xm implies m = x, for all x in X. The dual notion is called maximal element.
• Monotone. A function f between posets P and Q is monotone if, for all elements x, y of P, xy (in P) implies f(x) ≤ f(y) (in Q). Another name for this property is order-preserving. In analysis, in the presence of total orders, such functions are often called monotonically increasing, but this is not a very convenient description when dealing with non-total orders. The dual notion is called antitone or order reversing.

## O

• Order-embedding. A function f between posets P and Q is an order-embedding if, for all elements x, y of P, xy (in P) is equivalent to f(x) ≤ f(y) (in Q).
• Order isomorphism. A mapping f: P &rarr Q between two posets P and Q is called an order isomorphism, if it is bijective and both f and f-1 are monotone. Equivalently, an order isomorphism is a surjective order embedding.

## P

• Partially ordered set. A partially ordered set, or poset for short, is a set P together with a partial order ≤ defined on P.
• poset. See partial order.
• Preserving. A function f between posets P and Q is said to preserve suprema (joins), if, for all subsets X of P that have a supremum sup X in P, we find that sup{f(x): x in X} exists and is equal to f(sup X). Such a function is also called join-preserving. Analogously, one says that f preserves finite, non-empty, directed, or arbitrary joins (or meets). The converse property is called join-reflecting.
• Prime. An ideal I in a lattice L is said to be prime, if, for all elements x and y in L, x ^ y in I implies x in I or y in I. The dual notion is called a prime filter. Equivalently, a set is a prime filter iff its complement is a prime ideal.
• Principal. A filter is called principal filter if it has a least element. Dually, a principal ideal is an ideal with a greatest element. The least or greatest elements may also be called principal elements in these situations.
• Pseudo-complement. In a Heyting algebra, the element x => 0 is called the pseudo-complement of x. It is also given by sup{y : y ^ x = 0}, i.e. as the least upper bound of all elements y with y ^ x = 0.

## Q

• Quasiorder. See preorder.

## R

• Reflecting. A function f between posets P and Q is said to reflect suprema (joins), if, for all subsets X of P for which the supremum sup{f(x): x in X} exists and is of the form f(s) for some s in P, then we find that sup X exists and that sup X = s . Analogously, one says that f reflects finite, non-empty, directed, or arbitrary joins (or meets). The converse property is called join-preserving.

## S

• Scott-continuous. A monotone function f : PQ between posets P and Q is Scott-continuous if, for every directed set D that has a supremum sup D in P, the set {fx | x in D} has the supremum f(sup D) in Q. Stated differently, a Scott-continuous function is one that preserves all directed suprema. This is in fact equivalent to being continuous with respect to the Scott topology on the respective posets.
• Scott open. See Scott topology.
• Scott topology. For a poset P, an upper set O is Scott-open if all directed sets D that have a supremum in O have non-empty intersection with O. The set of all Scott-open sets forms a topology, the Scott-topology.
• Semilattice. A semilattice is a poset in which either all finite non-empty joins (suprema) or all finite non-empty meets (infima) exist. Accordingly, one speaks of a join-semilattice or meet-semilattice.
• Smallest element. See least element.
• Supremum. For a poset P and a subset X of P, the least element in the set of upper bounds of X (if it exists, which it may not) is called the supremum, join, or least upper bound of X. It is denoted by sup X or VX. The supremum of two elements may be written as sup{x,y} or x v y. If the set X is finite, one speaks of a finite supremum. The dual notion is called infimum.
• Symmetric. A relation R on a set X is symmetric, if x R y implies y R x, for all elements x, y in X.

## T

• Top. See unit.
• Total order. A total order T is a partial order in which, for each x and y in T, we have xy or yx. Total orders are also called linear orders or chains.
• Transitive. A relation R on a set X is transitive, if x R y and y R z imply x R z, for all elements x, y, z in X.

## U

• Unit. The greatest element of a poset P can be called unit or just 1 (if it exists). Another common term for this element is top. It is the infimum of the empty set and the supremum of P. The dual notion is called zero.
• Up-set. See upper set.
• Upper bound. An upper bound of a subset X of a poset P is an element b of P, such that xb, for all x in X. The dual notion is called lower bound.
• Upper set. A subset X of a poset P is called an upper set if, for all elements x in X and p in P, xp implies that p is contained in X. The dual notion is called lower set.

## W

• Way-below relation. In a poset P, some element x is way below y, written x<<y, if for all directed subsets D of P which have a supremum, ysup D implies xd for some d in D. One also says that x approximates y. See also domain theory.

## Z

• Zero. The least element of a poset P can be called zero or just 0 (if it exists). Another common term for this element is bottom. Zero is the supremum of the empty set and the infimum of P. The dual notion is called unit.

## References

The definitions given here are consistent with those that can be found in the following standard reference books:

• B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, 2nd Edition, Cambridge University Press, 2002.
• G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove and D. S. Scott, Continuous Lattices and Domains, In Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003.