## Monthly Archives: August 2011

### Lattice Isomorphism Theorem for semigroups

Let $S$ be a semigroup and let $\sigma$ be a congruence on $S$. Let $\mathsf{Q}_\sigma(S)$ denote the set of all congruences on $S$ which contain $\sigma$, and let $\mathsf{Q}(S/\sigma)$ denote the set of all congruences on $S/\sigma$. Note that both $\mathsf{Q}_\sigma(S)$ and $\mathsf{Q}(S/\sigma)$ are partially ordered by $\subseteq$. Show that in fact they are isomorphic as partially ordered sets.

Given $\rho \in \mathsf{Q}_\sigma(S)$, define a relation $\overline{\rho}$ on $S/\sigma$ by $[x]_\sigma \overline{\rho} [y]_\sigma$ if and only if there exist $x^\prime \sigma x$ and $y^\prime \sigma y$ such that $x^\prime \rho y^\prime$. Since $\sigma \subseteq \rho$, note that in fact $[x]_\sigma \overline{\rho} [y]_\sigma$ if and only if $x \rho y$.

We claim that $\overline{\rho}$ is a congruence on $S/\sigma$. Since $\rho$ is reflextive, we have $x \rho x$ for all $x \in S$, and thus $[x]_\sigma \overline{\rho} [x]_\sigma$ for all $x$. If $[x]_\sigma \overline{\rho} [y]_\sigma$, then $x \rho y$, so that $y \rho x$, and thus $[y]_\sigma \overline{\rho} [y]_\sigma$. If $[x]_\sigma \overline{\rho} [y]_\sigma$ and $[y]_\sigma \overline{\rho} [z]_\sigma$, then $x \rho y \rho z$, so that $x \rho z$ and hence $[x]_\sigma \overline{\rho} [z]_\sigma$. Finally, if $[x]_\sigma \overline{\rho} [y]_\sigma$ and $[z]_\sigma \overline{\rho} [w]_\sigma$, then $x \rho y$ and $z \rho w$, so that $xz \rho yz$, and hence $[x]_\sigma[z]_\sigma \overline{\rho} [y]_\sigma[w]_\sigma$. So $\overline{\rho}$ is a congruence on $S/\sigma$.

Now define $\Psi : \mathsf{Q}_\sigma(S) \rightarrow \mathsf{Q}(S/\sigma)$ by $\Psi(\rho) = \overline{\rho}$. We claim that $\Psi$ is a poset isomorphism.

Suppose $\Psi(\rho) = \Psi(\tau)$. Now for all $x,y \in S$, we have $x \rho y$ if and only if $[x]_\sigma \overline{\rho} [y]_\sigma$ if and only if $[x]_\sigma \overline{\tau} [y]_\sigma$ if and only if $x \tau y$. So $\rho = \tau$. Thus $\Psi$ is injective.

Now suppose $\tau \in \mathsf{Q}(S/\sigma)$. Define a relation $\rho$ on $S$ by $x \rho y$ if and only if $[x]_\sigma \tau [y]_\sigma$. We claim that $\rho$ is a congruence. Indeed, for all $x$, $[x]_\sigma \tau [x]_\sigma$, so $x \rho x$; if $x \rho y$ then $[x]_\sigma \tau [y]_\sigma$, so that $[y]_\sigma \tau [x]_\sigma$, hence $y \rho x$; if $x \rho y$ and $y \rho z$, then $[x]_\sigma \tau [y]_\sigma \tau [z]_\sigma$, so that $[x]_\sigma \tau [z]_\sigma$, and thus $x \rho z$; and if $x \rho y$ and $z \rho w$, then $[x]_\sigma \tau [y]_\sigma$ and $[z]_\sigma \tau [w]_\sigma$, so $[xz]_\sigma \tau [yw]_\sigma$, and thus $xz \rho yw$. We claim also that $\sigma \subseteq \rho$. Indeed, if $x \sigma y$, then $[x]_\sigma = [y]_\sigma$, so that $[x]_\sigma \tau [y]_\sigma$ and we have $x \rho y$. So in fact $\rho \in \mathsf{Q}_\sigma(S)$. Finally, we claim that $\Psi(\rho) = \tau$; in fact, $[x]_\sigma \Psi(\rho) [y]_\sigma$ if and only if $x \rho y$ if and only if $[x]_\sigma \tau [y]_\sigma$ as desired. So $\Psi$ is surjective.

So $\Psi$ is a bijection. Finally, we claim that $\Psi$ preserves set containment. Indeed, if $\rho \subseteq \tau$, then $[x]_\sigma \Psi(\rho) [y]_\sigma$ implies $x \rho y$, implies $x \tau y$, implies $[x]_\sigma \Psi(\tau) [y]_\sigma$. So $\Psi(\rho) \subseteq \Psi(\tau)$.

