Let be a semigroup and fix a congruence on . Let denote the set of all congruences on which contain . Show that is a(n order) lattice under .

Recall that a poset is called an order lattice if any two elements have a greatest lower bound and a least upper bound.

Now is contained in the set of all equivalence relations on . We will approach this problem by showing that is a lattice under and then showing that if are congruences, then their least upper and greatest lower bound in is again in .

Lemma 1: Let be equivalences. Then is also an equivalence on , and moreover is the greatest lower bound of and with respect to . Proof: Since , we have . So is reflexive. Letting overbars denote the relational converse, we have , so that is symmetric. Now if and , then and , so that . So is an equivalence on . Certainly we have . If , then . So is the greatest lower bound of and in .

Given a relation on a set , we define the transitive closure of to be , where denotes the -fold relational composition of with itself. (E.g. .)

Lemma 2: (1) is transitive. (2) If is symmetric, then is symmetric. (3) If is reflexive, then is reflexive. (4) is the -least equivalence containing . Proof: (1) Suppose and . By definition, there exist positive natural numbers and such that and . So , and we have . So is transitive. (2) Note that . So is symmetric. (3) If , then certainly . (4) Let be a relation. By parts (1), (2), and (3), is an equivalence relation which contains (note that is symmetric). Suppose now that is an equivalence containing . Certainly then , and since is transitive, .

Lemma 3: Let be equivalences on . Then is the least upper bound of and in . Proof: Certainly we have , so that by Lemma 2 is an equivalence relation containing both and . Now suppose is an equivalence containing both and . Now , and since is transitive, as desired.

Lemmas 1 and 3 show that is an order lattice under , where the greatest lower bound of and is and the least upper bound is . Now is a subset of .

Lemma 4: Let be an order lattice and let . If for all we have (as computed in ), then is a lattice with respect to the restriction of . Proof: It suffices to notice that the bounds (as computed in ) satisfy the properties of least upper and greatest lower bounds in .

In view of Lemma 4, to show that is a lattice under inclusion, we need only show that if are congruences containing , then so are and . Certainly these are equivalences. If and , then we have and , so that . Certainly . So . Now suppose and , and so we have and for some positive natural numbers and . Now there exist mappings , , , and such that and . Since each and is a congruence, we have and . So , and thus . Certainly . So .

Thus is a lattice under .