Appendix:Glossary of order theory

Definition from Wiktionary, the free dictionary
Jump to: navigation, search

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 ≤.


Table of Contents: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z


A[edit]

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 xy. In other words, the order relation of an antichain is just the identity relation.
Approximates relation 
See way-below relation.
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 
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.
asymmetric 
A 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 
In a poset P with least element 0, an element that is minimal among all elements that are unequal to 0.
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[edit]

Base 
See continuous poset.
Boolean algebra 
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 
One that has a least element 0 and a greatest element 1.
bounded complete 
Of poset: if every of its subsets with some upper bound also has a least such upper bound. The dual notion is not common.

C[edit]

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 Boolean algebra 
is 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 (possibly infinite) joins (suprema) and meets (infima) exist.
Complete partial order 
A complete partial order, or cpo, is a directed complete poset with least element.
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 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.
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.
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[edit]

dcpo 
See directed complete partial order.
dense order 
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.
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 ∧ (yz) = (xy) ∨ (xz). This condition is known to be equivalent to its order dual. A meet-semilattice is distributive if for all elements a, b and x, abx 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 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.

F[edit]

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\bigveeY = \bigvee{xy | y in Y} holds. Frames are also known as locales and as complete Heyting algebras.

G[edit]

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[edit]

Heyting algebra 
A Heyting algebra H is a bounded lattice in which the function fa: HH, given by fa(x) = ax 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) = ax. Every Boolean algebra is a Heyting algebra.

I[edit]

ideal 
A subset X of a poset P that is a directed lower set. The dual notion is called filter.
incidence algebra 
Of a poset: the associative algebra of all scalar-valued functions on intervals, with addition and scalar multiplication defined pointwise, and multiplication defined as a certain convolution; see incidence algebra for the details.
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 \bigwedgeX. The infimum of two elements may be written as inf{x,y} or xy. 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[edit]

Join 
See supremum.

L[edit]

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.
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 | 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[edit]

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[edit]

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: PQ 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.
Order-preserving 
See monotone.
Order-reversing 
See antitone.

P[edit]

partial order 
A binary relation that is reflexive, antisymmetric, and transitive. Since both notions depend on each other, the term is also used to refer to a partially ordered set.
partially ordered set 
(poset for short) A set P together with a partial order ≤ defined on P.
poset 
See partially ordered set.
preorder 
A binary relation that is reflexive and transitive. Such orders may also be called quasiorders.
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 ideal 
An ideal I in a lattice L such that for all elements x and y in L, xy in I implies x in I or y in I.
prime filter 
A set such that its complement is a prime ideal.
principal filter 
A filter that has a least element.
principal ideal 
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 x0 is called the pseudo-complement of x. It is also given by sup{y : yx = 0}, i.e. as the least upper bound of all elements y with yx = 0.

Q[edit]

quasiorder 
See preorder.

R[edit]

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 all elements x, y in X.

S[edit]

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 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, 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.
strict order 
A strict order is a binary relation that is antisymmetric, transitive, and irreflexive.
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 \bigveeX. The supremum of two elements may be written as sup{x,y} or xy. 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[edit]

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

U[edit]

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[edit]

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[edit]

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[edit]

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.