PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (498)
Corrections (24)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
congruence relation on an algebraic system (Definition)

Let $ (A,O)$ be an algebraic system. A congruence relation, or simply a congruence $ \mathfrak{C}$ on $ A$

  1. is an equivalence relation on $ A$; if $ (a,b)\in \mathfrak{C}$ we write $ a\equiv b\pmod {\mathfrak{C}}$, and
  2. respects every $ n$-ary operator on $ A$: if $ \omega_A$ is an $ n$-ary operator on $ A$ ( $ \omega\in O$), and for any $ a_i,b_i\in A$, $ i=1,\ldots,n$, we have
    $\displaystyle a_i\equiv b_i\pmod {\mathfrak{C}}$    implies $\displaystyle \qquad \omega_A(a_1,\ldots,a_n)\equiv \omega_A(b_1,\ldots,b_n) \pmod {\mathfrak{C}}.$

For example, $ A^2$ and $ \Delta_A:=\lbrace (a,a)\mid a\in A\rbrace$ are both congruence relations on $ A$. $ \Delta_A$ is called the trivial congruence (on $ A$). A proper congruence relation is one not equal to $ A^2$.

Remarks.

  • $ \mathfrak{C}$ is a congruence relation on $ A$ if and only if $ \mathfrak{C}$ is an equivalence relation on $ A$ and a subalgebra of the product $ A\times 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. This join corresponds to the subalgebra (of $ A\times A$) generated by the union of the underlying sets of the congruences. The lattice of congruences on $ A$ is denoted by $ \operatorname{Con}(A)$.
  • (restriction) If $ \mathfrak{C}$ is a congruence on $ A$ and $ B$ is a subalgebra of $ A$, then $ \mathfrak{C}_B$ defined by $ \mathfrak{C}\cap (B\times B)$ is a congruence on $ B$. The equivalence of $ \mathfrak{C}_B$ is obvious. For any $ n$-ary operator $ \omega_B$ inherited from $ A$'s $ \omega_A$, if $ a_i \equiv b_i \pmod {\mathfrak{C}_B}$, then $ \omega_B(a_1,\ldots,a_n)=\omega_A(a_1,\ldots, a_n)\equiv \omega_A(b_1,\ldots,b_n)=\omega_B(b_1,\ldots, b_n) \pmod {\mathfrak{C}}$. Since both $ \omega_B(a_1,\ldots,a_n)$ and $ \omega_B(b_1,\ldots,b_n)$ are in $ B$, $ \omega_B(a_1,\ldots,a_n)\equiv \omega_B(b_1,\ldots, b_n) \pmod {\mathfrak{C}_B}$ as well. $ \mathfrak{C}_B$ is the congruence restricted to $ B$.
  • (extension) Again, let $ \mathfrak{C}$ be a congruence on $ A$ and $ B$ a subalgebra of $ A$. Define $ B^{\mathfrak{C}}$ by $ \lbrace a\in A\mid (a,b)\in \mathfrak{C}$ and $ b\in B\rbrace$. In other words, $ a\in B^{\mathfrak{C}}$ iff $ a \equiv b \pmod {\mathfrak{C}}$ for some $ b\in B$. We assert that $ B^{\mathfrak{C}}$ is a subalgebra of $ A$. If $ \omega_A$ is an $ n$-ary operator on $ A$ and $ a_1,\ldots,a_n\in B^{\mathfrak{C}}$, then $ a_i\equiv b_i \pmod {\mathfrak{C}}$, so $ \omega_A(a_1,\ldots,a_n)\equiv \omega_A(b_1,\ldots,b_n) \pmod {\mathfrak{C}}$. Since $ \omega_A(b_1,\ldots,b_n)\in B$, $ \omega_A(a_1,\ldots,a_n)\in B^{\mathfrak{C}}$. Therefore, $ B^{\mathfrak{C}}$ is a subalgebra. Because $ B\subseteq B^{\mathfrak{C}}$, we call it the extension of $ B$ by $ \mathfrak{C}$.
  • Let $ B$ be a subset of $ A\times A$. The smallest congruence $ \mathfrak{C}$ on $ A$ such that $ a\equiv b\pmod {\mathfrak{C}}$ for all $ a,b\in B$ is called the congruence generated by $ B$. $ \mathfrak{C}$ is often written $ \langle B\rangle$. When $ B$ is a singleton $ \lbrace (a,b)\rbrace$, then we call $ \langle B\rangle$ a principal congruence, and denote it by $ \langle (a,b)\rangle$.

Quotient algebra

Given an algebraic structure $ (A,O)$ and a congruence relation $ \mathfrak{C}$ on $ A$, we can construct a new $ O$-algebra $ (A/\mathfrak{C},O)$, as follows: elements of $ A/\mathfrak{C}$ are of the form $ [a]$, where $ a\in A$. We set

$\displaystyle [a]=[b]$ iff $\displaystyle a\equiv b\pmod {\mathfrak{C}}.$
Furthermore, for each $ n$-ary operator $ \omega_A$ on $ A$, define $ \omega_{A/\mathfrak{C}}$ by
$\displaystyle \omega_{A/\mathfrak{C}}\big([a_1],\ldots,[a_n]\big):=\big[\omega_A(a_1,\ldots,a_n)\big].$
It is easy to see that $ \omega_{A/\mathfrak{C}}$ is a well-defined operator on $ A/\mathfrak{C}$. The $ O$-algebra thus constructed is called the quotient algebra of $ A$ over $ \mathfrak{C}$.

Remark. The bracket $ [\cdot]:A\to A/\mathfrak{C}$ is in fact an epimorphism, with kernel $ \ker([\cdot])=\mathfrak{C}$. This means that every congruence of an algebraic system $ A$ is the kernel of some homomorphism from $ A$. $ [\cdot]$ is usually written $ [\cdot]_{\mathfrak{C}}$ to signify its association with $ \mathfrak{C}$.

Bibliography

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



"congruence relation on an algebraic system" is owned by CWoo. [ full author list (3) ]
(view preamble)

View style:

See Also: congruence, congruence, congruence in algebraic number field, polynomial congruence

Also defines:  congruence, congruence relation, quotient algebra, proper congruence, trivial congruence, non-trivial congruence, congruence restricted to a subalgebra, extension of a subalgebra by a congruence, principal congruence, congruence generated by

Attachments:
simple algebraic system (Definition) by CWoo
congruence lattice (Definition) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: homomorphism, kernel, epimorphism, well-defined, singleton, subset, iff, extension, restricted, obvious, equivalence, restriction, lattice of congruences, union, generated by, number, join, intersection, meet, complete lattice, congruences, subalgebra, operator, equivalence relation, algebraic system
There are 17 references to this entry.

This is version 30 of congruence relation on an algebraic system, born on 2006-11-29, modified 2008-08-12.
Object id is 8594, canonical name is CongruenceRelationOnAnAlgebraicSystem.
Accessed 4310 times total.

Classification:
AMS MSC: 08A30 (General algebraic systems :: Algebraic structures :: Subalgebras, congruence relations)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)