complete semilattice


A completePlanetmathPlanetmathPlanetmathPlanetmath join-semilattice is a join-semilattice L such that for any subset AL, A, the arbitrary join operationMathworldPlanetmath on A, exists. Dually, a complete meet-semilattice is a meet-semilattice such that A exists for any AL. Because there are no restrictionsPlanetmathPlanetmathPlanetmath placed on the subset A, it turns out that a complete join-semilattice is a complete meet-semilattice, and therefore a complete latticeMathworldPlanetmath. In other words, by dropping the arbitrary join (meet) operation from a complete lattice, we end up with nothing new. For a proof of this, see here (http://planetmath.org/CriteriaForAPosetToBeACompleteLattice). The crux of the matter lies in the fact that () applies to any set, including L itself, and the empty setMathworldPlanetmath , so that L always contains has a top and a bottom.

Variations. To obtain new objects, one looks for variations in the definition of “complete”. For example, if we require that any AL to be countableMathworldPlanetmath, we get what is a called a countably complete join-semilattice (or dually, a countably complete meet-semilattice). More generally, if κ is any cardinal, then a κ-complete join-semilattice is a semilattice L such that for any set AL such that |A|κ, A exists. If κ is finite, then L is just a join-semilattice. When κ=, the only requirement on AL is that it be non-empty. In [1], a complete semilattice is defined to be a poset L such that for any non-empty AL, A exists, and any directed setMathworldPlanetmath DL, D exists.

Example. Let A and B be two isomorphicPlanetmathPlanetmathPlanetmath complete chains (a chain that is a complete lattice) whose cardinality is κ. Combine the two chains to form a latticeMathworldPlanetmath L by joining the top of A with the top of B, and the bottom of A with the bottom of B, so that

  • if ab in A, then ab in L

  • if cd in B, then cd in L

  • if aA, cB, then ac iff a is the bottom of A and c is the top of B

  • if aA, cB, then ca iff a is the top of A and c is the bottom of B

Now, L can be easily seen to be a κ-complete lattice. Next, remove the bottom element of L to obtain L. Since, the meet operation no longer works on all pairs of elements of L while still works, L is a join-semilattice that is not a lattice. In fact, works on all subsets of L. Since |L|=κ, we see that L is a κ-complete join-semilattice.

Remark. Although a complete semilattice is the same as a complete lattice, a homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath f between, say, two complete join-semilattices L1 and L2, may fail to be a homomorphism between L1 and L2 as complete lattices. Formally, a complete join-semilattice homomorphism between two complete join-semilattices L1 and L2 is a function f:L1L2 such that for any subset AL1, we have

f(A)=f(A)

where f(A)={f(a)aA}. Note that it is not required that f(A)=f(A), so that f needs not be a complete lattice homomorphism.

To give a concrete example where a complete join-semilattice homomorphism f fails to be complete lattice homomorphism, take L from the example above, and define f:LL by f(a)=1 if a0 and f(0)=0. Then for any AL, it is evident that f(A)=f(A). However, if we take two incomparable elements a,bL, then f(ab)=f(0)=0, while f(a)f(b)=11=1.

References

  • 1 G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. W. Mislove, D. S. Scott, ContinuousPlanetmathPlanetmath Lattices and Domains, Cambridge University Press, Cambridge (2003).
  • 2 P. T. Johnstone, Stone Spaces, Cambridge University Press (1982).
Title complete semilattice
Canonical name CompleteSemilattice
Date of creation 2013-03-22 17:44:49
Last modified on 2013-03-22 17:44:49
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 13
Author CWoo (3771)
Entry type Definition
Classification msc 06A12
Classification msc 06B23
Synonym countably complete upper-semilattice
Synonym countably complete lower-semilattice
Synonym complete upper-semilattice homomorphism
Synonym complete lower-semilattice homomorphism
Related topic CompleteLattice
Related topic Semilattice
Related topic ArbitraryJoin
Defines countably complete join-semilattice
Defines countably complete meet-semilattice
Defines complete join-semilattice homomorphism
Defines complete meet-semilattice homomorphism