Clarifications needed in an exercise about semilattice and abelian monoids in Arbib and Manes' text

63 Views Asked by At

The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes

Exercise: A $\textbf{semilattice}$ is a poset in which every finite subset has a least upper bound. Show that a semilattice is the same thing as an abelian monoid satisfying $x\cdot x=x$ for all $x$. [Hints: $\textit{LUB}\{x_1,\ldots,x_n\}=x_1+\ldots+x_n (=e\text{ if }n=0)$ where as $x\leq y$ iff $xy=x.$] Verify that a monoid homomorphism between semilattices preserves all finite $\textit{LUB}$'s and is automatically order-preserving.

Questions: I just few quick questions, the first is, I don't understand the how the hint resolves the question in particular where it states:

$\textit{LUB}\{x_1,\ldots,x_n\}=x_1+\ldots+x_n (=e\text{ if }n=0)$ where as $x\leq y$ iff $xy=x.$

I am guessing that for $\textit{LUB}\{x_1,\ldots,x_n\}=x_1+\ldots+x_n$, that would mean, I take the ${max}(x_1,\ldots,x_n)=x_i,$ and so $\textit{LUB}\{x_1,\ldots,x_n\}=x_1+\ldots+x_n=n\cdot x_i$? Also I don't understand the meaning of "$xy\leq x$ iff $xy=x$"?

Instead, can't I do the following: Suppose for any $a,b\in X$ and define the operation on the X with the binary operation: $a\cdot b={LUB}\{a,b\},$ and also show that it is a semilattice

Also, what does it mean to say "...monoid homomorphism between semilattices preserves all finite $\textit{LUB}$'s". I don't know what is meant by "preserves"?

Thank you in advance.

1

There are 1 best solutions below

1
On

From the context (the hint $LUB\{x_1,\ldots,x_n\}=e$ if $n=0$), I assume that this author considers that, in a semilattice, every finite set (including the empty set) has an upper bound, which I think is not usual, but still a reasonable definition. Hence the correspondence with idempotent commutative monoids, and not just with idempotent commutative semigroups, as usual.

The goal is to prove that, given a commutative idempotent monoid $(M,+,e)$, and defining $$ x_1 \vee x_2 \vee \cdots \vee x_n = \begin{cases} x_1 + \cdots + x_n, &\text{if } n>0,\\ e, &\text{if } n=0, \end{cases} $$ then $(M,\vee,e)$ is a join-semilattice with a top element $e$.
Of course you can define the binary operation join as $x \vee y = x + y$, and then generalize to the definition above, knowing that $x+e=x$ corresponds to $x \vee e = x$, meaning that $e$ is the top element.
But to reach that conclusion you must start by showing that there is order relation defined by $$x \leq y \iff x \vee y = y \iff x + y = y,$$ where the operation $\vee$ is the one of the semilattice, and the $+$, the one of the monoid (indeed, they are the same; the distinction is only so that you don't get lost in the correspondence).

In this answer I showed that the above formula does, indeed, define an order relation, and further that it defines a semilattice.
There is a difference though, which is, as I put in the beginning, the definition of semilattice which is used. However, that is not a problem, since in your case, you already have, by definition that the join of an empty set of elements is a fixed element $e$.

The meaning of "monoid homomorphism between semilattices preserves all finite LUBs" is that, if $\psi:(M,+,e)\to(M',*,e')$ is a monoid homomorphism, that is, $\psi(a+b)=\psi(a)*\psi(b)$ and $\psi(e)=e'$, then, considering the corresponding semilattices $(M,\vee,e)$ and $(M',\oplus,e')$, with top elements $e$ and $e'$, respectively, we have that $\psi(a\vee b) = \psi(a) \oplus \psi(b)$ (which certainly follows by definition, i.e., these operations coincide with the ones of the monoids), but also that $$\psi(a_1 \vee \cdots \vee a_n) = \psi(a_1) \oplus \cdots \oplus \psi(a_n),$$ which is not difficult to show.
Moreover, show that $\psi$ is order-preserving, that is, $$a \leq b \implies \psi(a) \leq \psi(b),$$ which follows from \begin{align} a \leq b &\implies a + b = b\\ &\implies \psi(a) * \psi(b) = \psi(b)\\ &\implies \psi(a) \leq \psi(b). \end{align}