## The set of congruences on a semigroup which contain a fixed congruence is a lattice under set containment

Let $S$ be a semigroup and fix a congruence $\sigma$ on $S$. Let $\mathsf{Q}_\sigma(S)$ denote the set of all congruences on $S$ which contain $\sigma$. Show that $\mathsf{Q}_\sigma(S)$ is a(n order) lattice under $\subseteq$.

Recall that a poset $(P, \leq)$ is called an order lattice if any two elements have a greatest lower bound and a least upper bound.

Now $\mathsf{Q}_\sigma(S)$ is contained in the set $\mathsf{E}(S)$ of all equivalence relations on $S$. We will approach this problem by showing that $\mathsf{E}(S)$ is a lattice under $\subseteq$ and then showing that if $\alpha,\beta$ are congruences, then their least upper and greatest lower bound in $\mathsf{E}(S)$ is again in $\mathsf{Q}_\sigma(S)$.

Lemma 1: Let $\varepsilon, \delta \in \mathsf{E}(S)$ be equivalences. Then $\varepsilon \cap \delta$ is also an equivalence on $S$, and moreover is the greatest lower bound of $\varepsilon$ and $\delta$ with respect to $\subseteq$. Proof: Since $\Delta_S \subseteq \varepsilon,\delta$, we have $\Delta_S \subseteq \varepsilon \cap \delta$. So $\varepsilon \cap \delta$ is reflexive. Letting overbars denote the relational converse, we have $\overline{\varepsilon \cap \delta} = \overline{\varepsilon} \cap \overline{\delta}$ $= \varepsilon \cap \delta$, so that $\varepsilon \cap \delta$ is symmetric. Now if $x (\varepsilon \cap \delta) y$ and $y (\varepsilon \cap \delta) z$, then $x \varepsilon y \varepsilon z$ and $x \delta y \delta z$, so that $x (\varepsilon \cap \delta) z$. So $\varepsilon \cap \delta$ is an equivalence on $S$. Certainly we have $\varepsilon \cap \delta \subseteq \varepsilon, \delta$. If $\eta \subseteq \varepsilon, \delta$, then $\eta \subseteq \varepsilon \cap \delta$. So $\varepsilon \cap \delta$ is the greatest lower bound of $\varepsilon$ and $\delta$ in $\mathsf{E}(S)$. $\square$

Given a relation $\sigma$ on a set $X$, we define the transitive closure of $\sigma$ to be $\mathsf{tc}(\sigma) = \bigcup_{n \in \mathbb{N}^+} \sigma^n$, where $\sigma^n$ denotes the $n$-fold relational composition of $\sigma$ with itself. (E.g. $\sigma^3 = \sigma \circ \sigma \circ \sigma$.)

Lemma 2: (1) $\mathsf{tc}(\sigma)$ is transitive. (2) If $\sigma$ is symmetric, then $\mathsf{tc}(\sigma)$ is symmetric. (3) If $\sigma$ is reflexive, then $\mathsf{tc}(\sigma)$ is reflexive. (4) $\mathsf{eq}(\sigma) = \mathsf{tc}(\sigma \circ \overline{\sigma} \circ \Delta)$ is the $\subseteq$-least equivalence containing $\sigma$. Proof: (1) Suppose $x \mathsf{tc}(\sigma) y$ and $y \mathsf{tc}(\sigma) z$. By definition, there exist positive natural numbers $m$ and $n$ such that $x \sigma^m y$ and $y \sigma^n z$. So $x \sigma^{m+n} z$, and we have $x \mathsf{tc}(\sigma) z$. So $\mathsf{tc}(\sigma)$ is transitive. (2) Note that $\overline{\mathsf{tc}(\sigma)} = \overline{\bigcup_{n \in \mathbb{N}^+} \sigma^n}$ $= \bigcup_{n \in \mathbb{N}^+} \overline{\sigma^n}$ $= \bigcup_n \overline{\sigma}^n$ $= \bigcup_n \sigma^n$ $= \mathsf{tc}(\sigma)$. So $\mathsf{tc}(\sigma)$ is symmetric. (3) If $\Delta \subseteq \sigma$, then certainly $\Delta \subseteq \mathsf{tc}(\sigma)$. (4) Let $\sigma$ be a relation. By parts (1), (2), and (3), $\mathsf{eq}(\sigma)$ is an equivalence relation which contains $\sigma$ (note that $\sigma \cup \overline{\sigma} \cup \Delta$ is symmetric). Suppose now that $\varepsilon$ is an equivalence containing $\sigma$. Certainly then $\sigma \cup \overline{\sigma} \cup \Delta \subseteq \varepsilon$, and since $\varepsilon$ is transitive, $\mathsf{eq}(\sigma) \subseteq \varepsilon$. $\square$

