congruence on a partial algebra

Definition

There are two types of congruences on a partial algebra $𝑨$, both are special types of a certain equivalence relation on $A$:

1. $\mathrm{\Theta }$ is a congruence relation on $𝑨$ if, given that

   • $a_1\equiv b_1(mod\mathrm{\Theta }),\mathrm{\dots },a_n\equiv b_n(mod\mathrm{\Theta })$,

   • both $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ and $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ are defined,

   then $f_{𝑨}(a_1,\mathrm{\dots },a_n)\equiv f_{𝑨}(b_1,\mathrm{\dots },b_n)(mod\mathrm{\Theta })$.

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

   • $a_1\equiv b_1(mod\mathrm{\Theta }),\mathrm{\dots },a_n\equiv b_n(mod\mathrm{\Theta })$,

   • $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined,

   then $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ is defined.

Proposition 1.

If $\varphi \mathrm{:}𝐀\mathrm{\to }𝐁$ is a homomorphism, then the equivalence relation $E_{\varphi }$ induced by $\varphi$ on $A$ is a congruence relation. Furthermore, if $\varphi$ is a strong, so is $E_{\varphi }$.

Proof.

Let $f\in \tau$ be an $n$-ary function symbol. Suppose $a_i\equiv b_i(mod{E}_{\varphi })$ and both $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ and $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ are defined. Then $\varphi (a_i)=\varphi (b_i)$, and therefore

$$\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))=f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))=f_{𝑩}(\varphi (b_1),\mathrm{\dots },\varphi (b_n))=\varphi (f_{𝑨}(b_1,\mathrm{\dots },b_n)),$$

so $f_{𝑨}(a_1,\mathrm{\dots },a_n)\equiv f_{𝑨}(b_1,\mathrm{\dots },b_n)(mod{E}_{\varphi })$. In other words, $E_{\varphi }$ is a congruence relation.

Now, suppose in addition that $\varphi$ is a strong homomorphism. Again, let $a_i\equiv b_i(mod{E}_{\varphi })$. Assume $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined. Since $\varphi (a_i)=\varphi (b_i)$, we get

$$\varphi (f_{𝑨}(a_1,\mathrm{\dots },a_n))=f_{𝑩}(\varphi (a_1),\mathrm{\dots },\varphi (a_n))=f_{𝑩}(\varphi (b_1),\mathrm{\dots },\varphi (b_n)).$$

Since $\varphi$ is strong, $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ is defined, which means that $E_{\varphi }$ is strong.∎

Congruences as Subalgebras

If $𝑨$ is a partial algebra of type $\tau$, then the direct power ${𝑨}^2$ is a partial algebra of type $\tau$. A binary relation $\mathrm{\Theta }$ on $A$ may be viewed as a subset of $A^2$. For each $n$-ary operation $f_{{𝑨}^2}$ on ${𝑨}^2$, take the restriction on $\mathrm{\Theta }$, and call it $f_{𝚯}$. For $a_i\in \mathrm{\Theta }$, $f_{𝚯}(a_1,\mathrm{\dots },a_n)$ is defined in $\mathrm{\Theta }$ iff $f_{{𝑨}^2}(a_1,\mathrm{\dots },a_n)$ is defined at all, and its value is in $\mathrm{\Theta }$. When $f_{𝚯}(a_1,\mathrm{\dots },a_n)$ is defined in $\mathrm{\Theta }$, its value is set as $f_{{𝑨}^2}(a_1,\mathrm{\dots },a_n)$. This turns $𝚯$ into a partial algebra. However, the type of $𝚯$ is $\tau$ only when $f_{𝚯}$ is non-empty for each function symbol $f\in \tau$. In particular,

Proposition 2.

If $\mathrm{\Theta }$ is reflexive, then $\mathrm{\Theta }$ is a relative subalgebra of ${𝐀}^{\mathrm{2}}$.

Proof.

Pick any $n$-ary function symbol $f\in \tau$. Then $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined for some $a_i\in A$. Then $f_{{𝑨}^2}((a_1,a_1),\mathrm{\dots },(a_n,a_n))$ is defined and is equal to $(f_{𝑨}(a_1,\mathrm{\dots },a_n),f_{𝑨}(a_1,\mathrm{\dots },a_n))$, which is in $\mathrm{\Theta }$, since $\mathrm{\Theta }$ is reflexive. This shows that $f_{𝚯}((a_1,a_1),\mathrm{\dots },(a_n,a_n))$ is defined. As a result, $𝚯$ is a partial algebra of type $\tau$. Furthermore, by virtue of the way $f_{𝚯}$ is defined for each $f\in \tau$, $𝚯$ is a relative subalgebra of $𝑨$.∎

Proposition 3.

An equivalence relation $\mathrm{\Theta }$ on $A$ is a congruence iff $\mathrm{\Theta }$ is a subalgebra of ${𝐀}^{\mathrm{2}}$.

Proof.

First, assume that $\mathrm{\Theta }$ is a congruence relation on $A$. Since $\mathrm{\Theta }$ is reflexive, $𝚯$ is a relative subalgebra of ${𝑨}^2$. Now, suppose $f_{{𝑨}^2}((a_1,b_1),\mathrm{\dots },(a_n,b_n))$ exists, where $a_i\equiv b_i(mod\mathrm{\Theta })$. Then $f_{𝑨}(a_1,\mathrm{\dots },a_n),f_{𝑨}(b_1,\mathrm{\dots },b_n)$ both exist. Since $\mathrm{\Theta }$ is a congruence, $f_{𝑨}(a_1,\mathrm{\dots },a_n)\equiv f_{𝑨}(b_1,\mathrm{\dots },b_n)(mod\mathrm{\Theta })$. In other words, $(f_{𝑨}(a_1,\mathrm{\dots },a_n),f_{𝑨}(b_1,\mathrm{\dots },b_n))\in \mathrm{\Theta }$. Hence $𝚯$ is a subalgebra of ${𝑨}^2$.

