In
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 ...
, a join-semilattice (or upper semilattice) is 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. A poset consists of a set together with a binary ...
that has a
join Join may refer to:
* Join (law), to include additional counts or additional defendants on an indictment
*In mathematics:
** Join (mathematics), a least upper bound of sets orders in lattice theory
** Join (topology), an operation combining two topo ...
(a
least upper bound) for any
nonempty finite subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
.
Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a
meet (or
greatest lower 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 ...
) 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
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
,
commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
,
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 ...
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
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 laws.
Order-theoretic definition
A
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
partially ordered by the
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 sets and is a new set of ordered pairs consisting of elements in and in ...
is a ''meet-semilattice'' if
: For all elements and of , the
greatest lower 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 ...
of the set exists.
The greatest lower bound of the set is called the
meet of and denoted
Replacing "greatest lower bound" with "
least upper bound" results in the dual concept of a ''join-semilattice''. The least upper bound of is called the
join Join may refer to:
* Join (law), to include additional counts or additional defendants on an indictment
*In mathematics:
** Join (mathematics), a least upper bound of sets orders in lattice theory
** Join (topology), an operation combining two topo ...
of and , denoted . Meet and join are
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
s on 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 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 ...
s between related posets — an approach of special interest for
category theoretic
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, categ ...
investigations of the concept.
Algebraic definition
A ''meet-semilattice'' is an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set o ...
consisting of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
with a
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
, called meet, such that for all members and of the following
identities hold:
;
Associativity
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
:
;
Commutativity
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
:
;
Idempotency:
A meet-semilattice
is bounded if includes an
identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
1 such that for all in
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 a
commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
,
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 ...
semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
; i.e., a commutative
band. A bounded semilattice is an idempotent commutative
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoid ...
.
A partial order is induced on a meet-semilattice by setting whenever . For a join-semilattice, the order is induced by setting whenever . In a bounded meet-semilattice, the identity 1 is the greatest element of Similarly, an identity element in a join semilattice is a least element.
Connection between the two definitions
An order theoretic meet-semilattice gives rise to a
binary operation
In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two.
More specifically, an internal binary op ...
such that is an algebraic meet-semilattice. Conversely, the meet-semilattice gives rise to 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 sets and is a new set of ordered pairs consisting of elements in and in ...
that partially orders in the following way: for all elements and in if and only if
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 the two 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
lattice is both a join- and a meet-semilattice. The interaction of these two semilattices via the
absorption law is what truly distinguishes a lattice from a semilattice.
* The
compact element {{Unreferenced, date=December 2008
In the mathematical area of order theory, the compact elements 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 alr ...
s of an algebraic
lattice, under the induced partial ordering, form a bounded join-semilattice.
* Any finite semilattice is bounded, by induction.
* A
totally ordered set
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) ...
is a
distributive lattice, hence in particular a meet-semilattice and join-semilattice: any two distinct elements have a greater and lesser one, which are their meet and join.
** A
well-ordered set is further a ''bounded'' join-semilattice, as the set as a whole has a least element, hence it is bounded.
*** The
natural numbers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
, with their usual order are a bounded join-semilattice, with least element 0, although they have no greatest element: they are the smallest infinite well-ordered set.
* Any single-rooted
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
(with the single root as the least element) of height
is a (generally unbounded) meet-semilattice. Consider for example the set of finite words over some alphabet, ordered by the
prefix order. It has a least element (the empty word), which is an annihilator element of the meet operation, but no greatest (identity) element.
* A
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 ...
is a meet-semilattice.
* Membership in any set can be taken as a
model of a semilattice with base set because a semilattice captures the essence of set
extensionality. Let denote & 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),
idempotence
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 ...
, (2). This semilattice is the
free semilattice In mathematics, in the area of order theory, a free lattice is the free object corresponding to a Lattice (order), lattice. As free objects, they have the universal property.
Formal definition
Any set (mathematics), set ''X'' may be used to generat ...
over It is not bounded by because a set is not a member of itself.
* Classical extensional
mereology
In logic, philosophy and related fields, mereology ( (root: , ''mere-'', 'part') and the suffix ''-logy'', 'study, discussion, science') is the study of parts and the wholes they form. Whereas set theory is founded on the membership relation bet ...
defines a join-semilattice, with join read as binary fusion. This semilattice is bounded from above by the world individual.
* Given a set the collection of partitions
of is a join-semilattice. In fact, the partial order is given by
if
such that
and the join of two partitions is given by
. This semilattice is bounded, with the least element being the singleton partition
.
Semilattice morphisms
The above algebraic definition of a semilattice suggests a notion of
morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
between two semilattices. Given two join-semilattices and , a
homomorphism
In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...
of (join-) semilattices is a function such that
:
Hence is just a homomorphism of the two
semigroups associated with each semilattice. If and both include a least element 0, then should also be a
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
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
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 ...
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
equivalence between the category
of join-semilattices with zero with
-homomorphisms and the category
of
algebraic lattices with
compactness
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
-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 {{Unreferenced, date=December 2008
In the mathematical area of order theory, the compact elements 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 alr ...
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. A join-semilattice is distributive if for all and with there exist and such that Distributive meet-semilattices are defined dually. These definitions are justified by the fact that any distributive join-semilattice in which binary meets exist is a distributive lattice. See the entry
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. Most of these apply to partially ordered sets that are at least lattices, but the concep ...
.
A join-semilattice is distributive if and only if the lattice of its
ideals (under inclusion) is distributive.
Complete semilattices
Nowadays, the term "complete semilattice" has no generally accepted meaning, and various mutually inconsistent definitions exist. If completeness is taken to require the existence of all infinite joins, or all infinite meets, whichever the case may be, as well as finite ones, this immediately leads to partial orders that are in fact
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.'' ...
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) 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 ter ...
.
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
In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...
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 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 ...
. 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
Director may refer to:
Literature
* ''Director'' (magazine), a British magazine
* ''The Director'' (novel), a 1971 novel by Henry Denker
* ''The Director'' (play), a 2000 play by Nancy Hasty
Music
* Director (band), an Irish rock band
* ''D ...
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
Algebraic may refer to any subject related to algebra in mathematics and related branches like algebraic number theory and algebraic topology. The word algebra itself has several meanings.
Algebraic may also refer to:
* Algebraic data type, a data ...
cpos are studied as
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 ...
s. Hence Scott domains have been called ''algebraic semilattices''.
Cardinality-restricted notions of completeness for semilattices have been rarely considered in the literature.
complete semilattices
on Planetmath.org
Free semilattices
This section presupposes some knowledge of category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
. In various situations, free semilattices exist. For example, the forgetful functor In mathematics, in the area of category theory, a forgetful functor (also known as a stripping functor) 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given sign ...
from the category of join-semilattices (and their homomorphisms) to the category
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce) ...
of sets (and functions) admits a left adjoint. Therefore, the free join-semilattice over a set is constructed by taking the collection of all non-empty ''finite'' subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
s of ordered by subset inclusion. Clearly, can be embedded into by a mapping that takes any element in to the singleton set Then any function from a to a join-semilattice (more formally, to the underlying set of ) induces a unique homomorphism between the join-semilattices and such that Explicitly, is given by Now the obvious uniqueness of suffices to obtain the required adjunction—the morphism-part of the functor can be derived from general considerations (see adjoint functors
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...
). 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.
See also
* − generalization of join semilattice
*
*
Notes
References
*
*
It is often the case that standard treatments of lattice theory define a semilattice, if that, and then say no more. See the references in the entries order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
and lattice theory
A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bou ...
. Moreover, there is no literature on semilattices of comparable magnitude to that on semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
s.
External links
* Jipsen's algebra structures page
Semilattices.
{{Authority control
Lattice theory
Algebraic structures