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 ===
== 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 :
:$h_1 \circ h_2 \in H$
:
:$h_1 \circ n_1 \in H$
By :
:${h_1}^{-1} \in H$
Hence by :
:${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$
:
:$n_1 \circ n_2 \in H$
Then by :
:$\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$
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$.
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.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.17 \ \text {(a)}$
Category:Monoids
Category:Subgroups
Category:Inverse Elements
Category:Condition for Partition between Invertible and Non-Invertible Elements to induce Congruence Relation on Monoid