This is a glossary of some terms used in various branches of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
that are related to the fields of
order,
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
, and
domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...
. Note that there is a structured
list of order topics
Order theory is a branch of mathematics that studies various kinds of objects (often binary relations) that capture the intuitive notion of ordering, providing a framework for saying when one thing is "less than" or "precedes" another.
An alphabet ...
available as well. Other helpful resources might be the following overview articles:
*
completeness properties of partial orders
*
distributivity laws of order theory
*
preservation properties of functions between posets.
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
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
induced by
__NOTOC__
A
* Acyclic. A
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
is acyclic if it contains no "cycles": equivalently, its
transitive closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
is
antisymmetric.
[
* Adjoint. See ''Galois connection''.
* ]Alexandrov topology In topology, an Alexandrov topology is a topology in which the intersection of any family of open sets is open. It is an axiom of topology that the intersection of any ''finite'' family of open sets is open; in Alexandrov topologies the finite rest ...
. 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
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.
The size of the largest antichain in a partially ordered set is known as its wid ...
. 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
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) 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. An antitone
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of orde ...
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
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
, in the presence of total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
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
In mathematics, an asymmetric relation is a binary relation R on a set X where for all a, b \in X, if a is related to b then b is ''not'' related to a.
Formal definition
A binary relation on X is any subset R of X \times X. Given a, b \in X, ...
. A homogeneous relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) 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. 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
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
. A binary relation over two sets is a subset of their Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
* Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
. A Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
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
:''"Bounded" and "boundary" are distinct concepts; for the latter see boundary (topology). A circle in isolation is a boundaryless bounded set, while the half plane is unbounded yet has a boundary.
In mathematical analysis and related areas of m ...
. A bounded poset is one that has a least element and a greatest element.
* Bounded complete In the mathematical field of order theory, a partially ordered set is bounded complete if all of its subsets that have some upper bound also have a least upper bound. Such a partial order can also be called consistently or coherently complete ( Viss ...
. A poset is bounded complete In the mathematical field of order theory, a partially ordered set is bounded complete if all of its subsets that have some upper bound also have a least upper bound. Such a partial order can also be called consistently or coherently complete ( Viss ...
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 serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A c ...
. A chain is a totally ordered set or a totally ordered subset of a poset. See also .
* Chain complete
In mathematics, specifically order theory, a partially ordered set is chain-complete if every chain (order theory), chain in it has a least upper bound. It is ω-complete when every increasing sequence of elements (a type of countable chain) has a ...
. A partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
in which every chain
A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A c ...
has a least upper bound
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
.
* Closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S
:
Closure operators are de ...
. A closure operator on the poset ''P'' is a function ''C'' : ''P'' → ''P'' that is monotone, idempotent
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
, and satisfies ''C''(''x'') ≥ ''x'' for all ''x'' in ''P''.
* Compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
. 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 .
* Comparable
Comparable may refer to:
* Comparability, in mathematics
* Comparative
general linguistics, the comparative is a syntactic construction that serves to express a comparison between two (or more) entities or groups of entities in quality or degr ...
. Two elements ''x'' and ''y'' of a poset ''P'' are comparable if either ''x'' ≤ ''y'' or ''y'' ≤ ''x''.
* Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable grap ...
. The comparability graph of a poset (''P'', ≤) is the graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
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
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
. A Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
that is a complete lattice.
* Complete Heyting algebra
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra that is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and ...
. A Heyting algebra In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ''a'' → ''b'' of '' ...
that is a complete lattice is called a complete Heyting algebra. This notion coincides with the concepts ''frame'' and ''locale''.
* Complete lattice
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
. A complete lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
is a poset in which arbitrary (possibly infinite) joins (suprema) and meets (infima) exist.
* Complete partial order In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central rol ...
. A complete partial order, or cpo, is a directed complete partial order In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central ro ...
(q.v.) with least element.
* Complete relation. Synonym for ''Connected relation
In mathematics, a relation on a set is called connected or total if it relates (or "compares") all pairs of elements of the set in one direction or the other while it is called strongly connected if it relates pairs of elements.
As described ...
''.
* Complete semilattice. The notion of a ''complete semilattice'' is defined in different ways. As explained in the article on completeness (order theory) In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the te ...
, 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 In the mathematical field of order theory, a partially ordered set is bounded complete if all of its subsets that have some upper bound also have a least upper bound. Such a partial order can also be called consistently or coherently complete ( Viss ...
cpos, which is arguably the most complete class of posets that are not already complete lattices.
* Completely distributive lattice In the mathematical area of order theory, a completely distributive lattice is a complete lattice in which arbitrary joins distribute over arbitrary meets.
Formally, a complete lattice ''L'' is said to be completely distributive if, for any doubl ...
. A complete lattice is completely distributive if arbitrary joins distribute over arbitrary meets.
* Completion. A completion of a poset is an order-embedding In order theory, a branch of mathematics, an order embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order embeddings constitute a notion which is stric ...
of the poset in a complete lattice.
* Completion by cuts. Synonym of Dedekind–MacNeille completion
In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed ...
.
* Connected relation
In mathematics, a relation on a set is called connected or total if it relates (or "compares") all pairs of elements of the set in one direction or the other while it is called strongly connected if it relates pairs of elements.
As described ...
. 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 .
* 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''.
* cpo
CPO may refer to:
Occupations
* Certified Professional Organizer
* Certified Protection Officer, a professional certification for security officers from the International Foundation for Protection Officers
* Chief people officer, a corporate of ...
. See ''complete partial order''.
D
* dcpo. See ''directed complete partial order In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central ro ...
''.
* Dedekind–MacNeille completion
In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed ...
. The Dedekind–MacNeille completion of a partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
is the smallest complete lattice
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
that contains it.
* Dense order In mathematics, a partial order or total order < on a is said to be dense if, for all . A dense
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
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
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.
The number of derangements of ...
. A permutation of the elements of a set, such that no element appears in its original position.
* Directed set
In mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive and transitive binary relation \,\leq\, (that is, a preorder), with the additional property that every pair of elements has ...
. A non-empty
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other t ...
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 In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central ro ...
. 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'' ∧ (''y'' ∨ ''z'') = (''x'' ∧ ''y'') ∨ (''x'' ∧ ''z''). This condition is known to be equivalent to its order dual. A meet-semilattice
In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
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 may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
. Domain is a general term for objects like those that are studied in domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...
. If used, it requires further definition.
* Down-set. See ''lower set''.
* Dual. For a poset (''P'', ≤), the dual order ''P''''d'' = (''P'', ≥) is defined by setting ''x ≥ y'' if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
''y ≤ x''. The dual order of ''P'' is sometimes denoted by ''P''op, 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
Filter, filtering or filters may refer to:
Science and technology
Computing
* Filter (higher-order function), in functional programming
* Filter (software), a computer program to process a data stream
* Filter (video), a software component tha ...
. 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
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other t ...
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 is often a structural system that supports other components of a physical construction and/or steel frame that limits the construction's extent.
Frame and FRAME may also refer to:
Physical objects
In building construction
*Framing (con ...
. 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'' ∧ ''Y'' = holds. Frames are also known as ''locales'' and as complete Heyting algebra In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ''a'' → ''b'' of '' ...
s.
G
* Galois connection In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the funda ...
. 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
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
. 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 In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ''a'' → ''b'' of '' ...
. 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 In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the funda ...
, 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
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...
is a Heyting algebra.
* Hasse diagram
In order theory, 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. Concretely, for a partially ordered set ''(S, ≤)'' one represents ea ...
. 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
In the mathematical field of graph theory, a transitive reduction of a directed graph is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices , a (directed) path from to in exists i ...
.
* Homogeneous relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
. A homogeneous relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
on a set is a subset of Said differently, it is a binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
over and itself.
I
* Ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
. An ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
is a subset ''X'' of a poset ''P'' that is a directed lower set. The dual notion is called ''filter''.
* Incidence algebra In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set
and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural constructi ...
. The incidence algebra In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set
and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural constructi ...
of a poset is the associative algebra
In mathematics, an associative algebra ''A'' is an algebraic structure with compatible operations of addition, multiplication (assumed to be associative), and a scalar multiplication by elements in some field ''K''. The addition and multiplic ...
of all scalar-valued functions on intervals, with addition and scalar multiplication defined pointwise, and multiplication defined as a certain convolution; see incidence algebra In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set
and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural constructi ...
for the details.
* Infimum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest low ...
. 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 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 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 is a finite set.
* Inverse. See ''converse''.
* Irreflexive
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
. A relation
Relation or relations may refer to:
General uses
*International relations, the study of interconnection of politics, economics, and law on a global level
*Interpersonal relationship, association or acquaintance between two or more people
*Public ...
''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
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
. A lattice is a poset in which all non-empty finite joins (suprema) and meets (infima) exist.
* Least element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
. 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
In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extens ...
. 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 In mathematics, pointless topology, also called point-free topology (or pointfree topology) and locale theory, is an approach to topology that avoids mentioning points, and in which the lattices of open sets are the primitive notions. In this appr ...
.
* Locally finite poset. A partially ordered set ''P'' is ''locally finite'' if every interval 'a'', ''b''= is a finite set.
* Lower bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an eleme ...
. 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
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
. 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
A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A c ...
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
In mathematics, especially in order theory, a maximal element of a subset ''S'' of some preordered set is an element of ''S'' that is not smaller than any other element in ''S''. A minimal element of a subset ''S'' of some preordered set is defin ...
. 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 maxim''um'' element is necessarily maxim''al'', but the converse need not hold.
* Meet. See ''infimum''.
* Minimal element
In mathematics, especially in order theory, a maximal element of a subset ''S'' of some preordered set is an element of ''S'' that is not smaller than any other element in ''S''. A minimal element of a subset ''S'' of some preordered set is defin ...
. 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 minim''um'' element is necessarily minim''al'', but the converse need not hold.
* Monotone
Monotone refers to a sound, for example music or speech, that has a single unvaried tone. See: monophony.
Monotone or monotonicity may also refer to:
In economics
*Monotone preferences, a property of a consumer's preference ordering.
*Monotonic ...
. 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
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
, in the presence of total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
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 In order theory, a branch of mathematics, an order embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, order embeddings constitute a notion which is stric ...
. 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
In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be cons ...
. A mapping ''f'': ''P'' → ''Q'' between two posets ''P'' and ''Q'' is called an order isomorphism, if it is bijective
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
and both ''f'' and ''f''−1 are monotone function
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
s. Equivalently, an order isomorphism is a surjective ''order embedding''.
* Order-preserving
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
. See ''monotone''.
* Order-reversing. See ''antitone''.
P
* Partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
. A partial order is a binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
that is reflexive, antisymmetric, and 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
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
. A partially ordered set or for short, is a set together with a partial order on
* Poset. A partially ordered set.
* Preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
. A preorder is a binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
that is reflexive and transitive. Such orders may also be called or . The term is also used to denote an acyclic binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
(also called an ).
* Preordered set
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive relation, reflexive and Transitive relation, transitive. Preorders are more general than equivalence relations and (non-strict) partia ...
. A preordered set is a set together with a preorder on
* 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 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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. An ''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
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
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.
* Projection (operator). A self-map on a partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
that is monotone
Monotone refers to a sound, for example music or speech, that has a single unvaried tone. See: monophony.
Monotone or monotonicity may also refer to:
In economics
*Monotone preferences, a property of a consumer's preference ordering.
*Monotonic ...
and idempotent
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
under function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
. Projections play an important role in domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...
.
* Pseudo-complement. In a Heyting algebra In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ''a'' → ''b'' of '' ...
, the element ''x'' ⇒; ''0'' is called the pseudo-complement of ''x''. It is also given by sup, i.e. as the least upper bound of all elements ''y'' with ''y'' ∧ ''x'' = 0.
Q
* Quasiorder. See ''preorder''.
* Quasitransitive. A relation is quasitransitive if the relation on distinct elements is transitive. Transitive implies quasitransitive and quasitransitive implies acyclic.
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 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
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
''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
In mathematics, the concept of a residuated mapping arises in the theory of partially ordered sets. It refines the concept of a monotone function.
If ''A'', ''B'' are posets, a function ''f'': ''A'' → ''B'' is defined to be monotone if it is o ...
.
* Residuated mapping
In mathematics, the concept of a residuated mapping arises in the theory of partially ordered sets. It refines the concept of a monotone function.
If ''A'', ''B'' are posets, a function ''f'': ''A'' → ''B'' is defined to be monotone if it is o ...
. 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 chain
A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A c ...
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. A total order is scattered if it has no densely ordered subset.
* Scott-continuous In mathematics, given two partially ordered sets ''P'' and ''Q'', a Function (mathematics), function ''f'': ''P'' → ''Q'' between them is Scott-continuous (named after the mathematician Dana Scott) if it limit preserving function (order theory), p ...
. 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 has the supremum ''f''(sup ''D'') in ''Q''. Stated differently, a Scott-continuous function is one that preserves
Fruit preserves are preparations of fruits whose main preserving agent is sugar and sometimes acid, often stored in glass jars and used as a condiment or spread.
There are many varieties of fruit preserves globally, distinguished by the meth ...
all directed suprema. This is in fact equivalent to being continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous ...
with respect to the Scott topology
Scott may refer to:
Places Canada
* Scott, Quebec, municipality in the Nouvelle-Beauce regional municipality in Quebec
* Scott, Saskatchewan, a town in the Rural Municipality of Tramping Lake No. 380
* Rural Municipality of Scott No. 98, Saskat ...
on the respective posets.
* Scott domain
In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded-complete cpo. They are named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory. Scott domains a ...
. A Scott domain is a partially ordered set which is a bounded complete In the mathematical field of order theory, a partially ordered set is bounded complete if all of its subsets that have some upper bound also have a least upper bound. Such a partial order can also be called consistently or coherently complete ( Viss ...
algebraic cpo
CPO may refer to:
Occupations
* Certified Professional Organizer
* Certified Protection Officer, a professional certification for security officers from the International Foundation for Protection Officers
* Chief people officer, a corporate of ...
.
* Scott open. See ''Scott topology''.
* Scott topology. For a poset ''P'', a subset ''O'' is Scott-open if it is an upper set
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
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
In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
, the Scott topology.
* Semilattice
In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
. 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
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
. See .
* Strict partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
. A strict partial order is a homogeneous binary relation that is transitive, irreflexive
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
, and antisymmetric.
* Strict preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...
. See .
* Supremum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
. For a poset ''P'' and a subset ''X'' of ''P'', the least element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
in the set of upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an eleme ...
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 ''X''. The supremum of two elements may be written as sup 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∗ ''y'' implies that ''x'' R ''y'' or not ''y'' R ''x''.[
* Symmetric relation. A ]homogeneous relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) 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
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
. 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''.
* Total relation
In mathematics, a binary relation ''R'' ⊆ ''X''×''Y'' between two sets ''X'' and ''Y'' is total (or left total) if the source set ''X'' equals the domain . Conversely, ''R'' is called right total if ''Y'' equals the range .
When ''f'': ''X'' ...
. Synonym for ''Connected relation
In mathematics, a relation on a set is called connected or total if it relates (or "compares") all pairs of elements of the set in one direction or the other while it is called strongly connected if it relates pairs of elements.
As described ...
''.
* Transitive relation
In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive.
Definition
A homog ...
. A relation
Relation or relations may refer to:
General uses
*International relations, the study of interconnection of politics, economics, and law on a global level
*Interpersonal relationship, association or acquaintance between two or more people
*Public ...
''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
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
. The transitive closure R∗ of a relation R consists of all pairs ''x'',''y'' for which there cists a finite chain ''x'' R ''a'', ''a'' R ''b'', ..., ''z'' R ''y''.[
]
U
* Unit. The greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
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
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an eleme ...
. 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
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
. 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 , a valuation