You are here
Homecongruence on a partial algebra
Primary tabs
congruence on a partial algebra
Definition
There are two types of congruences on a partial algebra $\boldsymbol{A}$, both are special types of a certain equivalence relation on $A$:
1. $\Theta$ is a congruence relation on $\boldsymbol{A}$ if, given that

$a_{1}\equiv b_{1}\;\;(\mathop{{\rm mod}}\Theta),\ldots,a_{n}\equiv b_{n}\;\;(% \mathop{{\rm mod}}\Theta)$,

both $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ and $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})$ are defined,
then $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})\equiv f_{{\boldsymbol{A}}}(b_{1},% \ldots,b_{n})\;\;(\mathop{{\rm mod}}\Theta)$.

2. $\Theta$ is a strong congruence relation on $\boldsymbol{A}$ if it is a congruence relation on $\boldsymbol{A}$, and, given

$a_{1}\equiv b_{1}\;\;(\mathop{{\rm mod}}\Theta),\ldots,a_{n}\equiv b_{n}\;\;(% \mathop{{\rm mod}}\Theta)$,

$f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ is defined,
then $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})$ is defined.

Proposition 1.
If $\phi:\boldsymbol{A}\to\boldsymbol{B}$ is a homomorphism, then the equivalence relation $E_{{\phi}}$ induced by $\phi$ on $A$ is a congruence relation. Furthermore, if $\phi$ is a strong, so is $E_{{\phi}}$.
Proof.
Let $f\in\tau$ be an $n$ary function symbol. Suppose $a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}E_{{\phi}})$ and both $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ and $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})$ are defined. Then $\phi(a_{i})=\phi(b_{i})$, and therefore
$\phi(f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n}))=f_{{\boldsymbol{B}}}(\phi(a_{1}% ),\ldots,\phi(a_{n}))=f_{{\boldsymbol{B}}}(\phi(b_{1}),\ldots,\phi(b_{n}))=% \phi(f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})),$ 
so $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})\equiv f_{{\boldsymbol{A}}}(b_{1},% \ldots,b_{n})\;\;(\mathop{{\rm mod}}E_{{\phi}})$. In other words, $E_{{\phi}}$ is a congruence relation.
Now, suppose in addition that $\phi$ is a strong homomorphism. Again, let $a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}E_{{\phi}})$. Assume $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ is defined. Since $\phi(a_{i})=\phi(b_{i})$, we get
$\phi(f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n}))=f_{{\boldsymbol{B}}}(\phi(a_{1}% ),\ldots,\phi(a_{n}))=f_{{\boldsymbol{B}}}(\phi(b_{1}),\ldots,\phi(b_{n})).$ 
Since $\phi$ is strong, $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})$ is defined, which means that $E_{{\phi}}$ is strong. ∎
Congruences as Subalgebras
If $\boldsymbol{A}$ is a partial algebra of type $\tau$, then the direct power $\boldsymbol{A}^{2}$ is a partial algebra of type $\tau$. A binary relation $\Theta$ on $A$ may be viewed as a subset of $A^{2}$. For each $n$ary operation $f_{{\boldsymbol{A}^{2}}}$ on $\boldsymbol{A}^{2}$, take the restriction on $\Theta$, and call it $f_{{\boldsymbol{\Theta}}}$. For $a_{i}\in\Theta$, $f_{{\boldsymbol{\Theta}}}(a_{1},\ldots,a_{n})$ is defined in $\Theta$ iff $f_{{\boldsymbol{A}^{2}}}(a_{1},\ldots,a_{n})$ is defined at all, and its value is in $\Theta$. When $f_{{\boldsymbol{\Theta}}}(a_{1},\ldots,a_{n})$ is defined in $\Theta$, its value is set as $f_{{\boldsymbol{A}^{2}}}(a_{1},\ldots,a_{n})$. This turns $\boldsymbol{\Theta}$ into a partial algebra. However, the type of $\boldsymbol{\Theta}$ is $\tau$ only when $f_{{\boldsymbol{\Theta}}}$ is nonempty for each function symbol $f\in\tau$. In particular,
Proposition 2.
If $\Theta$ is reflexive, then $\boldsymbol{\Theta}$ is a relative subalgebra of $\boldsymbol{A}^{2}$.
Proof.
Pick any $n$ary function symbol $f\in\tau$. Then $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ is defined for some $a_{i}\in A$. Then $f_{{\boldsymbol{A}^{2}}}((a_{1},a_{1}),\ldots,(a_{n},a_{n}))$ is defined and is equal to $(f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n}),f_{{\boldsymbol{A}}}(a_{1},\ldots,a_% {n}))$, which is in $\Theta$, since $\Theta$ is reflexive. This shows that $f_{{\boldsymbol{\Theta}}}((a_{1},a_{1}),\ldots,(a_{n},a_{n}))$ is defined. As a result, $\boldsymbol{\Theta}$ is a partial algebra of type $\tau$. Furthermore, by virtue of the way $f_{{\boldsymbol{\Theta}}}$ is defined for each $f\in\tau$, $\boldsymbol{\Theta}$ is a relative subalgebra of $\boldsymbol{A}$. ∎
Proposition 3.
An equivalence relation $\Theta$ on $A$ is a congruence iff $\boldsymbol{\Theta}$ is a subalgebra of $\boldsymbol{A}^{2}$.
Proof.
First, assume that $\Theta$ is a congruence relation on $A$. Since $\Theta$ is reflexive, $\boldsymbol{\Theta}$ is a relative subalgebra of $\boldsymbol{A}^{2}$. Now, suppose $f_{{\boldsymbol{A}^{2}}}((a_{1},b_{1}),\ldots,(a_{n},b_{n}))$ exists, where $a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}\Theta)$. Then $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n}),f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{% n})$ both exist. Since $\Theta$ is a congruence, $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})\equiv f_{{\boldsymbol{A}}}(b_{1},% \ldots,b_{n})\;\;(\mathop{{\rm mod}}\Theta)$. In other words, $(f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n}),f_{{\boldsymbol{A}}}(b_{1},\ldots,b_% {n}))\in\Theta$. Hence $\boldsymbol{\Theta}$ is a subalgebra of $\boldsymbol{A}^{2}$.
Conversely, assume $\boldsymbol{\Theta}$ is a subalgebra of $\boldsymbol{A}^{2}$. Suppose $(a_{i},b_{i})\in\Theta$ and both $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ and $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})$ are defined. Then $f_{{\boldsymbol{A}^{2}}}((a_{1},b_{1}),\ldots,(a_{n},b_{n}))$ is defined. Since $\boldsymbol{\Theta}$ is a subalgebra of $\boldsymbol{A}^{2}$, $f_{{\boldsymbol{\Theta}}}((a_{1},b_{1}),\ldots,(a_{n},b_{n}))$ is also defined, and $(f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n}),f_{{\boldsymbol{A}}}(b_{1},\ldots,b_% {n}))=f_{{\boldsymbol{A}^{2}}}((a_{1},b_{1}),\ldots,(a_{n},b_{n}))=f_{{% \boldsymbol{\Theta}}}((a_{1},b_{1}),\ldots,(a_{n},b_{n}))\in\Theta$. This shows that $\Theta$ is a congruence relation on $A$. ∎
Quotient Partial Algebras
With congruence relations defined, one may then define quotient partial algebras: given a partial algebra $\boldsymbol{A}$ of type $\tau$ and a congruence relation $\Theta$ on $A$, the quotient partial algebra of $\boldsymbol{A}$ by $\Theta$ is the partial algebra $\boldsymbol{A/\Theta}$ whose underlying set is $A/\Theta$, the set of congruence classes, and for each $n$ary function symbol $f\in\tau$, $f_{{\boldsymbol{A/\Theta}}}([a_{1}],\ldots,[a_{n}])$ is defined iff there are $b_{1},\ldots,b_{n}\in A$ such that $[a_{i}]=[b_{i}]$ and $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})$ is defined. When this is the case:
$f_{{\boldsymbol{A/\Theta}}}([a_{1}],\ldots,[a_{n}]):=[f_{{\boldsymbol{A}}}(b_{% 1},\ldots,b_{n})].$ 
Suppose there are $c_{1},\ldots,c_{n}\in A$ such that $[a_{i}]=[c_{i}]$, or $a_{i}\equiv c_{i}\;\;(\mathop{{\rm mod}}\Theta)$, and $f_{{\boldsymbol{A}}}(c_{1},\ldots,c_{n})$ is defined, then $b_{i}\equiv c_{i}\;\;(\mathop{{\rm mod}}\Theta)$ and $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})\equiv f_{{\boldsymbol{A}}}(c_{1},% \ldots,c_{n})\;\;(\mathop{{\rm mod}}\Theta)$, or, equivalently, $[f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})]=[f_{{\boldsymbol{A}}}(c_{1},\ldots,% c_{n})]$, so that $f_{{\boldsymbol{A/\Theta}}}$ is a welldefined operation.
In addition, it is easy to see that $\boldsymbol{A/\Theta}$ is in fact a $\tau$algebra. For each $n$ary $f\in\tau$, pick $a_{1},\ldots,a_{n}\in A$ such that $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ is defined. Then $f_{{\boldsymbol{A/\Theta}}}([a_{1}],\ldots,[a_{n}])$ is defined, and is equal to $[f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})]$.
Proposition 4.
Let $\boldsymbol{A}$ and $\Theta$ be defined as above. Then $[\cdot]:\boldsymbol{A}\to\boldsymbol{A/\Theta}$, given by $[\cdot](a)=[a]$, is a surjective full homomorphism, and $E_{{[\cdot]}}=\Theta$. Furthermore, $[\cdot]$ is a strong homomorphism iff $\Theta$ is a strong congruence relation.
Proof.
$[\cdot]$ is obviously surjective. The fact that $[\cdot]$ is a full homomorphism follows directly from the definition of $f_{{\boldsymbol{A/\Theta}}}$, for each $f\in\tau$. Next, $aE_{{[\cdot]}}b$ iff $[a]=[b]$ iff $a\equiv b\;\;(\mathop{{\rm mod}}\Theta)$. This proves the first statement.
The next statement is proved as follows:
$(\Rightarrow)$. If $a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}\Theta)$ and $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ is defined, then $f_{{\boldsymbol{A/\Theta}}}([a_{1}],\ldots,[a_{n}])$ is defined, which is just $f_{{\boldsymbol{A/\Theta}}}([b_{1}],\ldots,[b_{n}])$, and, as $[\cdot]$ is strong, $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})$ is defined, showing that $\Theta$ is strong.
$(\Leftarrow)$. Suppose $f_{{\boldsymbol{A/\Theta}}}([a_{1}],\ldots,[a_{n}])$ is defined. Then there are $b_{1},\ldots,b_{n}\in A$ with $a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}\Theta)$ such that $f_{{\boldsymbol{A}}}(b_{1},\ldots,b_{n})$ is defined. Since $\Theta$ is strong, $f_{{\boldsymbol{A}}}(a_{1},\ldots,a_{n})$ is defined as well, which shows that $[\cdot]$ is strong. ∎
References
 1 G. Grätzer: Universal Algebra, 2nd Edition, Springer, New York (1978).
Mathematics Subject Classification
08A55 no label found03E99 no label found08A62 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections