congruence relation on an algebraic system
Let (A,O) be an algebraic system. A congruence relation, or simply a congruence
ℭ on A
-
1.
is an equivalence relation
on A; if (a,b)∈ℭ we write a≡b(modℭ), and
-
2.
respects every n-ary operator on A: if ωA is an n-ary operator on A (ω∈O), and for any ai,bi∈A, i=1,…,n, we have
ai≡bi(modℭ) implies ωA(a1,…,an)≡ωA(b1,…,bn)(modℭ).
For example, A2 and ΔA:={(a,a)∣a∈A} are both congruence relations on A. ΔA is called the trivial congruence (on A). A proper congruence relation is one not equal to A2.
Remarks.
-
•
ℭ is a congruence relation on A if and only if ℭ is an equivalence relation on A and a subalgebra
of the product
(http://planetmath.org/DirectProductOfAlgebras) A×A.
-
•
The set of congruences of an algebraic system is a complete lattice
. The meet is the usual set intersection
. The join (of an arbitrary number of congruences) is the join of the underlying equivalence relations (http://planetmath.org/PartitionsFormALattice). This join corresponds to the subalgebra (of A×A) generated by the union of the underlying sets of the congruences. The lattice of congruences on A is denoted by Con(A).
-
•
(restriction
) If ℭ is a congruence on A and B is a subalgebra of A, then ℭB defined by ℭ∩(B×B) is a congruence on B. The equivalence of ℭB is obvious. For any n-ary operator ωB inherited from A’s ωA, if ai≡bi(modℭB), then ωB(a1,…,an)=ωA(a1,…,an)≡ωA(b1,…,bn)=ωB(b1,…,bn)(modℭ). Since both ωB(a1,…,an) and ωB(b1,…,bn) are in B, ωB(a1,…,an)≡ωB(b1,…,bn)(modℭB) as well. ℭB is the congruence restricted to B.
-
•
(extension
) Again, let ℭ be a congruence on A and B a subalgebra of A. Define Bℭ by {a∈A∣(a,b)∈ℭ and b∈B}. In other words, a∈Bℭ iff a≡b(modℭ) for some b∈B. We assert that Bℭ is a subalgebra of A. If ωA is an n-ary operator on A and a1,…,an∈Bℭ, then ai≡bi(modℭ), so ωA(a1,…,an)≡ωA(b1,…,bn)(modℭ). Since ωA(b1,…,bn)∈B, ωA(a1,…,an)∈Bℭ. Therefore, Bℭ is a subalgebra. Because B⊆Bℭ, we call it the extension of B by ℭ.
-
•
Let B be a subset of A×A. The smallest congruence ℭ on A such that a≡b(modℭ) for all a,b∈B is called the congruence generated by B. ℭ is often written ⟨B⟩. When B is a singleton {(a,b)}, then we call ⟨B⟩ a principal congruence, and denote it by ⟨(a,b)⟩.
Quotient algebra
Given an algebraic structure (A,O) and a congruence relation ℭ on A, we can construct a new O-algebra (A/ℭ,O), as follows: elements of A/ℭ are of the form [a], where a∈A. We set
[a]=[b] iff a≡b(modℭ). |
Furthermore, for each n-ary operator ωA on A, define ωA/ℭ by
ωA/ℭ([a1],…,[an]):=[ωA(a1,…,an)]. |
It is easy to see that ωA/ℭ is a well-defined operator on A/ℭ. The O-algebra thus constructed is called the quotient algebra of A over ℭ.
Remark. The bracket [⋅]:A→A/ℭ is in fact an epimorphism, with kernel (http://planetmath.org/KernelOfAHomomorphismBetweenAlgebraicSystems) ker([⋅])=ℭ. This means that every congruence of an algebraic system A is the kernel of some homomorphism
from A. [⋅] is usually written [⋅]ℭ to signify its association with ℭ.
References
- 1 G. Grätzer: Universal Algebra, 2nd Edition, Springer, New York (1978).
Title | congruence relation on an algebraic system |
Canonical name | CongruenceRelationOnAnAlgebraicSystem |
Date of creation | 2013-03-22 16:26:23 |
Last modified on | 2013-03-22 16:26:23 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 33 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 08A30 |
Related topic | Congruence3 |
Related topic | Congruence2 |
Related topic | CongruenceInAlgebraicNumberField |
Related topic | PolynomialCongruence |
Related topic | QuotientCategory |
Related topic | CategoryOfAdditiveFractions |
Defines | congruence |
Defines | congruence relation |
Defines | quotient algebra |
Defines | proper congruence |
Defines | trivial congruence |
Defines | non-trivial congruence |
Defines | congruence restricted to a subalgebra |
Defines | extension of a subalgebra by a congruence |
Defines | principal congruence |
Defines | congruence generated by |