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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: