Condition for Partition between Invertible and Non-Invertible Elements to induce Congruence Relation on Monoid
Theorem
Let $\struct {S, \circ}$ be a monoid whose identity element is $e$ such that $\struct {S, \circ}$ is specifically not a group.
Let $\struct {H, \circ}$ be the subgroup of $\struct {S, \circ}$ consisting of its invertible elements.
Let $N$ be the set of non-invertible elements of $\struct {S, \circ}$.
Let $\RR$ be the equivalence relation induced by the partition $\set {N \mid H}$.
Let either:
- $\circ$ be a cancellable operation
or:
- $\circ$ be a commutative operation.
Then:
- $\RR$ is a congruence relation on $\circ$
and:
- the quotient structure $\struct {S / \RR, \circ_\RR}$ is isomorphic to $\struct {\Z_2, \times_2}$, the multiplicative monoid of integers modulo $2$.
Counterexample
Let $\circ$ be such that it is neither a cancellable operation nor a commutative operation.
Then it is not necessarily the case that either:
- $\RR$ is a congruence relation on $\circ$
or:
- the quotient structure $\struct {S / \RR, \circ_\RR}$ is isomorphic to $\struct {\Z_2, \times_2}$, the multiplicative monoid of integers modulo $2$.
Proof
First we confirm from Invertible Elements of Monoid form Subgroup that $\struct {H, \circ}$ is in fact a subgroup of $\struct {S, \circ}$.
Let $h_1, h_2 \in H$ and $n_1, n_2 \in N$.
Immediately we have by Group Axiom $\text G 0$: Closure:
- $h_1 \circ h_2 \in H$
Aiming for a contradiction, suppose:
- $h_1 \circ n_1 \in H$
By Group Axiom $\text G 3$: Existence of Inverse Element:
- ${h_1}^{-1} \in H$
Hence by Group Axiom $\text G 0$: Closure:
- ${h_1}^{-1} \circ \paren {h_1 \circ n_1} = n_1 \in H$
This is a contradiction.
Therefore we must have:
- $h_1 \circ n_1 \in N$
Similarly, we must have:
- $n_1 \circ h_1 \in N$
Aiming for a contradiction, suppose:
- $n_1 \circ n_2 \in H$
Then by Group Axiom $\text G 3$: Existence of Inverse Element:
- $\exists h \in H: h \circ \paren {n_1 \circ n_2} = \paren {n_1 \circ n_2} \circ h = e_H$
so $\paren {n_2 \circ h}$ is a right inverse of $n_1$.
If $\circ$ is cancellable, from:
- $e_H \circ n_2 = n_2 \circ e_H = n_2 \circ \paren {h \circ n_1 \circ n_2}$
we would have:
- $e_H = n_2 \circ h \circ n_1$
If $\circ$ is commutative:
- $\paren {n_2 \circ h} \circ n_1 = n_1 \circ \paren {n_2 \circ h} = e_H$
In either case, we see that:
- $\paren {n_2 \circ h} \circ n_1 = e_H$
So $\paren {n_2 \circ h}$ is also a left inverse of $n_1$.
Thus $n_1$ is invertible, which is a contradiction.
Therefore we must have $n_1 \circ n_2 \in N$.
So far we have:
- $h_1 \circ h_2 \in H$
- $h_1 \circ n_1 \in N$
- $n_1 \circ h_1 \in N$
- $n_1 \circ n_2 \in N$
$\Box$
![]() | This article needs proofreading. In particular: The organization of the information below If you believe all issues are dealt with, please remove {{Proofread}} from the code.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Proofread}} from the code. |
Now we show that $\RR$ is a congruence relation on $\circ$.
By definition of $\RR$:
- $x \mathrel \RR y \iff \set {x, y} \subseteq N \lor \set {x, y} \subseteq H$
and we need to show:
- $\forall x_1, x_2, y_1, y_2 \in S: \paren {x_1 \mathrel \RR x_2} \land \paren {y_1 \mathrel \RR y_2} \implies \paren {x_1 \circ y_1} \mathrel \RR \paren {x_2 \circ y_2}$
There are $4$ cases:
- $x_1, x_2, y_1, y_2 \in H$:
Then:
- $x_1 \circ y_1, x_2 \circ y_2 \in H$
So:
- $\paren {x_1 \circ y_1} \mathrel \RR \paren {x_2 \circ y_2}$
The remaining cases are:
- $x_1, x_2 \in H, y_1, y_2 \in N$
- $x_1, x_2 \in N, y_1, y_2 \in H$
- $x_1, x_2, y_1, y_2 \in N$
In these cases we have:
- $x_1 \circ y_1, x_2 \circ y_2 \in N$
So:
- $\paren {x_1 \circ y_1} \mathrel \RR \paren {x_2 \circ y_2}$
Since in each case we have:
- $\paren {x_1 \circ y_1} \mathrel \RR \paren {x_2 \circ y_2}$
So:
- $\RR$ is a congruence relation on $\circ$.
$\Box$
Finally we show that the quotient structure $\struct {S / \RR, \circ_\RR}$ is isomorphic to $\struct {\Z_2, \times_2}$, the multiplicative monoid of integers modulo $2$.
We do this by defining a mapping $\phi: S / \RR \to \Z_2$ by:
- $\map \phi N = 0, \map \phi H = 1$
It is clear that $\phi$ is a bijection.
By writing $H = \eqclass h {\RR}$ and $N = \eqclass n \RR$, where $h \in H$ and $n \in N$, we see that:
- $H \circ_\RR H = \eqclass h {\RR} \circ_{\RR} \eqclass h {\RR} = \eqclass {h \circ h} {\RR} = H$
- $H \circ_\RR N = \eqclass h {\RR} \circ_{\RR} \eqclass n {\RR} = \eqclass {h \circ n} {\RR} = N$
- $N \circ_\RR H = \eqclass n {\RR} \circ_{\RR} \eqclass h {\RR} = \eqclass {n \circ h} {\RR} = N$
- $N \circ_\RR N = \eqclass n {\RR} \circ_{\RR} \eqclass n {\RR} = \eqclass {n \circ n} {\RR} = N$
and hence:
- $1 = \map \phi H = \map \phi {H \circ_\RR H} = \map \phi H \times \map \phi H = 1 \times 1$
- $0 = \map \phi N = \map \phi {H \circ_\RR N} = \map \phi H \times \map \phi N = 1 \times 0$
- $0 = \map \phi N = \map \phi {N \circ_\RR H} = \map \phi N \times \map \phi H = 0 \times 1$
- $0 = \map \phi N = \map \phi {N \circ_\RR N} = \map \phi N \times \map \phi N = 0 \times 0$
Thus $\phi$ is an isomorphism.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.17 \ \text {(a)}$