# congruence on a partial algebra

## Definition

1. 1.

$\Theta$ is a congruence relation on $\boldsymbol{A}$ if, given that

• $a_{1}\equiv b_{1}\pmod{\Theta},\ldots,a_{n}\equiv b_{n}\pmod{\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})\pmod{\Theta}$.

2. 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}\pmod{\Theta},\ldots,a_{n}\equiv b_{n}\pmod{\Theta}$,

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

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

###### Proof.

Let $f\in\tau$ be an $n$-ary function symbol. Suppose $a_{i}\equiv b_{i}\pmod{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})\pmod{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}\pmod{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 non-empty for each function symbol $f\in\tau$. In particular,

###### 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}\pmod{\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})\pmod{\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}\pmod{\Theta}$, and $f_{\boldsymbol{A}}(c_{1},\ldots,c_{n})$ is defined, then $b_{i}\equiv c_{i}\pmod{\Theta}$ and $f_{\boldsymbol{A}}(b_{1},\ldots,b_{n})\equiv f_{\boldsymbol{A}}(c_{1},\ldots,c% _{n})\pmod{\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 well-defined 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\pmod{\Theta}$. This proves the first statement.

The next statement is proved as follows:

$(\Rightarrow)$. If $a_{i}\equiv b_{i}\pmod{\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}\pmod{\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

 Title congruence on a partial algebra Canonical name CongruenceOnAPartialAlgebra Date of creation 2013-03-22 18:43:01 Last modified on 2013-03-22 18:43:01 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 14 Author CWoo (3771) Entry type Definition Classification msc 08A55 Classification msc 03E99 Classification msc 08A62 Synonym congruence Synonym strong congruence Synonym quotient algebra Defines congruence relation Defines strong congruence relation Defines quotient partial algebra