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:

  • completeness properties of partial orders
  • distributivity laws of order theory

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, <math>\,\leq\,</math> will suffice to denote the corresponding relational symbol, even without prior introduction. Furthermore, < will denote the strict order induced by <math>\,\leq.</math>

__NOTOC__

A

  • Acyclic. A binary relation is acyclic if it contains no "cycles": equivalently, its transitive closure is antisymmetric.
  • Inverse. See converse.
  • Irreflexive. A relation R on a set X is irreflexive, if there is no element x in X such that x R x.
  • Isotone. See monotone.

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 a ≤ x for every element x in X. The dual notion is called greatest element.
  • The length of a chain is the number of elements less one. A chain with 1 element has length 0, one with 2 elements has length 1, etc.
  • Linear. See total order.
  • Linear extension. A linear extension of a partial order is an extension that is a linear order, or total order.
  • Locale. A locale is a complete Heyting algebra. Locales are also called frames and appear in Stone duality and pointless topology.
  • Locally finite poset. A partially ordered set P is locally finite if every interval [a, b] = {x in P | a ≤ x ≤ b} 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 b ≤ x, 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, p ≤ x implies that p is contained in X. The dual notion is called upper set.

M

  • Maximal chain. A chain in a poset to which no element can be added without losing the property of being totally ordered. This is stronger than being a saturated chain, as it also excludes the existence of elements either less than all elements of the chain or greater than all its elements. A finite saturated chain is maximal if and only if it contains both a minimal and a maximal element of the poset.
  • Maximal element. A maximal element of a subset X of a poset P is an element m of X, such that m ≤ x implies m = x, for all x in X. The dual notion is called minimal element.
  • Maximum element. Synonym of greatest element. For a subset X of a poset P, an element a of X is called the maximum element of X if x ≤ a for every element x in X. A maximum element is necessarily maximal, but the converse need not hold.
  • Meet. See infimum.
  • Minimal element. A minimal element of a subset X of a poset P is an element m of X, such that x ≤ m implies m = x, for all x in X. The dual notion is called maximal element.
  • Minimum element. Synonym of least element. For a subset X of a poset P, an element a of X is called the minimum element of X if x ≥ a for every element x in X. A minimum element is necessarily minimal, but the converse need not hold.
  • Monotone. A function f between posets P and Q is monotone if, for all elements x, y of P, x ≤ y (in P) implies f(x) ≤ f(y) (in Q). Other names for this property are isotone and 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-dual. The order dual of a partially ordered set is the same set with the partial order relation replaced by its converse.
  • Order-embedding. A function f between posets P and Q is an order-embedding if, for all elements x, y of P, x ≤ y (in P) is equivalent to f(x) ≤ f(y) (in Q).
  • Order isomorphism. A mapping f: P → Q between two posets P and Q is called an order isomorphism, if it is bijective and both f and f<sup>−1</sup> are monotone functions. Equivalently, an order isomorphism is a surjective order embedding.
  • Order-preserving. See monotone.
  • Order-reversing. See antitone.

P

  • Partial order. A partial order is a binary relation that is reflexive, antisymmetric, and transitive. In a slight abuse of terminology, the term is sometimes also used to refer not to such a relation, but to its corresponding partially ordered set.
  • Partially ordered set. A partially ordered set <math>(P, \leq),</math> or for short, is a set <math>P</math> together with a partial order <math>\,\leq\,</math> on <math>P.</math>
  • Poset. A partially ordered set.
  • Preorder. A preorder is a binary relation that is reflexive and transitive. Such orders may also be called or . The term is also used to denote an acyclic binary relation (also called an ).
  • Preordered set. A preordered set <math>(P, \leq)</math> is a set <math>P</math> together with a preorder <math>\,\leq\,</math> on <math>P.</math>
  • 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 I in a lattice L is said to be prime, if, for all elements x and y in L, x &and; 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 if and only if 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.
  • Projection (operator). A self-map on a partially ordered set that is monotone and idempotent under function composition. Projections play an important role in domain theory.
  • 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 &and; x = 0}, i.e. as the least upper bound of all elements y with y &and; x = 0.

Q

  • Quasiorder. See preorder.
  • Quasitransitive. A relation is quasitransitive if the relation on distinct elements is transitive. Transitive implies quasitransitive and quasitransitive implies acyclic.

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.
  • Reflexive. A binary relation R on a set X is reflexive, if x R x holds for every element x in X.
  • Residual. A dual map attached to a residuated mapping.
  • Residuated mapping. A monotone map for which the preimage of a principal down-set is again principal. Equivalently, one component of a Galois connection.

S

  • Saturated chain. A chain in a poset such that no element can be added between two of its elements without losing the property of being totally ordered. If the chain is finite, this means that in every pair of successive elements the larger one covers the smaller one. See also maximal chain.
  • Scattered. A total order is scattered if it has no densely ordered subset.
  • Scott-continuous. A monotone function f : P → Q 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 domain. A Scott domain is a partially ordered set which is a bounded complete algebraic cpo.
  • Scott open. See Scott topology.
  • Scott topology. For a poset P, a subset O is Scott-open if it is an upper set and 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.
  • Sperner property of a partially ordered set
  • Sperner poset
  • Strictly Sperner poset
  • Strongly Sperner poset
  • Strict order. See .
  • Strict partial order. A strict partial order is a homogeneous binary relation that is transitive, irreflexive, and antisymmetric.
  • Strict preorder. See .
  • 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 <math>\bigvee</math>X. The supremum of two elements may be written as sup{x,y} or x &or; y. If the set X is finite, one speaks of a finite supremum. The dual notion is called infimum.
  • Suzumura consistency. A binary relation R is Suzumura consistent if x R<sup>&lowast;</sup> y implies that x R y or not y R x.