Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Glossary of order theory
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Glossary of terms used in branch of mathematics}} {{wiktionary|Appendix:Glossary of order theory}} This is a glossary of some terms used in various branches of [[mathematics]] that are related to the fields of [[Order theory|order]], [[Lattice (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 (order theory)|completeness properties]] of partial orders * [[Distributivity (order theory)|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> {{compact ToC|side=yes|top=yes|num=yes}} __NOTOC__ == A == * '''Acyclic'''. A [[binary relation]] is acyclic if it contains no "cycles": equivalently, its [[transitive closure]] is [[Antisymmetric relation|antisymmetric]].<ref name=BosSuz/> * '''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''. * '''Antisymmetric relation'''. A [[homogeneous relation]] ''R'' on a set ''X'' is '''[[Antisymmetric relation|antisymmetric]]''', if ''x R y'' and ''y R x'' implies ''x = y'', for all elements ''x'', ''y'' in ''X''. * '''Antitone'''. 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 [[Mathematical analysis|analysis]], in the presence of [[total order]]s, 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 relation]]'''. A [[homogeneous 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 (order theory)|Atom]]'''. An atom in a poset ''P'' with least element 0, is an element that is minimal among all elements that are unequal to 0. * '''Atomic'''. An 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''. == B == * '''Base'''. See ''continuous poset''. * '''[[Binary relation]]'''. A binary relation over two sets <math>X \text{ and } Y</math> is a subset of their [[Cartesian product]] <math>X \times Y.</math> * '''[[Boolean algebra (structure)|Boolean algebra]]'''. 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. * '''[[Bounded poset]]'''. A [[Bounded poset|bounded]] poset is one that has a least element and a greatest element. * '''[[Bounded complete]]'''. 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. == C == * '''[[Total order#Chains|Chain]]'''. A chain is a totally ordered set or a totally ordered subset of a poset. See also {{em|total order}}. * '''[[Chain complete]]'''. A [[partially ordered set]] in which every [[Total order#Chains|chain]] has a [[least upper bound]]. * '''[[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 element|Compact]]'''. An element ''x'' of a poset is compact if it is ''[[Way-below relation|way below]]'' itself, i.e. ''x''<<''x''. One also says that such an ''x'' is {{em|finite}}. * '''[[Comparability|Comparable]]'''. Two elements ''x'' and ''y'' of a poset ''P'' are comparable if either ''x'' ≤ ''y'' or ''y'' ≤ ''x''. * '''[[Comparability graph]]'''. The comparability graph of a poset (''P'', ≤) is the [[Graph (discrete mathematics)|graph]] with vertex set ''P'' in which the edges are those pairs of distinct elements of ''P'' that are comparable under ≤ (and, in particular, under its reflexive reduction <). * '''[[Complete Boolean algebra]]'''. A [[Boolean algebra (structure)|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 (order)|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 partial order]] (q.v.) with least element. * '''Complete relation'''. Synonym for ''[[Connected relation]]''. * '''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]] [[complete partial order|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. * '''[[Dedekind–MacNeille completion|Completion by cuts]]'''. Synonym of [[Dedekind–MacNeille completion]]. * '''[[Connected relation]]'''. A total or complete relation ''R'' on a set ''X'' has the property that for all elements ''x'', ''y'' of ''X'', at least one of ''x R y'' or ''y R x'' holds. * '''[[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''. * '''Converse'''. The converse <° of an order < is that in which x <° y whenever y < x. * '''Cover'''. An element ''y'' of a poset ''P'' is said to cover an element ''x'' of ''P'' (and is called a cover of ''x'') if ''x'' < ''y'' and there is no element ''z'' of ''P'' such that ''x'' < ''z'' < ''y''. * '''[[Complete partial order|cpo]]'''. See ''complete partial order''. == D == * '''dcpo'''. See ''[[directed complete partial order]]''. * '''[[Dedekind–MacNeille completion]]'''. The Dedekind–MacNeille completion of a [[partially ordered set]] is the smallest [[complete lattice]] that contains it. * '''[[Dense order]]'''. A '''[[Dense order|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''. * '''[[Derangement]]'''. A permutation of the elements of a set, such that no element appears in its original position. * '''[[Directed set]]'''. 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''. * '''[[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. * '''[[Distributivity (order theory)|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 theory|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''. * '''[[Duality (order theory)|Dual]]'''. For a poset (''P'', ≤), the dual order ''P''<sup>''d''</sup> = (''P'', ≥) is defined by setting ''x ≥ y'' [[if and only if]] ''y ≤ x''. The dual order of ''P'' is sometimes denoted by ''P''<sup>op</sup>, 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. == 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 (mathematics)|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''. * '''[[Complete Heyting algebra|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'' ∧ <math>\bigvee</math>''Y'' = <math>\bigvee</math>{''x'' ∧ ''y'' | ''y'' in ''Y''} holds. Frames are also known as ''locales'' and as complete [[Heyting algebra]]s. == 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''<sub>''a''</sub>: ''H'' → ''H'', given by ''f''<sub>''a''</sub>(''x'') = ''a'' ∧ ''x'' is the lower adjoint of a [[Galois connection]], for every element ''a'' of ''H''. The upper adjoint of ''f''<sub>''a''</sub> is then denoted by ''g''<sub>''a''</sub>, with ''g''<sub>''a''</sub>(''x'') = ''a'' ⇒; ''x''. Every [[Boolean algebra (structure)|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 <math>X</math> is a subset of <math>X \times X.</math> Said differently, it is a [[binary relation]] over <math>X</math> and itself. == I == * '''[[Ideal (order theory)|Ideal]]'''. An '''[[Ideal (order theory)|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 <math>\bigwedge</math>''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 (mathematics)|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. *<span id="interval finite poset"></span>'''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.<ref>{{harvnb|Deng|2008|loc=p. 22}}</ref> * '''Inverse'''. See ''converse''. * '''[[Irreflexive]]'''. A [[Relation (mathematics)|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 (order)|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. * '''[[Complete Heyting algebra|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 [[Total order#Chains|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''. * '''[[Greatest 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 maxim''um'' element is necessarily maxim''al'', 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''. * '''[[Least 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 minim''um'' element is necessarily minim''al'', but the converse need not hold. * '''[[Monotone function|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 [[Mathematical analysis|analysis]], in the presence of [[total order]]s, 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 function]]s. 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 relation|reflexive]], [[Antisymmetric relation|antisymmetric]], and [[Transitive relation|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 {{em|poset}} 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 relation|reflexive]] and [[Transitive relation|transitive]]. Such orders may also be called {{em|quasiorders}} or {{em|non-strict preorder}}. The term {{em|preorder}} is also used to denote an [[#A|acyclic]] [[binary relation]] (also called an {{em|acyclic digraph}}). * '''[[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''. * '''[[Order ideal|Prime]]'''. An {{em|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. * '''[[Order 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 [[Monotonic function|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'' ∧ ''x'' = 0}, i.e. as the least upper bound of all elements ''y'' with ''y'' ∧ ''x'' = 0. == Q == * '''Quasiorder'''. See ''preorder''. * '''[[Quasitransitive relation|Quasitransitive]]'''. A relation is quasitransitive if the relation on distinct elements is transitive. Transitive implies quasitransitive and quasitransitive implies acyclic.<ref name=BosSuz>{{cite book | title=Consistency, choice and rationality | first1=Walter | last1=Bossert | first2=Kōtarō | last2=Suzumura | publisher=Harvard University Press | year=2010 | isbn=978-0674052994 }}</ref> == 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 relation|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 [[Total order#Chains|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 order|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 [[Continuity (topology)|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 poset|algebraic]] [[Complete partial order|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 {{em|strict partial order}}. * '''[[Strict partial order]]'''. A strict partial order is a [[Homogeneous relation|homogeneous binary relation]] that is [[Transitive relation|transitive]], [[Irreflexive relation|irreflexive]], and [[Antisymmetric relation|antisymmetric]]. * '''[[Strict preorder]]'''. See {{em|strict partial order}}. * '''[[Supremum]]'''. For a poset ''P'' and a subset ''X'' of ''P'', the [[least element]] in the set of [[upper bound]]s 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'' ∨ ''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>∗</sup> ''y'' implies that ''x'' R ''y'' or not ''y'' R ''x''.<ref name=BosSuz/> * '''[[Symmetric relation]]'''. A [[homogeneous 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 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''. * '''[[Connected relation|Total relation]]'''. Synonym for ''[[Connected relation]]''. * '''[[Transitive relation]]'''. A [[Homogeneous relation|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''. * '''[[Transitive closure]]'''. The transitive closure R<sup>∗</sup> of a relation R consists of all pairs ''x'',''y'' for which there exists a finite chain ''x'' R ''a'', ''a'' R ''b'', ..., ''z'' R ''y''.<ref name=BosSuz/> == 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''. == V == * '''Valuation'''. Given a lattice <math>X</math>, a valuation <math>\nu : X \to [0,1]</math> is strict (that is, <math>\nu(\varnothing) = 0</math>), monotone, modular (that is, <math>\nu(U) + \nu(V) = \nu(U \cup V) + \nu(U \cap V)</math>) and positive. Continuous valuations are a generalization of measures. == 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]]. * '''[[Weak order]]'''. A partial order ≤ on a set ''X'' is a weak order provided that the poset (X, ≤) is [[isomorphic]] to a countable collection of sets ordered by comparison of [[cardinality]]. == 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''. == Notes == {{reflist}} ==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. Specific definitions: * {{Citation | last=Deng | first=Bangming | title=Finite dimensional algebras and quantum groups | year=2008 | publisher=American Mathematical Society | isbn=978-0-8218-4186-0 | series=Mathematical surveys and monographs | volume=150 }} {{Order theory}} [[Category:Glossaries of mathematics|Order theory]] [[Category:Order theory| ]] [[Category:Wikipedia glossaries using unordered lists]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation
(
edit
)
Template:Cite book
(
edit
)
Template:Compact ToC
(
edit
)
Template:Em
(
edit
)
Template:Harvnb
(
edit
)
Template:Order theory
(
edit
)
Template:Reflist
(
edit
)
Template:Short description
(
edit
)
Template:Wiktionary
(
edit
)