Glossary of order theory

From Wikipedia, the free encyclopedia

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: Top - 0–9 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


[edit] 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 x ≤ y. In other words, the order relation of an antichain is just the identity relation.
  • Approximates relation. See way-below relation.
  • A 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.
  • An antitone function f between posets P and Q is a function for which, for all elements x, y of P, x ≤ y (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.
  • 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 a ≤ x.

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

[edit] 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 : P → P 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 x ≤ y or y ≤ x.
  • 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.
  • 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.

[edit] 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 x ≤ z and y ≤ z. 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 ∨ z) = (x ∧ y) ∨ (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 ∧ 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 (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.

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

[edit] G

  • Galois connection. Given two posets P and Q, a pair of monotone functions F:P → Q and G:Q → P is called a Galois connection, if F(x) ≤ y is equivalent to x ≤ G(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 x ≤ a for every element x in X. The dual notion is called least element.

[edit] H

  • Heyting algebra. A Heyting algebra H is a bounded lattice in which the function fa: H → H, 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.

[edit] 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 \bigwedgeX. 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 | a ≤ x ≤ b} of P. If a ≤ b 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.

[edit] J

  • Join. See supremum.

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

[edit] M

  • 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.
  • 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.
  • 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). 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.

[edit] O

  • 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-1 are monotone. Equivalently, an order isomorphism is a surjective order embedding.

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

[edit] Q

  • Quasiorder. See preorder.

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

[edit] S

  • 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 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 \bigveeX. The supremum of two elements may be written as sup{x,y} or x ∨ 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.

[edit] 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 x ≤ y or y ≤ x. 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.

[edit] 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 x ≤ b, 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, x ≤ p implies that p is contained in X. The dual notion is called lower set.

[edit] 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, y ≤ sup D implies x ≤ d for some d in D. One also says that x approximates y. See also domain theory.

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

[edit] 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.
Retrieved from "http://en.wikipedia.org../../../g/l/o/Glossary_of_order_theory.html"