congruence on a partial algebra


There are two types of congruencesMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath on a partial algebraMathworldPlanetmath 𝑨, both are special types of a certain equivalence relationMathworldPlanetmath on A:

  1. 1.

    Θ is a congruence relation on 𝑨 if, given that

    • –


    • –

      both f𝑨⁒(a1,…,an) and f𝑨⁒(b1,…,bn) are defined,

    then f𝑨⁒(a1,…,an)≑f𝑨⁒(b1,…,bn)(modΘ).

  2. 2.

    Θ is a strong congruence relation on 𝑨 if it is a congruence relation on 𝑨, and, given

    • –


    • –

      f𝑨⁒(a1,…,an) is defined,

    then f𝑨⁒(b1,…,bn) is defined.

Proposition 1.

If Ο•:𝐀→𝐁 is a homomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath, then the equivalence relation EΟ• induced by Ο• on A is a congruence relation. Furthermore, if Ο• is a strong, so is EΟ•.


Let fβˆˆΟ„ be an n-ary function symbol. Suppose ai≑bi(modEΟ•) and both f𝑨⁒(a1,…,an) and f𝑨⁒(b1,…,bn) are defined. Then ϕ⁒(ai)=ϕ⁒(bi), and therefore


so f𝑨⁒(a1,…,an)≑f𝑨⁒(b1,…,bn)(modEΟ•). In other words, EΟ• is a congruence relation.

Now, suppose in additionPlanetmathPlanetmath that Ο• is a strong homomorphism. Again, let ai≑bi(modEΟ•). Assume f𝑨⁒(a1,…,an) is defined. Since ϕ⁒(ai)=ϕ⁒(bi), we get


Since Ο• is strong, f𝑨⁒(b1,…,bn) is defined, which means that EΟ• is strong. ∎

Congruences as Subalgebras

If 𝑨 is a partial algebra of type Ο„, then the direct power 𝑨2 is a partial algebra of type Ο„. A binary relationMathworldPlanetmath Θ on A may be viewed as a subset of A2. For each n-ary operationMathworldPlanetmath f𝑨2 on 𝑨2, take the restrictionPlanetmathPlanetmathPlanetmath on Θ, and call it f𝚯. For ai∈Θ, f𝚯⁒(a1,…,an) is defined in Θ iff f𝑨2⁒(a1,…,an) is defined at all, and its value is in Θ. When f𝚯⁒(a1,…,an) is defined in Θ, its value is set as f𝑨2⁒(a1,…,an). This turns 𝚯 into a partial algebra. However, the type of 𝚯 is Ο„ only when f𝚯 is non-empty for each function symbol fβˆˆΟ„. In particular,

Proposition 2.

If Θ is reflexiveMathworldPlanetmathPlanetmath, then Θ is a relative subalgebra of 𝐀2.


Pick any n-ary function symbol fβˆˆΟ„. Then f𝑨⁒(a1,…,an) is defined for some ai∈A. Then f𝑨2⁒((a1,a1),…,(an,an)) is defined and is equal to (f𝑨⁒(a1,…,an),f𝑨⁒(a1,…,an)), which is in Θ, since Θ is reflexive. This shows that f𝚯⁒((a1,a1),…,(an,an)) is defined. As a result, 𝚯 is a partial algebra of type Ο„. Furthermore, by virtue of the way f𝚯 is defined for each fβˆˆΟ„, 𝚯 is a relative subalgebra of 𝑨. ∎

Proposition 3.

An equivalence relation Θ on A is a congruence iff Θ is a subalgebraMathworldPlanetmath of 𝐀2.


First, assume that Θ is a congruence relation on A. Since Θ is reflexive, 𝚯 is a relative subalgebra of 𝑨2. Now, suppose f𝑨2⁒((a1,b1),…,(an,bn)) exists, where ai≑bi(modΘ). Then f𝑨⁒(a1,…,an),f𝑨⁒(b1,…,bn) both exist. Since Θ is a congruence, f𝑨⁒(a1,…,an)≑f𝑨⁒(b1,…,bn)(modΘ). In other words, (f𝑨⁒(a1,…,an),f𝑨⁒(b1,…,bn))∈Θ. Hence 𝚯 is a subalgebra of 𝑨2.

Conversely, assume 𝚯 is a subalgebra of 𝑨2. Suppose (ai,bi)∈Θ and both f𝑨⁒(a1,…,an) and f𝑨⁒(b1,…,bn) are defined. Then f𝑨2⁒((a1,b1),…,(an,bn)) is defined. Since 𝚯 is a subalgebra of 𝑨2, f𝚯⁒((a1,b1),…,(an,bn)) is also defined, and (f𝑨⁒(a1,…,an),f𝑨⁒(b1,…,bn))=f𝑨2⁒((a1,b1),…,(an,bn))=f𝚯⁒((a1,b1),…,(an,bn))∈Θ. This shows that Θ 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 Ο„ and a congruence relation Θ on A, the quotient partial algebra of 𝑨 by Θ is the partial algebra 𝑨/𝚯 whose underlying set is A/Θ, the set of congruence classes, and for each n-ary function symbol fβˆˆΟ„, f𝑨/𝚯⁒([a1],…,[an]) is defined iff there are b1,…,bn∈A such that [ai]=[bi] and f𝑨⁒(b1,…,bn) is defined. When this is the case:


Suppose there are c1,…,cn∈A such that [ai]=[ci], or ai≑ci(modΘ), and f𝑨⁒(c1,…,cn) is defined, then bi≑ci(modΘ) and f𝑨⁒(b1,…,bn)≑f𝑨⁒(c1,…,cn)(modΘ), or, equivalently, [f𝑨⁒(b1,…,bn)]=[f𝑨⁒(c1,…,cn)], so that f𝑨/𝚯 is a well-defined operation.

In addition, it is easy to see that 𝑨/𝚯 is in fact a Ο„-algebraMathworldPlanetmath. For each n-ary fβˆˆΟ„, pick a1,…,an∈A such that f𝑨⁒(a1,…,an) is defined. Then f𝑨/𝚯⁒([a1],…,[an]) is defined, and is equal to [f𝑨⁒(a1,…,an)].

Proposition 4.

Let 𝐀 and Θ be defined as above. Then [β‹…]:𝐀→𝐀/Θ, given by [β‹…]⁒(a)=[a], is a surjectivePlanetmathPlanetmath full homomorphism, and E[β‹…]=Θ. Furthermore, [β‹…] is a strong homomorphism iff Θ is a strong congruence relation.


[β‹…] is obviously surjective. The fact that [β‹…] is a full homomorphism follows directly from the definition of f𝑨/𝚯, for each fβˆˆΟ„. Next, a⁒E[β‹…]⁒b iff [a]=[b] iff a≑b(modΘ). This proves the first statement.

The next statement is proved as follows:

(β‡’). If ai≑bi(modΘ) and f𝑨⁒(a1,…,an) is defined, then f𝑨/𝚯⁒([a1],…,[an]) is defined, which is just f𝑨/𝚯⁒([b1],…,[bn]), and, as [β‹…] is strong, f𝑨⁒(b1,…,bn) is defined, showing that Θ is strong.

(⇐). Suppose f𝑨/𝚯⁒([a1],…,[an]) is defined. Then there are b1,…,bn∈A with ai≑bi(modΘ) such that f𝑨⁒(b1,…,bn) is defined. Since Θ is strong, f𝑨⁒(a1,…,an) is defined as well, which shows that [β‹…] is strong. ∎


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