Hence $\mathsf{Q}_\sigma(S)$ and $\mathsf{Q}(S/\sigma)$ are isomorphic as partially ordered sets.

### First Isomorphism Theorem for semigroups

Given a semigroup $S$ and a congruence $\sigma$ on $S$, show that the mapping $\pi_\sigma : S \rightarrow S/\sigma$ given by $s \mapsto [s]_\sigma$ is a surjective semigroup homomorphism.

Let $\varphi : S \rightarrow T$ be a homomorphism of semigroups. Define a relation $\mathsf{ker}\ \varphi$ by $(x,y) \in \mathsf{ker}\ \varphi$ if and only if $\varphi(x) = \varphi(y)$. Show that $\mathsf{ker}\ \varphi$ is a congruence on $S$. Show further that $S/\mathsf{ker}\ \varphi \cong \mathsf{im}\ \varphi$.

Recall that $S/\sigma$ is a semigroup under the operator $[x]_\sigma \star [y]_\sigma = [xy]_\sigma$, which is well-defined (i.e. does not depend on the representatives chosen) since $\sigma$ is a congruence. Now $\pi_\sigma(st) = [st]_\sigma = [s]_\sigma[t]_\sigma$ $= \pi_\sigma(s)\pi_\sigma(t)$, so that $\pi_\sigma$ is a semigroup homomorphism. Moreover, we have $[s]_\sigma = \pi_\sigma(s)$ for all $s \in S$, so that $\pi_\sigma$ is surjective.

Now let $\varphi$ and $\mathsf{ker}\ \varphi$ be as described above. Certainly $\mathsf{ker}\ \varphi$ is an equivalence. Now if $(x,y) \in \mathsf{ker}\ \varphi$ and $(z,w) \in \mathsf{ker}\ \varphi$, then $\varphi(x) = \varphi(y)$ and $\varphi(z) = \varphi(w)$, so that $\varphi(xz) = \varphi(x) \varphi(z) = \varphi(y) \varphi(w) = \varphi(yw)$. Hence $(xz,yw) \in \mathsf{ker}\ \varphi$, and so $\mathsf{ker}\ \varphi$ is a congruence on $S$.

Now define $\psi \subseteq S/\mathsf{ker}\ \varphi \times T$ by $\psi = \{ ([x]_\mathsf{ker}\ \varphi, \varphi(x)) \ |\ x \in S \}$. Certianly $\psi$ is total, and we claim it is well defined. Indeed, if we have $x,y \in S$ such that $(x,y) \in \mathsf{ker}\ \varphi$, then $\varphi(x) = \varphi(y)$. So in fact $\psi : S/\mathsf{ker}\ \varphi \rightarrow T$ is a function. Since $\psi([x][y]) = \psi([xy])$ $= \varphi(xy) = \varphi(x)\varphi(y)$ $= \psi([x])\psi([y])$, $\psi$ is a semigroup homomorphism. If $\psi([x]) = \psi([y])$, then we have $\varphi(x) = \varphi(y)$, so that $[x] = [y]$. Hence $psi$ is injective. Finally, if $t \in \mathsf{im}\ \varphi$, with $t = \varphi(s)$, then $t = \psi([s])$. So $\psi$ is onto the subset $\mathsf{im}\ \varphi \subseteq T$, and we have $S/\mathsf{ker}\ \varphi \cong \mathsf{im}\ \varphi$.

### An equivalent characterization of semigroup congruences

Let $S$ be a semigroup and let $\sigma$ be an equivalence on $S$. Show that $\sigma$ is a congruence on $S$ if and only if for all $a,b,c,d \in S$, if $a \sigma b$ and $c \sigma d$, then $ac \sigma bd$.

Recall that an equivalence on $S$ is a congruence if for all $a,b,c \in S$, if $a \sigma b$ then $ac \sigma bc$ and $ca \sigma cb$.

Suppose $\sigma$ is a congruence, and suppose $a \sigma b$ and $c \sigma d$. Certainly $c \sigma c$ and $b \sigma b$, so we have $ac \sigma bc$ and $bc \sigma bd$. So $ac \sigma bd$.

Conversely, if $a \sigma b$, then we have $c \sigma c$, so that $ac \sigma bc$ and $ca \sigma cb$.

### 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$.

### A natural partial order on the set of idempotents in a semigroup

Let $S$ be a semigroup and let $E(S)$ denote the set of idempotents in $S$. Define an order $\leq$ on $E(S)$ by $e \leq f$ iff $e = ef = fe$. Show that $\leq$ is a partial order.

