Transitive binary relations v t e
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder(Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all${\displaystyle a,b}$ and${\displaystyle S\ne \varnothing :}$ ${\displaystyle \begin{array}{r}minS\\ \text{exists}\end{array}}$ ${\displaystyle \begin{array}{r}a\vee b\\ \text{exists}\end{array}}$ ${\displaystyle \begin{array}{r}a\wedge b\\ \text{exists}\end{array}}$ ${\displaystyle aRa}$ ${\displaystyle \text{not }aRa}$ ${\displaystyle \begin{array}{r}aRb\Rightarrow \\ \text{not }bRa\end{array}}$
Y indicates that the column's property is always true for the row's term (at the very left), while✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated byY in the "Symmetric" column and✗ in the "Antisymmetric" column, respectively. All definitions tacitly require thehomogeneous relation${\displaystyle R}$ betransitive: for all${\displaystyle a,b,c,}$ if${\displaystyle aRb}$ and${\displaystyle bRc}$ then${\displaystyle aRc.}$ A term's definition may require additional properties that are not listed in this table.

Inmathematics, ajoin-semilattice (orupper semilattice) is apartially ordered set that has ajoin (aleast upper bound) for anynonemptyfinitesubset.Dually, ameet-semilattice (orlower semilattice) is a partially ordered set which has ameet (orgreatest lower bound) for any nonempty finite subset. Every join-semilattice is a meet-semilattice in theinverse order and vice versa.

Semilattices can also be definedalgebraically: join and meet areassociative,commutative,idempotentbinary operations, 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.

Alattice 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 correspondingabsorption laws.

AsetSpartially ordered by thebinary relation≤ is ameet-semilattice if

For all elementsx andy ofS, thegreatest lower bound of the set{x,y} exists.

The greatest lower bound of the set{x,y} is called themeet ofx andy, denotedx ∧y.

Replacing "greatest lower bound" with "least upper bound" results in the dual concept of ajoin-semilattice. The least upper bound of{x,y} is called thejoin ofx andy, denotedx ∨y. Meet and join arebinary operations onS. A simpleinduction 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 isbounded if it has aleast element, the join of the empty set.Dually, a meet-semilattice isbounded if it has agreatest element, the meet of the empty set.

Other properties may be assumed; see the article oncompleteness 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 suitableGalois connections between related posets—an approach of special interest forcategory theoretic investigations of the concept.

Ameet-semilattice is analgebraic structure${\displaystyle ⟨S,\wedge ⟩}$ consisting of asetS with abinary operation∧, calledmeet, such that for all membersx,y, andz ofS, the followingidentities hold:

Associativity

x ∧ (y ∧z) = (x ∧y) ∧z

Commutativity

x ∧y =y ∧x

Idempotency

x ∧x =x

A meet-semilattice${\displaystyle ⟨S,\wedge ⟩}$ isbounded ifS includes anidentity element 1 such thatx ∧ 1 =x for allx inS.

If the symbol∨, calledjoin, replaces∧ in the definition just given, the structure is called ajoin-semilattice. One can be ambivalent about the particular choice of symbol for the operation, and speak simply ofsemilattices.

A semilattice is acommutative,idempotentsemigroup; i.e., a commutativeband. A bounded semilattice is an idempotent commutativemonoid.

A partial order is induced on a meet-semilattice by settingx ≤y wheneverx ∧y =x. For a join-semilattice, the order is induced by settingx ≤y wheneverx ∨y =y. In a bounded meet-semilattice, the identity 1 is the greatest element ofS. Similarly, an identity element in a join semilattice is a least element.

An order theoretic meet-semilattice⟨S, ≤⟩ gives rise to abinary operation∧ such that⟨S, ∧⟩ is an algebraic meet-semilattice. Conversely, the meet-semilattice⟨S, ∧⟩ gives rise to abinary relation≤ that partially ordersS in the following way: for all elementsx andy inS,x ≤y if and only ifx =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⟨S, ∧⟩ 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 ≥.

Semilattices are employed to construct other order structures, or in conjunction with other completeness properties.

• Alattice is both a join- and a meet-semilattice. The interaction of these two semilattices via theabsorption law is what truly distinguishes a lattice from a semilattice.
• Thecompact elements of an algebraiclattice, under the induced partial ordering, form a bounded join-semilattice.
• By induction on the number of elements, any non-empty finite meet semilattice has a least element and any non-empty finite join semilattice has a greatest element. (In neither case will the semilattice necessarily be bounded.)
• Atotally ordered set is adistributive 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.
  • Awell-ordered set is further abounded join-semilattice, as the set as a whole has a least element, hence it is bounded.
    • Thenatural numbers${\displaystyle \mathbb{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-rootedtree (with the single root as the least element) of height${\displaystyle \le \omega }$ is a (generally unbounded) meet-semilattice. Consider for example the set of finite words over some alphabet, ordered by theprefix order. It has a least element (the empty word), which is an annihilator element of the meet operation, but no greatest (identity) element.
• AScott domain is a meet-semilattice.
• Membership in any setL can be taken as amodel of a semilattice with base setL, because a semilattice captures the essence of setextensionality. Leta ∧b denotea ∈L &b ∈L. Two sets differing only in one or both of the:

1. Order in which their members are listed;
2. Multiplicity of one or more members,

are in fact the same set. Commutativity and associativity of∧ assure (1),idempotence, (2). This semilattice is thefree semilattice overL. It is not bounded byL, because a set is not a member of itself.

• Classical extensionalmereology defines a join-semilattice, with join read as binary fusion. This semilattice is bounded from above by the world individual.
• Given a setS, the collection of partitions${\displaystyle \xi }$ ofS is a join-semilattice. In fact, the partial order is given by${\displaystyle \xi \le \eta }$ if${\displaystyle \mathrm{\forall }Q\in \eta ,\mathrm{\exists }P\in \xi }$ such that${\displaystyle Q\subset P}$ and the join of two partitions is given by${\displaystyle \xi \vee \eta =\{P\cap Q\mid P\in \xi \wedge Q\in \eta \}}$. This semilattice is bounded, with the least element being the singleton partition${\displaystyle \{S\}}$.

The above algebraic definition of a semilattice suggests a notion ofmorphism between two semilattices. Given two join-semilattices(S, ∨) and(T, ∨), ahomomorphism of (join-) semilattices is a functionf:S →T such that

f(x ∨y) =f(x) ∨f(y).

Hencef is just a homomorphism of the twosemigroups associated with each semilattice. IfS andT both include a least element 0, thenf should also be amonoid 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.

Any semilattice homomorphism is necessarilymonotone with respect to the associated ordering relation.

There is a well-knownequivalence between the category${\displaystyle \mathcal{S}}$ of join-semilattices with zero with${\displaystyle (\vee ,0)}$-homomorphisms and the category${\displaystyle \mathcal{A}}$ ofalgebraic lattices withcompactness-preserving complete join-homomorphisms, as follows. With a join-semilattice${\displaystyle S}$ with zero, we associate its ideal lattice${\displaystyle \mathrm{Id}S}$. With a${\displaystyle (\vee ,0)}$-homomorphism${\displaystyle f:S\to T}$ of${\displaystyle (\vee ,0)}$-semilattices, we associate the map${\displaystyle \mathrm{Id}f:\mathrm{Id}S\to \mathrm{Id}T}$, that with any ideal${\displaystyle I}$ of${\displaystyle S}$ associates the ideal of${\displaystyle T}$ generated by${\displaystyle f(I)}$. This defines a functor${\displaystyle \mathrm{Id}:\mathcal{S}\to \mathcal{A}}$. Conversely, with every algebraic lattice${\displaystyle A}$ we associate the${\displaystyle (\vee ,0)}$-semilattice${\displaystyle K(A)}$ of allcompact elements of${\displaystyle A}$, and with every compactness-preserving complete join-homomorphism${\displaystyle f:A\to B}$ between algebraic lattices we associate the restriction${\displaystyle K(f):K(A)\to K(B)}$. This defines a functor${\displaystyle K:\mathcal{A}\to \mathcal{S}}$. The pair${\displaystyle (\mathrm{Id},K)}$ defines a category equivalence between${\displaystyle \mathcal{S}}$ and${\displaystyle \mathcal{A}}$.

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 isdistributive if for alla,b, andx withx ≤a ∨b there exista' ≤a andb' ≤b such thatx =a' ∨b'. 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 entrydistributivity (order theory).

A join-semilattice is distributive if and only if the lattice of itsideals (under inclusion) is distributive.

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 factcomplete lattices. For why the existence of all possible infinite joins entails the existence of all possible infinite meets (and vice versa), see the entrycompleteness (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 thehomomorphisms. 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 someGalois connection. The corresponding (unique) upper adjoint will then be a homomorphism of complete meet-semilattices. This gives rise to a number of usefulcategorical dualities between the categories of all complete semilattices with morphisms preserving all meets or joins, respectively.

Another usage of "complete meet-semilattice" refers to abounded completecpo. 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 allnon-empty meets (which is equivalent to being bounded complete) and alldirected 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 indomain theory, where bounded completealgebraic cpos are studied asScott domains. Hence Scott domains have been calledalgebraic semilattices.

Cardinality-restricted notions of completeness for semilattices have been rarely considered in the literature.^[1]

This section presupposes some knowledge ofcategory theory. In various situations,free semilattices exist. For example, theforgetful functor from the category of join-semilattices (and their homomorphisms) to thecategory of sets (and functions) admits aleft adjoint. Therefore, the free join-semilatticeF(S) over a setS is constructed by taking the collection of all non-emptyfinitesubsets ofS, ordered by subset inclusion. Clearly,S can be embedded intoF(S) by a mappinge that takes any elements inS to the singleton set{s}. Then any functionf from aS to a join-semilatticeT (more formally, to the underlying set ofT) induces a unique homomorphismf' between the join-semilatticesF(S) andT, such thatf =f' ○e. Explicitly,f' is given by$f^{\prime }(A)=\bigvee \{f(s)|s\in A\}.$ Now the obvious uniqueness off' suffices to obtain the required adjunction—the morphism-part of the functorF can be derived from general considerations (seeadjoint 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 offrames and frame-homomorphisms, and from the category of distributive lattices and lattice-homomorphisms, have a left adjoint.

• Directed set – Mathematical ordering with upper bounds – generalization of join semilattice
• List of order topics
• Semiring – Algebraic ring that need not have additive negative elements

• Davey, B. A.;Priestley, H. A. (2002).Introduction to Lattices and Order (second ed.).Cambridge University Press.ISBN 0-521-78451-4.
• Vickers, Steven (1989).Topology via Logic.Cambridge University Press.ISBN 0-521-36062-5.

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 entriesorder theory andlattice theory. Moreover, there is no literature on semilattices of comparable magnitude to that onsemigroups.

• Jipsen's algebra structures page:Semilattices.

• Lattice theory
• Algebraic structures

• Articles with short description
• Short description is different from Wikidata