Glossary of order theory

E

• Extension. For partial orders ≤ and ≤′ on a set X, ≤′ is an extension of ≤ provided that for all elements x and y of X, x ≤ y implies that x ≤′ y.

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 ∧ ${\displaystyle \bigvee }$Y = ${\displaystyle \bigvee }${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: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.
• Ground set. The ground set of a poset (X, ≤) is the set X on which the partial order ≤ is defined.

H

• Heyting algebra. A Heyting algebra H is a bounded lattice in which the function f_a: H → H, given by f_a(x) = a ∧ x is the lower adjoint of a Galois connection, for every element a of H. The upper adjoint of f_a is then denoted by g_a, with g_a(x) = a ⇒; x. Every Boolean algebra is a Heyting algebra.
• Hasse diagram. A Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction.
• Homogeneous relation. A homogeneous relation on a set ${\displaystyle X}$ is a subset of ${\displaystyle X\times X.}$ Said differently, it is a binary relation over ${\displaystyle X}$ and itself.

I

• Ideal. An ideal is a subset X of a poset P that is a directed lower set. The dual notion is called filter.
• Incidence algebra. The incidence algebra of a poset is 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 ${\displaystyle \bigwedge }$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 | a ≤ x ≤ b} of P. If a ≤ b does not hold the interval will be empty.
• Interval finite poset. A partially ordered set P is interval finite if every interval of the form {x in P | x ≤ a} is a finite set.^[2]
• 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.

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