Set of Congruence Relations on Algebraic Structure forms Complete Lattice

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \odot}$ be an algebraic structure.

Let $\map \RR \odot$ be the set of all congruence relations on $\struct {S, \odot}$.


Then $\struct {\map \RR \odot, \subseteq}$ is a complete lattice.


Proof

Elements of $\map \RR \odot$ are subsets of $S \times S$.

First we consider the trivial relation $S \times S$ itself.

From Trivial Relation is Universally Congruent, $S \times S$ is a congruence relation on $\struct {S, \odot}$.


Let $\TT$ be a subset of $\map \RR \odot$.

Consider the intersection $\HH = \ds \bigcap \TT$.


Let $x_1, y_1, x_2, y_2 \in S$ be arbitrary, such that:

$x_1 \mathrel \HH y_1$ and $x_2 \mathrel \HH y_2$

We have:

\(\ds x_1\) \(\HH\) \(\ds y_1\)
\(\, \ds \land \, \) \(\ds x_2\) \(\HH\) \(\ds y_2\)
\(\ds \leadsto \ \ \) \(\ds \forall \KK \in \TT: \, \) \(\ds x_1\) \(\KK\) \(\ds y_1\) Definition of Intersection of Set of Sets
\(\, \ds \land \, \) \(\ds x_2\) \(\KK\) \(\ds y_2\)
\(\ds \leadsto \ \ \) \(\ds \forall \KK \in \TT: \, \) \(\ds x_1 \odot x_2\) \(\KK\) \(\ds y_1 \odot y_2\) Definition of Congruence Relation
\(\ds \leadsto \ \ \) \(\ds x_1 \odot x_2\) \(\HH\) \(\ds y_1 \odot y_2\) Definition of Intersection of Set of Sets

Hence $\HH = \ds \bigcap \TT$ is a congruence relation on $\struct {S, \odot}$.

That is:

$\ds \bigcap \TT \in \map \RR \odot$


The appropriate conditions are fulfilled, and from Set of Subsets which contains Set and Intersection of Subsets is Complete Lattice:

$\struct {\map \RR \odot, \subseteq}$ is a complete lattice.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Set_of_Congruence_Relations_on_Algebraic_Structure_forms_Complete_Lattice&oldid=701158"