Recall that a partial order is a binary relation which is reflexive, antisymmetric, and transitive.

If $e \in E(S)$, then $e$ is idempotent, so that $e = ee$. So $e \leq e$.

Suppose $e,f \in E(S)$ such that $e \leq f$ and $f \leq e$. Then $e = ef = fe$ and $f = fe = ef$, so that $e = f$.

Suppose $e,f,h \in E(S)$ such that $e \leq f$ and $f \leq h$. Now $e = ef = fe$ and $f = fh = hf$. So we have $e = ef = efh = eh$ and $e = fe = hfe = he$, and thus $e \leq h$.

### Characterize the invertible elements in a semigroup

Let $S$ be a semigroup with identity $e$ and let $a \in S$. Show that $a$ is invertible if and only if $Sa = aS = S$.

Suppose $a$ is invertible; then there exists an element $b$ such that $ab = ba = e$. Now let $s \in S$. We have $s = se = sba \in Sa$ and $s = es = abs \in aS$. So $aS = Sa = S$.

Conversely, suppose $aS = Sa = S$. Now $e \in S$, so there exist elements $b,c \in S$ such that $ab = ca = e$. Now $b = eb = cab = ce = c$, so that in fact $a$ is invertible.

### A semigroup can have at most one zero

Show that a semigroup can have at most one zero.

Recall that an element $z \in S$ is called a left zero if $zs = z$ for all $s \in S$ and a right zero if $sz = z$ for all $s \in S$, and a zero if it is both a left and a right zero.

Suppose $z$ is a left zero and $w$ a right zero. Then $w = zw = z$. In particular, if $z$ and $w$ are zeros in $S$, then $z = w$.

### A semigroup can have at most one identity element

Show that a semigroup can have at most one identity element.

Recall that a left identity is an element $e$ such that $es = s$ for all $s \in S$, and a right identity an element $f$ such that $sf = s$ for all $s \in S$. An identity is an element which is both a left and a right identity.

Suppose $e \in S$ is a left identity and $f \in S$ a right identity. Then $e = ef = f$. In particular, if $e$ and $f$ are identities, then $e = f$.

### A characterization of left simple and simple semigroups

Let $S$ be a semigroup. Show that $S$ is left simple if and only if $Sa = S$ for all $a \in S$, and is simple if and only if $SaS = S$ for all $a \in S$.

Recall that a semigroup is called left simple if the only left ideal is $S$ itself.

Suppose $S$ is left simple. Now $S(Sa) \subseteq Sa$, so that $Sa$ is a left ideal. Hence $Sa = S$. Conversely, suppose $Sa = S$ for every $a \in S$. Let $L$ be a left ideal. Now $L \neq \emptyset$, so we have $a \in L$ for some $a$. Then $S = Sa \subseteq L$, and thus $L = S$. So $S$ is left simple.

Similarly, we can show that $S$ is right simple if and only if $aS = S$ for all $a \in S$.

Now suppose $S$ is simple. (That is, it has no nontrivial ideals.) Let $a \in S$. Now $S(SaS) \subseteq SaS$ and $(SaS)S \subseteq SaS$, so that $SaS$ is an ideal. Hence $SaS = S$. Now suppose $SaS = S$ for all $a \in S$. If $I$ is a two-sided ideal, then we have $a \in I$ for some $a \in S$. Now $S = SaS \subseteq I$, so that $I = S$. Hence $S$ is simple.

### A characterization of principal ideals in a semigroup

Let $S$ be a semigroup and let $a \in S$. Let $L(a)$, $R(a)$, and $J(a)$ be the left, right, and two-sided ideals generated by $a$, respectively. Prove that $L(a) = a \cup Sa$, $R(a) = a \cup aS$, and $J(a) = a \cup Sa \cup aS \cup SaS$.

Recall that by definition, $L(a)$ is the intersection over the class of left ideals which contain $a$. Suppose $L$ is a left ideal containing $a$. Then for all $s \in S$, $sa \in L$, and thus $a \cup Sa \subseteq L$. So $a \cup Sa \subseteq L(a)$. On the other hand, we have $S(a \cup Sa) = Sa \cup SSa \subseteq Sa$ $\subseteq a \cup Sa$. So $a \cup Sa$ is a left ideal containing $a$, and thus $L(a) \subseteq a \cup Sa$. So $L(a) = a \cup Sa$.

The proofs for $R(a)$ and $J(a)$ are similar; show that every (right,two sided) ideal contains the set in question, and that the set in question is a (right, two-sided) ideal.