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.