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 (mathematics), set. A poset consists of a set toget ...
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
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 any
nonempty
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 ...
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked ...
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), 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 ...
.
Dually Dually may refer to:
*Dualla, County Tipperary, a village in Ireland
*A pickup truck with dual wheels on the rear axle
* DUALLy, s platform for architectural languages interoperability
* Dual-processor
See also
* Dual (disambiguation)
Dual or ...
, a meet-semilattice (or lower semilattice) is a partially ordered set which has a
meet
Meet may refer to:
People with the name
* Janek Meet (born 1974), Estonian footballer
* Meet Mukhi (born 2005), Indian child actor
Arts, entertainment, and media
* ''Meet'' (TV series), an early Australian television series which aired on ABC du ...
(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 l ...
) for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the
inverse order
In the mathematical area of order theory, every partially ordered set ''P'' gives rise to a dual (or opposite) partially ordered set which is often denoted by ''P''op or ''P'd''. This dual order ''P''op is defined to be the same set, but with th ...
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 f ...
,
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 o ...
,
idempotent
Idempotence (, ) is the property of certain operation (mathematics), 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 ...
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
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 ornam ...
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
In algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.
Two binary operations, ¤ and ⁂, are said to be connected by the absorption law if:
:''a'' ¤ (''a'' ⁂ ''b'') = ''a'' ⁂ (''a'' ¤ ''b ...
s.
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
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 ...
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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
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 l ...
of the set exists.
The greatest lower bound of the set is called the
meet
Meet may refer to:
People with the name
* Janek Meet (born 1974), Estonian footballer
* Meet Mukhi (born 2005), Indian child actor
Arts, entertainment, and media
* ''Meet'' (TV series), an early Australian television series which aired on ABC du ...
of and denoted
Replacing "greatest lower bound" with "
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 low ...
" 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
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
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
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 ...
, the join of the empty set.
Dually Dually may refer to:
*Dualla, County Tipperary, a village in Ireland
*A pickup truck with dual wheels on the rear axle
* DUALLy, s platform for architectural languages interoperability
* Dual-processor
See also
* Dual (disambiguation)
Dual or ...
, a meet-semilattice is bounded if it has a
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 ...
, 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 of ...
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 f ...
:
;
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
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 ...
:
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 o ...
,
idempotent
Idempotence (, ) is the property of certain operation (mathematics), 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 ...
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
Band or BAND may refer to:
Places
*Bánd, a village in Hungary
*Band, Iran, a village in Urmia County, West Azerbaijan Province, Iran
*Band, Mureș, a commune in Romania
* Band-e Majid Khan, a village in Bukan County, West Azerbaijan Province, I ...
. 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.
Monoids ...
.
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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
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
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 ornam ...
is both a join- and a meet-semilattice. The interaction of these two semilattices via the
absorption law
In algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.
Two binary operations, ¤ and ⁂, are said to be connected by the absorption law if:
:''a'' ¤ (''a'' ⁂ ''b'') = ''a'' ⁂ (''a'' ¤ ''b ...
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
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 ornam ...
, 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
In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set uni ...
, 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
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-ord ...
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 n ...
, 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 In mathematics, especially order theory, a prefix ordered set generalizes the intuitive concept of a tree by introducing the possibility of continuous progress and continuous branching. Natural prefix orders often occur when considering dynamical sy ...
. 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
A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
of a semilattice with base set because a semilattice captures the essence of set
extensionality
In logic, extensionality, or extensional equality, refers to principles that judge objects to be equal if they have the same external properties. It stands in contrast to the concept of intensionality, which is concerned with whether the internal ...
. 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. As free objects, they have the universal property.
Formal definition
Any set ''X'' may be used to generate the free semilattice ''FX''. The ...
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 a ...
between two semilattices. Given two join-semilattices and , a
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
of (join-) semilattices is a function such that
:
Hence is just a homomorphism of the two
semigroups
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'', ...
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.
Monoids ...
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
Equivalence or Equivalent may refer to:
Arts and entertainment
*Album-equivalent unit, a measurement unit in the music industry
*Equivalence class (music)
*''Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre
*'' Equival ...
between the category
of join-semilattices with zero with
-homomorphisms and the category
of
algebraic lattice {{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 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 te ...
.
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 structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
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 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 ...
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 ...
. 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
* ''Di ...
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 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 ...
, where bounded complete
algebraic 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, cate ...
. In various situations, free
Free may refer to:
Concept
* Freedom, having the ability to do something, without having to obey anyone/anything
* Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism
* Emancipate, to procur ...
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 signa ...
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
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 ...
. Therefore, the free join-semilattice over a set is constructed by taking the collection of all non-empty ''finite'' subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), 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 ...
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 boun ...
. 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