PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (204)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
complete semilattice (Definition)

A complete join-semilattice is a join-semilattice $ L$ such that for any subset $ A\subseteq L$, $ \bigvee A$, the arbitrary join operation on $ A$, exists. Dually, a complete meet-semilattice is a meet-semilattice such that $ \bigwedge A$ exists for any $ A\subseteq L$. Because there are no restrictions placed on the subset $ A$, it turns out that a complete join-semilattice is a complete meet-semilattice, and therefore a complete lattice. 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. The crux of the matter lies in the fact that $ \bigvee$ ($ \bigwedge$) applies to any set, including $ L$ itself, and the empty set $ \varnothing$, 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 $ A\subseteq L$ to be countable, we get what is a called a countably complete join-semilattice (or dually, a countably complete meet-semilattice). More generally, if $ \kappa$ is any cardinal, then a $ \kappa$-complete join-semilattice is a semilattice $ L$ such that for any set $ A\subseteq L$ such that $ \vert A\vert\le \kappa$, $ \bigvee A$ exists. If $ \kappa$ is finite, then $ L$ is just a join-semilattice. When $ \kappa=\infty$, the only requirement on $ A\subseteq L$ is that it be non-empty. In [1], a complete semilattice is defined to be a poset $ L$ such that for any non-empty $ A\subseteq L$, $ \bigwedge A$ exists, and any directed set $ D\subseteq L$, $ \bigvee D$ exists.

Example. Let $ A$ and $ B$ be two isomorphic complete chains (a chain that is a complete lattice) whose cardinality is $ \kappa$. Combine the two chains to form a lattice $ 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 $ a\le b$ in $ A$, then $ a\le b$ in $ L$
  • if $ c\le d$ in $ B$, then $ c\le d$ in $ L$
  • if $ a\in A$, $ c\in B$, then $ a\le c$ iff $ a$ is the bottom of $ A$ and $ c$ is the top of $ B$
  • if $ a\in A$, $ c\in B$, then $ c\le a$ iff $ a$ is the top of $ A$ and $ c$ is the bottom of $ B$
Now, $ L$ can be easily seen to be a $ \kappa$-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 $ \vee$ still works, $ L'$ is a join-semilattice that is not a lattice. In fact, $ \bigvee$ works on all subsets of $ L'$. Since $ \vert L'\vert=\kappa$, we see that $ L'$ is a $ \kappa$-complete join-semilattice.

Remark. Although a complete semilattice is the same as a complete lattice, a homomorphism $ f$ between, say, two complete join-semilattices $ L_1$ and $ L_2$, may fail to be a homomorphism between $ L_1$ and $ L_2$ as complete lattices. Formally, a complete join-semilattice homomorphism between two complete join-semilattices $ L_1$ and $ L_2$ is a function $ f:L_1\to L_2$ such that for any subset $ A\subseteq L_1$, we have

$\displaystyle f(\bigvee A)=\bigvee f(A)$
where $ f(A)=\lbrace f(a)\mid a\in A\rbrace$. Note that it is not required that $ f(\bigwedge A)=\bigwedge 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:L\to L$ by $ f(a)=1$ if $ a\ne 0$ and $ f(0)=0$. Then for any $ A\subseteq L$, it is evident that $ f(\bigvee A)=\bigvee f(A)$. However, if we take two incomparable elements $ a,b\in L$, then $ f(a\wedge b)=f(0)=0$, while $ f(a)\wedge f(b)= 1\wedge 1=1$.

Bibliography

1
G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. W. Mislove, D. S. Scott, Continuous Lattices and Domains, Cambridge University Press, Cambridge (2003).
2
P. T. Johnstone, Stone Spaces, Cambridge University Press (1982).



"complete semilattice" is owned by CWoo.
(view preamble)

View style:

See Also: complete lattice, semilattice, arbitrary join

Other names:  countably complete upper-semilattice, countably complete lower-semilattice, complete upper-semilattice homomorphism, complete lower-semilattice homomorphism
Also defines:  countably complete join-semilattice, countably complete meet-semilattice, complete join-semilattice homomorphism, complete meet-semilattice homomorphism
Log in to rate this entry.
(view current ratings)

Cross-references: incomparable, complete lattice homomorphism, function, homomorphism, iff, lattice, cardinality, chain, complete chains, isomorphic, directed set, poset, finite, semilattice, cardinal, countable, objects, variations, bottom, top, contains, empty set, meet, complete lattice, restrictions, meet-semilattice, operation, arbitrary join, subset, join-semilattice, complete
There are 2 references to this entry.

This is version 10 of complete semilattice, born on 2008-01-17, modified 2008-02-04.
Object id is 10197, canonical name is CompleteSemilattice.
Accessed 659 times total.

Classification:
AMS MSC: 06B23 (Order, lattices, ordered algebraic structures :: Lattices :: Complete lattices, completions)
 06A12 (Order, lattices, ordered algebraic structures :: Ordered sets :: Semilattices)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)