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}\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.
$\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.

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}\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,

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}\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

1 G. Grätzer: Universal Algebra, 2nd Edition, Springer, New York (1978).

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