Appendix:Glossary of order theory

Hello, you have come here looking for the meaning of the word Appendix:Glossary of order theory. In DICTIOUS you will not only get to know all the dictionary meanings for the word Appendix:Glossary of order theory, but we will also tell you about its etymology, its characteristics and you will know how to say Appendix:Glossary of order theory in singular and plural. Everything you need to know about the word Appendix:Glossary of order theory you have here. The definition of the word Appendix:Glossary of order theory will help you to be more precise and correct when speaking or writing your texts. Knowing the definition ofAppendix:Glossary of order theory, as well as those of other words, enriches your vocabulary and provides you with more and better linguistic resources.

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

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

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

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

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

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

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 xY = {xy | 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) = 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

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 X. 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 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.
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 = {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: 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

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

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.
reflexive
A binary relation R on a set X is reflexive, if x R x holds for all elements x, y in X.

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

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

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.