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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: