Equivalence of algebraic and order semilattices

Let S be an algebraic semilattice. (That is, an commutative semigroup in which every element is idempotent.) Recall the natural partial order \leq on S given by e \leq f if and only if e = ef = fe. Show that any two elements e and f of S have a greatest lower bound with respect to \leq, which is ef.

Conversely, suppose S is an order semilattice. (That is, we have a partial order \leq on S such that any two elements have a greatest lower bound.) Show that the operator \mathsf{glb} on S makes S into an algebraic semilattice, whose natural order coincides with \leq.

Suppose S is an algebraic semilattice, and let e,f \in S. Now ef = eff and ef = eef = efe, so that ef \leq e and ef \leq f. Now suppose h \leq e and h \leq f. Then h = he and h = hf, so that h = hf = hef, and we have h \leq ef. So ef is a greatest lower bound of e and f with respect to the natural order.

Now suppose (S,\leq) is an order semilattice, and denote the greatest lower bound of e and f by \mathsf{glb}(e,f). We claim that \mathsf{glb} is associative. To that end, let a,b,c \in S. Note that \mathsf{glb}(\mathsf{glb}(a,b),c) \leq \mathsf{glb}(a,b) \leq a, \mathsf{glb}(\mathsf{glb}(a,b),c) \leq \mathsf{glb}(a,b) \leq b, and \mathsf{glb}(\mathsf{glb}(a,b),c) \leq c. So \mathsf{glb}(\mathsf{glb}(a,b)) \leq \mathsf{glb}(b,c), and we have \mathsf{glb}(\mathsf{glb}(a,b),c) \leq \mathsf{glb}(a,\mathsf{glb}(b,c)). Similarly, \mathsf{glb}(a,\mathsf{glb}(b,c)) \leq a,b,c, so that \mathsf{glb}(a,\mathsf{glb}(b,c)) \leq \mathsf{glb}(a,b), and we have \mathsf{glb}(a,\mathsf{glb}(b,c)) \leq \mathsf{glb}(\mathsf{glb}(a,b),c). Since \leq is antisymmetric, \mathsf{glb}(\mathsf{glb}(a,b),c) = \mathsf{glb}(a,\mathsf{glb}(b,c)). So S is a semigroup under \mathsf{glb}. Certainly this operator is commutative and associative, so that (S,\mathsf{glb}) is an algebraic semilattice. Now let \sigma denote the natural order on S. If e \sigma f, we have e = \mathsf{glb}(e,f), so that e \leq f. Conversely, if e \leq f, then \mathsf{glb}(e,f) = e, and thus e \sigma f.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: