Semilattice
Encyclopedia
In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set
which 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 meet
(or greatest lower bound) for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.
Semilattices can also be defined algebraically
: join and meet are associative
, commutative
, idempotent binary operation
s, and any such operation induces a partial order (and the respective inverse order) such that the result of the operation for any two elements is the least upper bound (or greatest lower bound) of the elements with respect to this partial order.
A lattice
is a partially ordered set that is both a meet- and join-semilattice with respect to the same partial order. Algebraically, a lattice is a set with two associative, commutative idempotent binary operations linked by corresponding absorption law
s.
by the binary relation
≤ is a meet-semilattice if
The greatest lower bound of the set {x, y} is called the meet
of x and y, denoted .
Replacing "greatest lower bound" with "least upper bound
" results in the dual concept of a join-semilattice. The least upper bound of {x, y} is called the join of x and y, denoted . Meet and join are binary operation
s on S. A simple induction
argument shows that the existence of all possible pairwise suprema (infima), as per the definition, implies the existence of all non-empty finite suprema (infima).
A join-semilattice is bounded if it has a least element, the join of the empty set. Dually
, a meet-semilattice is bounded if it has a greatest element, the meet of the empty set.
Other properties may be assumed; see the article on completeness in order theory
for more discussion on this subject. That article also discusses how we may rephrase the above definition in terms of the existence of suitable Galois connection
s between related posets — an approach of special interest for category theoretic
investigations of the concept.
consisting of a set S with a binary operation
∧, called meet, such that for all members x, y, and z of S, the following identities
hold:
Associativity
: x ∧ (y ∧ z) = (x ∧ y) ∧ z
Commutativity
: x ∧ y = y ∧ x
Idempotency: x ∧ x = x
A meet-semilattice is bounded if S includes an identity element
1 such that x ∧ 1 = x for all x in S.
If the symbol ∨, called join, replaces ∧ in the definition just given, the structure is called a join-semilattice. One can be ambivalent about the particular choice of symbol for the operation, and speak simply of semilattices.
A semilattice is an idempotent, commutative
semigroup
. Alternatively, a semilattice is a commutative band
. A bounded semilattice is an idempotent commutative monoid
.
A partial order is induced on a meet-semilattice by setting whenever x∧y=x. For a join-semilattice, the order is induced by setting whenever x∨y=y. In a bounded meet-semilattice, the identity 1 is the greatest element of S. Similarly, an identity element in a join semilattice is a least element.
∧ such that is an algebraic meet-semilattice. Conversely, the meet-semilattice gives rise to a binary relation
≤ that partially orders S in the following way: for all elements x and y in S, x ≤ y if and only if x = x ∧ y.
The relation ≤ introduced in this way defines a partial ordering from which the binary operation ∧ may be recovered. Conversely, the order induced by the algebraically defined semilattice coincides with that induced by ≤.
Hence both definitions may be used interchangeably, depending on which one is more convenient for a particular purpose. A similar conclusion holds for join-semilattices and the dual ordering ≥.
between two semilattices. Given two join-semilattices and , a homomorphism
of (join-) semilattices is a function f: S → T such that
Hence f is just a homomorphism of the two semigroups associated with each semilattice. If S and T both include a least element 0, then f should also be a monoid
homomorphism, i.e. we additionally require that
In the order-theoretic formulation, these conditions just state that a homomorphism of join-semilattices is a function that preserves binary joins and least elements, if such there be. The obvious dual—replacing ∧ with ∨ and 0 with 1—transforms this definition of a join-semilattice homomorphism into its meet-semilattice equivalent.
Note that any semilattice homomorphism is necessarily monotone with respect to the associated ordering relation. For an explanation see the entry preservation of limits.
between the category
of join-semilattices with zero with 
-homomorphisms and the category 
of algebraic lattices with compactness
-preserving complete join-homomorphisms, as follows. With a join-semilattice
with zero, we associate its ideal lattice 
. With a 
-homomorphism 
of 
-semilattices, we associate the map 
, that with any ideal 
of 
associates the ideal of 
generated by 
. This defines a functor 
. Conversely, with every algebraic lattice 
we associate the 
-semilattice 
of all compact element
s of
, and with every compactness-preserving complete join-homomorphism 
between algebraic lattices we associate the restriction 
. This defines a functor 
. The pair 
defines a category equivalence between 
and 
.
.
s. For why the existence of all possible infinite joins entails the existence of all possible infinite meets (and vice versa), see the entry completeness (order theory)
.
Nevertheless, the literature on occasion still takes complete join- or meet-semilattices to be complete lattices. In this case, "completeness" denotes a restriction on the scope of the homomorphism
s. Specifically, a complete join-semilattice requires that the homomorphisms preserve all joins, but contrary to the situation we find for completeness properties, this does not require that homomorphisms preserve all meets. On the other hand, we can conclude that every such mapping is the lower adjoint of some Galois connection
. The corresponding (unique) upper adjoint will then be a homomorphism of complete meet-semilattices. This gives rise to a number of useful categorical dualities between the categories of all complete semilattices with morphisms preserving all meets or joins, respectively.
Another usage of "complete meet-semilattice" refers to a bounded complete cpo
. A complete meet-semilattice in this sense is arguably the "most complete" meet-semilattice that is not necessarily a complete lattice. Indeed, a complete meet-semilattice has all non-empty meets (which is equivalent to being bounded complete) and all directed joins. If such a structure has also a greatest element (the meet of the empty set), it is also a complete lattice. Thus a complete semilattice turns out to be "a complete lattice possibly lacking a top". This definition is of interest specifically in domain theory
, where bounded complete algebraic cpos are studied as Scott domain
s. Hence Scott domains have been called algebraic semilattices.
. In various situations, free
semilattices exist. For example, the forgetful functor
from the category of join-semilattices (and their homomorphisms) to the category
of sets (and functions) admits a left adjoint
. Therefore, the free join-semilattice F(S) over a set S is constructed by taking the collection of all non-empty finite subset
s of S, ordered by subset inclusion. Clearly, S can be embedded into F(S) by a mapping e that takes any element s in S to the singleton set {s}. Then any function f from a S to a join-semilattice T (more formally, to the underlying set of T) induces a unique homomorphism f' between the join-semilattices F(S) and T, such that f = f' o e. Explicitly, f' is given by f' (A) =
{f(s) | s in S}. Now the obvious uniqueness of f' suffices to obtain the required adjunction—the morphism-part of the functor F can be derived from general considerations (see adjoint functors
). The case of free meet-semilattices is dual, using the opposite subset inclusion as an ordering. For join-semilattices with bottom, we just add the empty set to the above collection of subsets.
In addition, semilattices often serve as generators for free objects within other categories. Notably, both the forgetful functors from the category of frames
and frame-homomorphisms, and from the category of distributive lattices and lattice-homomorphisms, have a left adjoint.
Partially ordered set
In mathematics, especially order theory, a partially ordered set 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 relation that indicates that, for certain pairs of elements in the...
which has a join (a least upper bound) for any nonempty finite subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
. Dually
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
, a meet-semilattice (or lower semilattice) is a partially ordered set which has a meet
Meet (mathematics)
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
(or greatest lower bound) for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.
Semilattices can also be defined algebraically
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
: join and meet are associative
Associativity
In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
, commutative
Commutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
, idempotent binary operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
s, and any such operation induces a partial order (and the respective inverse order) such that the result of the operation for any two elements is the least upper bound (or greatest lower bound) of the elements with respect to this partial order.
A lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
is a partially ordered set that is both a meet- and join-semilattice with respect to the same partial order. Algebraically, a lattice is a set with two associative, commutative idempotent binary operations linked by corresponding absorption law
Absorption law
In algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.Two binary operations, say ¤ and *, are said to be connected by the absorption law if:...
s.
Order-theoretic definition
A set S partially orderedPartially ordered set
In mathematics, especially order theory, a partially ordered set 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 relation that indicates that, for certain pairs of elements in the...
by the binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
≤ is a meet-semilattice if
- For all elements x and y of S, the greatest lower boundInfimumIn mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
of the set {x, y} exists.
The greatest lower bound of the set {x, y} is called the meet
Meet (mathematics)
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
of x and y, denoted .
Replacing "greatest lower bound" with "least upper bound
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
" results in the dual concept of a join-semilattice. The least upper bound of {x, y} is called the join of x and y, denoted . Meet and join are binary operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
s on S. A simple induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
argument shows that the existence of all possible pairwise suprema (infima), as per the definition, implies the existence of all non-empty finite suprema (infima).
A join-semilattice is bounded if it has a least element, the join of the empty set. Dually
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
, a meet-semilattice is bounded if it has a greatest element, the meet of the empty set.
Other properties may be assumed; see the article on completeness in order theory
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 . A special use of the term refers to complete partial orders or complete lattices...
for more discussion on this subject. That article also discusses how we may rephrase the above definition in terms of the existence of suitable Galois connection
Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...
s between related posets — an approach of special interest for category theoretic
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
investigations of the concept.
Algebraic definition
A "meet-semilattice" is an algebraic structureAlgebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
consisting of a set S with a binary operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
∧, called meet, such that for all members x, y, and z of S, the following identities
Identity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...
hold:
Associativity
Associativity
In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
: x ∧ (y ∧ z) = (x ∧ y) ∧ z
Commutativity
Commutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
: x ∧ y = y ∧ x
Idempotency: x ∧ x = x
A meet-semilattice is bounded if S includes an identity element
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
1 such that x ∧ 1 = x for all x in S.
If the symbol ∨, called join, replaces ∧ in the definition just given, the structure is called a join-semilattice. One can be ambivalent about the particular choice of symbol for the operation, and speak simply of semilattices.
A semilattice is an idempotent, commutative
Commutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
semigroup
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
. Alternatively, a semilattice is a commutative band
Band (algebra)
In mathematics, a band is a semigroup in which every element is idempotent . Bands were first studied and named by ; the lattice of varieties of bands was described independently in the early 1970s by Biryukov, Fennemore and Gerhard...
. A bounded semilattice is an idempotent commutative monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
.
A partial order is induced on a meet-semilattice by setting whenever x∧y=x. For a join-semilattice, the order is induced by setting whenever x∨y=y. In a bounded meet-semilattice, the identity 1 is the greatest element of S. Similarly, an identity element in a join semilattice is a least element.
Connection between both definitions
An order theoretic meet-semilattice gives rise to a binary operationBinary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
∧ such that is an algebraic meet-semilattice. Conversely, the meet-semilattice gives rise to a binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
≤ that partially orders S in the following way: for all elements x and y in S, x ≤ y if and only if x = x ∧ y.
The relation ≤ introduced in this way defines a partial ordering from which the binary operation ∧ may be recovered. Conversely, the order induced by the algebraically defined semilattice coincides with that induced by ≤.
Hence both definitions may be used interchangeably, depending on which one is more convenient for a particular purpose. A similar conclusion holds for join-semilattices and the dual ordering ≥.
Examples
Semilattices are employed to construct other order structures, or in conjunction with other completeness properties.- A latticeLattice (order)In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
is both a join- and a meet-semilattice. The interaction of these two semilattices via the absorption lawAbsorption lawIn algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.Two binary operations, say ¤ and *, are said to be connected by the absorption law if:...
is what truly distinguishes a lattice from a semilattice. - The compact elementCompact elementIn the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
s of an algebraic latticeLattice (order)In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
, under the induced partial ordering, form a bounded join-semilattice. - Any tree structureTree structureA tree structure is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the...
(with the root as the least element) is a meet-semilattice. Consider for example the set of finite words over some alphabet, ordered by the prefix ordering. It has a least but no greatest element: the root is the meet of all other elements. - A Scott domainScott domainIn the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded complete cpo. It has been named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory...
is a meet-semilattice. - Membership in any set L can be taken as a modelModel theoryIn mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
of a semilattice with base set L, because a semilattice captures the essence of set extensionalityExtensionalityIn logic, extensionality, or extensional equality refers to principles that judge objects to be equal if they have the same external properties...
. Let a∧b denote a∈L & b∈L. Two sets differing only in one or both of the:
- Order in which their members are listed;
- Multiplicity of one or more members,
- are in fact the same set. Commutativity and associativity of ∧ assure (1), idempotenceIdempotenceIdempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application...
, (2). This semilattice is the free semilattice over L. It is not bounded by L, because a set is not a member of itself.- Classical extensional mereologyMereologyIn philosophy and mathematical logic, mereology treats parts and the wholes they form...
defines a join-semilattice, with join read as binary fusion. This semilattice is bounded from above by the world individual.
- Classical extensional mereology
Semilattice morphisms
The above algebraic definition of a semilattice suggests a notion of morphismMorphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
between two semilattices. Given two join-semilattices and , a homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
of (join-) semilattices is a function f: S → T such that
- f(x ∨ y) = f(x) ∨ f(y).
Hence f is just a homomorphism of the two semigroups associated with each semilattice. If S and T both include a least element 0, then f should also be a monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
homomorphism, i.e. we additionally require that
- f(0) = 0.
In the order-theoretic formulation, these conditions just state that a homomorphism of join-semilattices is a function that preserves binary joins and least elements, if such there be. The obvious dual—replacing ∧ with ∨ and 0 with 1—transforms this definition of a join-semilattice homomorphism into its meet-semilattice equivalent.
Note that any semilattice homomorphism is necessarily monotone with respect to the associated ordering relation. For an explanation see the entry preservation of limits.
Equivalence with algebraic lattices
There is a well-known equivalenceEquivalence of categories
In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...
between the category
of join-semilattices with zero with -homomorphisms and the category of algebraic lattices with compactnessCompact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
-preserving complete join-homomorphisms, as follows. With a join-semilattice
with zero, we associate its ideal lattice . With a -homomorphism of -semilattices, we associate the map , that with any ideal of associates the ideal of generated by . This defines a functor . Conversely, with every algebraic lattice we associate the -semilattice of all compact elementCompact element
In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element....
s of
, and with every compactness-preserving complete join-homomorphism between algebraic lattices we associate the restriction . This defines a functor . The pair defines a category equivalence between and .Distributive semilattices
Surprisingly, there is a notion of "distributivity" applicable to semilattices, even though distributivity conventionally requires the interaction of two binary operations. This notion requires but a single operation, and generalizes the distributivity condition for lattices. See the entry distributivity (order theory)Distributivity (order theory)
In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima...
.
Complete semilattices
Nowadays, the term "complete semilattice" has no generally accepted meaning, and various inconsistent definitions exist. If completeness is taken to require the existence of all infinite joins and meets, whichever the case may be, as well as finite ones, this immediately leads to partial orders that are in fact complete latticeComplete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
s. For why the existence of all possible infinite joins entails the existence of all possible infinite meets (and vice versa), see the entry completeness (order theory)
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 . A special use of the term refers to complete partial orders or complete lattices...
.
Nevertheless, the literature on occasion still takes complete join- or meet-semilattices to be complete lattices. In this case, "completeness" denotes a restriction on the scope of the homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
s. Specifically, a complete join-semilattice requires that the homomorphisms preserve all joins, but contrary to the situation we find for completeness properties, this does not require that homomorphisms preserve all meets. On the other hand, we can conclude that every such mapping is the lower adjoint of some Galois connection
Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets . The same notion can also be defined on preordered sets or classes; this article presents the common case of posets. Galois connections generalize the correspondence...
. The corresponding (unique) upper adjoint will then be a homomorphism of complete meet-semilattices. This gives rise to a number of useful categorical dualities between the categories of all complete semilattices with morphisms preserving all meets or joins, respectively.
Another usage of "complete meet-semilattice" refers to a bounded complete cpo
Complete partial order
In mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties...
. A complete meet-semilattice in this sense is arguably the "most complete" meet-semilattice that is not necessarily a complete lattice. Indeed, a complete meet-semilattice has all non-empty meets (which is equivalent to being bounded complete) and all directed joins. If such a structure has also a greatest element (the meet of the empty set), it is also a complete lattice. Thus a complete semilattice turns out to be "a complete lattice possibly lacking a top". This definition is of interest specifically in domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
, where bounded complete algebraic cpos are studied as Scott domain
Scott domain
In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded complete cpo. It has been named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory...
s. Hence Scott domains have been called algebraic semilattices.
Free semilattices
This section presupposes some knowledge of category theoryCategory theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
. In various situations, free
Free object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure . It also has a formulation in terms of category theory, although this is in yet more abstract terms....
semilattices exist. For example, the forgetful functor
Forgetful functor
In mathematics, in the area of category theory, a forgetful functor is a type of functor. The nomenclature is suggestive of such a functor's behaviour: given some object with structure as input, some or all of the object's structure or properties is 'forgotten' in the output...
from the category of join-semilattices (and their homomorphisms) to the category
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
of sets (and functions) admits a left adjoint
Adjoint functors
In mathematics, adjoint functors are pairs of functors which stand in a particular relationship with one another, called an adjunction. The relationship of adjunction is ubiquitous in mathematics, as it rigorously reflects the intuitive notions of optimization and efficiency...
. Therefore, the free join-semilattice F(S) over a set S is constructed by taking the collection of all non-empty finite subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s of S, ordered by subset inclusion. Clearly, S can be embedded into F(S) by a mapping e that takes any element s in S to the singleton set {s}. Then any function f from a S to a join-semilattice T (more formally, to the underlying set of T) induces a unique homomorphism f' between the join-semilattices F(S) and T, such that f = f' o e. Explicitly, f' is given by f' (A) =
{f(s) | s in S}. Now the obvious uniqueness of f' suffices to obtain the required adjunction—the morphism-part of the functor F can be derived from general considerations (see adjoint functorsAdjoint functors
In mathematics, adjoint functors are pairs of functors which stand in a particular relationship with one another, called an adjunction. The relationship of adjunction is ubiquitous in mathematics, as it rigorously reflects the intuitive notions of optimization and efficiency...
). The case of free meet-semilattices is dual, using the opposite subset inclusion as an ordering. For join-semilattices with bottom, we just add the empty set to the above collection of subsets.
In addition, semilattices often serve as generators for free objects within other categories. Notably, both the forgetful functors from the category of frames
Complete Heyting algebra
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the category CHey, the category Loc of locales, and its opposite, the category Frm of frames...
and frame-homomorphisms, and from the category of distributive lattices and lattice-homomorphisms, have a left adjoint.
External links
- Jipsen's algebra structures page: Semilattices.