Conversely, assume $𝚯$ is a subalgebra of ${𝑨}^2$. Suppose $(a_i,b_i)\in \mathrm{\Theta }$ and both $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ and $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ are defined. Then $f_{{𝑨}^2}((a_1,b_1),\mathrm{\dots },(a_n,b_n))$ is defined. Since $𝚯$ is a subalgebra of ${𝑨}^2$, $f_{𝚯}((a_1,b_1),\mathrm{\dots },(a_n,b_n))$ is also defined, and $(f_{𝑨}(a_1,\mathrm{\dots },a_n),f_{𝑨}(b_1,\mathrm{\dots },b_n))=f_{{𝑨}^2}((a_1,b_1),\mathrm{\dots },(a_n,b_n))=f_{𝚯}((a_1,b_1),\mathrm{\dots },(a_n,b_n))\in \mathrm{\Theta }$. This shows that $\mathrm{\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 $𝑨$ of type $\tau$ and a congruence relation $\mathrm{\Theta }$ on $A$, the quotient partial algebra of $𝑨$ by $\mathrm{\Theta }$ is the partial algebra $𝑨\mathbf{/}𝚯$ whose underlying set is $A/\mathrm{\Theta }$, the set of congruence classes, and for each $n$-ary function symbol $f\in \tau$, $f_{𝑨\mathbf{/}𝚯}([a_1],\mathrm{\dots },[a_n])$ is defined iff there are $b_1,\mathrm{\dots },b_n\in A$ such that $[a_i]=[b_i]$ and $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ is defined. When this is the case:

$$f_{𝑨\mathbf{/}𝚯}([a_1],\mathrm{\dots },[a_n]):=[f_{𝑨}(b_1,\mathrm{\dots },b_n)].$$

Suppose there are $c_1,\mathrm{\dots },c_n\in A$ such that $[a_i]=[c_i]$, or $a_i\equiv c_i(mod\mathrm{\Theta })$, and $f_{𝑨}(c_1,\mathrm{\dots },c_n)$ is defined, then $b_i\equiv c_i(mod\mathrm{\Theta })$ and $f_{𝑨}(b_1,\mathrm{\dots },b_n)\equiv f_{𝑨}(c_1,\mathrm{\dots },c_n)(mod\mathrm{\Theta })$, or, equivalently, $[f_{𝑨}(b_1,\mathrm{\dots },b_n)]=[f_{𝑨}(c_1,\mathrm{\dots },c_n)]$, so that $f_{𝑨\mathbf{/}𝚯}$ is a well-defined operation.

In addition, it is easy to see that $𝑨\mathbf{/}𝚯$ is in fact a $\tau$-algebra. For each $n$-ary $f\in \tau$, pick $a_1,\mathrm{\dots },a_n\in A$ such that $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined. Then $f_{𝑨\mathbf{/}𝚯}([a_1],\mathrm{\dots },[a_n])$ is defined, and is equal to $[f_{𝑨}(a_1,\mathrm{\dots },a_n)]$.

Proposition 4.

Let $𝐀$ and $\mathrm{\Theta }$ be defined as above. Then $\mathrm{[}\mathrm{\cdot }\mathrm{]}\mathrm{:}𝐀\mathrm{\to }𝐀\mathrm{/}\mathrm{\Theta }$, given by $\mathrm{[}\mathrm{\cdot }\mathrm{]}\mathit{}\mathrm{(}a\mathrm{)}\mathrm{=}\mathrm{[}a\mathrm{]}$, is a surjective full homomorphism, and $E_{\mathrm{[}\mathrm{\cdot }\mathrm{]}}\mathrm{=}\mathrm{\Theta }$. Furthermore, $\mathrm{[}\mathrm{\cdot }\mathrm{]}$ is a strong homomorphism iff $\mathrm{\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_{𝑨\mathbf{/}𝚯}$, for each $f\in \tau$. Next, $a{E}_{[\cdot ]}b$ iff $[a]=[b]$ iff $a\equiv b(mod\mathrm{\Theta })$. This proves the first statement.

The next statement is proved as follows:

$(\Rightarrow )$. If $a_i\equiv b_i(mod\mathrm{\Theta })$ and $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined, then $f_{𝑨\mathbf{/}𝚯}([a_1],\mathrm{\dots },[a_n])$ is defined, which is just $f_{𝑨\mathbf{/}𝚯}([b_1],\mathrm{\dots },[b_n])$, and, as $[\cdot ]$ is strong, $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ is defined, showing that $\mathrm{\Theta }$ is strong.

$(\Leftarrow )$. Suppose $f_{𝑨\mathbf{/}𝚯}([a_1],\mathrm{\dots },[a_n])$ is defined. Then there are $b_1,\mathrm{\dots },b_n\in A$ with $a_i\equiv b_i(mod\mathrm{\Theta })$ such that $f_{𝑨}(b_1,\mathrm{\dots },b_n)$ is defined. Since $\mathrm{\Theta }$ is strong, $f_{𝑨}(a_1,\mathrm{\dots },a_n)$ is defined as well, which shows that $[\cdot ]$ is strong.∎