Quotient (universal algebra)

In mathematics, a quotient algebra, (where algebra means algebraic structure in the sense of universal algebra), also called a factor algebra, is obtained by partitioning the elements of an algebra into equivalence classes given by a congruence relation, that is an equivalence relation that is additionally compatible with all the operations of the algebra, in the formal sense described below.

Compatible relation

Let A be a set (of the elements of an algebra ${\mathcal {A}}$), and let E be an equivalence relation on the set A. The relation E is said to be compatible with (or have the substitution property with respect to) an n-ary operation f if for all $a_{1},a_{2},\ldots ,a_{n},b_{1},b_{2},\ldots ,b_{n}\in A$ whenever $(a_{1},b_{1})\in E,(a_{2},b_{2})\in E,\ldots ,(a_{n},b_{n})\in E$ implies $(f(a_{1},a_{2},\ldots ,a_{n}),f(b_{1},b_{2},\ldots ,b_{n}))\in E$. An equivalence relation compatible with all the operations of an algebra is called a congruence.

Quotient algebras and homomorphisms

A set A can be partitioned in equivalence classes given by an equivalence relation E, and usually called a quotient set, and denoted A/E. For an algebra ${\mathcal {A}}$, it is straightforward to define the operations induced on A/E if E is a congruence. Specifically, for any operation $f_{i}^{\mathcal {A}}$ of arity $n_{i}$ in ${\mathcal {A}}$ (where the superscript simply denotes that it's an operation in ${\mathcal {A}}$) define $f_{i}^{{\mathcal {A}}/E}:(A/E)^{n_{i}}\to A/E$ as $f_{i}^{{\mathcal {A}}/E}([a_{1}]_{E},\ldots ,[a_{n_{i}}]_{E})=[f_{i}^{\mathcal {A}}(a_{1},\ldots ,a_{n_{i}})]_{E}$, where $[a]_{E}$ denotes the equivalence class of a modulo E.

For an algebra ${\mathcal {A}}=(A,(f_{i}^{\mathcal {A}})_{i\in I})$, given a congruence E on ${\mathcal {A}}$, the algebra ${\mathcal {A}}/E=(A/E,(f_{i}^{{\mathcal {A}}/E})_{i\in I})$ is called the quotient algebra (or factor algebra) of ${\mathcal {A}}$ modulo E. There is a natural homomorphism from ${\mathcal {A}}$ to ${\mathcal {A}}/E$ mapping every element to its equivalence class. In fact, every homomorphism h determines a congruence relation; the kernel of the homomorphism, $\mathop {\mathrm {ker} } \,h=\{(a,a')\in A\times A|h(a)=h(a')\}$.

Given an algebra ${\mathcal {A}}$, a homomorphism h thus defines two algebras homomorphic to ${\mathcal {A}}$, the image h(${\mathcal {A}}$) and ${\mathcal {A}}/\mathop {\mathrm {ker} } \,h$ The two are isomorphic, a result known as the homomorphic image theorem or as the first isomorphism theorem for universal algebra. Formally, let $h:{\mathcal {A}}\to {\mathcal {B}}$ be a surjective homomorphism. Then, there exists a unique isomorphism g from ${\mathcal {A}}/\mathop {\mathrm {ker} } \,h$ onto ${\mathcal {B}}$ such that g composed with the natural homomorphism induced by $\mathop {\mathrm {ker} } \,h$ equals h.

Congruence lattice

For every algebra ${\mathcal {A}}$ on the set A, the identity relation on A, and $A\times A$ are trivial congruences. An algebra with no other congruences is called simple.

Let $\mathrm {Con} ({\mathcal {A}})$ be the set of congruences on the algebra ${\mathcal {A}}$. Because congruences are closed under intersection, we can define a meet operation: $\wedge :\mathrm {Con} ({\mathcal {A}})\times \mathrm {Con} ({\mathcal {A}})\to \mathrm {Con} ({\mathcal {A}})$ by simply taking the intersection of the congruences $E_{1}\wedge E_{2}=E_{1}\cap E_{2}$.

On the other hand, congruences are not closed under union. However, we can define the closure of any binary relation E, with respect to a fixed algebra ${\mathcal {A}}$, such that it is a congruence, in the following way: $\langle E\rangle _{\mathcal {A}}=\bigcap \{F\in \mathrm {Con} ({\mathcal {A}})|E\subseteq F\}$. Note that the (congruence) closure of a binary relation depends on the operations in ${\mathcal {A}}$, not just on the carrier set. Now define $\vee :\mathrm {Con} ({\mathcal {A}})\times \mathrm {Con} ({\mathcal {A}})\to \mathrm {Con} ({\mathcal {A}})$ as $E_{1}\vee E_{2}=\langle E_{1}\cup E_{2}\rangle _{\mathcal {A}}$.

For every algebra ${\mathcal {A}}$, $({\mathcal {A}},\wedge ,\vee )$ with the two operations defined above forms a lattice, called the congruence lattice of ${\mathcal {A}}$.

Maltsev conditions

If two congruences permute (commute) with the composition of relations as operation, i.e.$\alpha \circ \beta =\beta \circ \alpha$ then their join (in the congruence lattice) is equal to their composition: $\alpha \circ \beta =\alpha \vee \beta$. An algebra is called congruence-permutable if every pair of its congruences permutes; likewise a variety is said to be congruence-permutable if all its members are congruence-permutable algebras.

In 1954, Anatoly Maltsev established the following characterization of congruence-permutable varieties: a variety is congruence permutable if and only if there exist a ternary term q(x, y, z) such that q(x, y, y) ≈ x ≈ q(y, y, x); this is called a Maltsev term and varieties with this property are called Maltsev varieties. Maltsev's characterization explains a large number of similar results in groups (take q = xy⁻¹z), rings, quasigroups (take q = (x / (y \ y))(y \ z)), complemented lattices, Heyting algebras etc. Furthermore, every congruence-permutable algebra is congruence-modular, i.e. its lattice of congruences is modular lattice as well; the converse is not true however.

After Maltsev's result, other researchers found characterizations based on conditions similar to that found by Maltsev but for other kinds of properties, e.g. in 1967 Bjarni Jónsson found the conditions for varieties having congruence lattices that are distributive (thus called congruence-distributive varieties). Generically, such conditions are called Maltsev conditions.

This line of research led to the Pixley–Wille algorithm for generating Maltsev conditions associated with congruence identities.

See also

• quotient ring
• Congruence lattice problem
• Lattice of subgroups

References

• Klaus Denecke; Shelly L. Wismath (2009). Universal algebra and coalgebra. World Scientific. pp. 14–17. ISBN 978-981-283-745-5.
• Purna Chandra Biswal (2005). Discrete mathematics and graph theory. PHI Learning Pvt. Ltd. p. 215. ISBN 978-81-203-2721-4.
• Clifford Bergman (2011). Universal Algebra: Fundamentals and Selected Topics. CRC Press. pp. 122–124, 137 (Maltsev varieties). ISBN 978-1-4398-5129-6.