Lemma 3: Let $\alpha,\beta$ be equivalences on $S$. Then $\mathsf{eq}(\alpha \cup \beta)$ is the least upper bound of $\alpha$ and $\beta$ in $\mathsf{E}(S)$. Proof: Certainly we have $\alpha,\beta \subseteq \alpha \cup \beta \subseteq \mathsf{eq}(\alpha \cup \beta)$, so that by Lemma 2 $\mathsf{eq}(\alpha \cup \beta)$ is an equivalence relation containing both $\alpha$ and $\beta$. Now suppose $\delta$ is an equivalence containing both $\alpha$ and $\beta$. Now $(\alpha \cup \beta) \cup \overline{\alpha \cup \beta} \cup \Delta = \alpha \cup \beta \subseteq \delta$, and since $\delta$ is transitive, $\mathsf{eq}(\alpha \cup \beta) \subseteq \delta$ as desired. $\square$

Lemmas 1 and 3 show that $\mathsf{E}(S)$ is an order lattice under $\subseteq$, where the greatest lower bound of $\alpha$ and $\beta$ is $\alpha \cap \beta$ and the least upper bound is $\mathsf{eq}(\alpha \cup \beta)$. Now $\mathsf{Q}_\sigma(S)$ is a subset of $\mathsf{E}(S)$.

Lemma 4: Let $(P, \leq)$ be an order lattice and let $Q \subseteq P$. If for all $x,y \in Q$ we have $\mathsf{glb}(x,y), \mathsf{lub}(x,y) \in Q$ (as computed in $P$), then $Q$ is a lattice with respect to the restriction of $\leq$. Proof: It suffices to notice that the bounds (as computed in $P$) satisfy the properties of least upper and greatest lower bounds in $Q$. $\square$

In view of Lemma 4, to show that $\mathsf{Q}_\sigma(S)$ is a lattice under inclusion, we need only show that if $\tau,\rho$ are congruences containing $\sigma$, then so are $\tau \cap \rho$ and $\mathsf{eq}(\tau \circ \rho)$. Certainly these are equivalences. If $x (\tau \cap \rho) y$ and $z (\tau \cap \rho) w$, then we have $xz \tau yw$ and $xz \rho yw$, so that $xz (\tau \cap \rho) yw$. Certainly $\sigma \subseteq \tau \cap \rho$. So $\tau \cap \rho \in \mathsf{Q}_\sigma(S)$. Now suppose $x \mathsf{eq}(\tau \cup \rho) y$ and $z \mathsf{eq}(\tau \cup \rho) w$, and so we have $x (\tau \cup \rho)^m y$ and $z (\tau \cup \rho)^n w$ for some positive natural numbers $m$ and $n$. Now there exist mappings $\varepsilon : m \rightarrow \{\tau,\rho\}$, $\delta : n \rightarrow \{\tau,\rho\}$, $e : m-1 \rightarrow S$, and $d : n-1 \rightarrow S$ such that $x \varepsilon_1 e_1 \varepsilon_2 e_2 \cdots e_{m-1} \varepsilon_m y$ and $z \delta_1 d_1 \cdots d_{n-1} \delta_n w$. Since each $\varepsilon_i$ and $\delta_i$ is a congruence, we have $xz \varepsilon_1 e_1z \cdots e_{m-1}z \varepsilon_m yz$ and $yz \delta_1 yd_1 \cdots yd_{n-1} \delta_n yw$. So $xz (\tau \cup \rho)^{m+n} yw$, and thus $xz \mathsf{eq}(\tau \cup \rho) yw$. Certainly $\sigma \subseteq \mathsf{eq}(\tau \cup \rho)$. So $\mathsf{eq}(\tau \cup \rho) \in \mathsf{Q}_\sigma(S)$.

Thus $\mathsf{Q}_\sigma(S)$ is a lattice under $\subseteq$.