Relación de congruencia

El ejemplo prototípico de una relación de congruencia es el módulo de congruencia ${\displaystyle n}$ en el conjunto de los números enteros. Para un número entero positivo dado ${\displaystyle n}$ , otros dos enteros ${\displaystyle a}$ y ${\displaystyle b}$ se llaman congruentes de módulo ${\displaystyle n}$, escrito

${\displaystyle a\equiv b{\pmod {n}}}$

si ${\displaystyle a-b}$ es divisible por ${\displaystyle n}$ (o equivalentemente, si ${\displaystyle a}$ y ${\displaystyle b}$ tienen el mismo resto cuando se dividen por ${\displaystyle n}$).

Por ejemplo, ${\displaystyle 37}$ y ${\displaystyle 57}$ son congruentes módulo ${\displaystyle 10}$ ,

${\displaystyle 37\equiv 57{\pmod {10}}}$

ya que ${\displaystyle 37-57=-20}$ es un múltiplo de 10, o equivalentemente, ya que tanto ${\displaystyle 37}$ como ${\displaystyle 57}$ tienen un resto de ${\displaystyle 7}$ cuando se dividen por ${\displaystyle 10}$ .

El módulo de congruencia ${\displaystyle n}$ (para un ${\displaystyle n}$ fijo) es compatible tanto con la suma como con la multiplicación entre enteros. Es decir,

si

${\displaystyle a_{1}\equiv a_{2}{\pmod {n}}}$ y ${\displaystyle b_{1}\equiv b_{2}{\pmod {n}}}$

luego

${\displaystyle a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {n}}}$ y ${\displaystyle a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}}$

La correspondiente suma y multiplicación de clases de equivalencia se conoce como aritmética modular. Desde el punto de vista del álgebra abstracta, el módulo de congruencia ${\displaystyle n}$ es una relación de congruencia en el anillo de los números enteros y el módulo aritmético ${\displaystyle n}$ se verifica en el anillo cociente correspondiente.

La definición de una congruencia depende del tipo de estructura algebraica en consideración. Se pueden hacer definiciones particulares de congruencia para grupos, anillos, espacios vectoriales, módulos, semigrupos o retículos. El tema común es que una congruencia es una relación de equivalencia en un objeto algebraico que es compatible con la estructura algebraica, en el sentido de que las operaciones están bien definidas en las clases de equivalencia.

Por ejemplo, un grupo es un objeto algebraico que consiste en un conjunto junto con una sola operación binaria, que satisface ciertos axiomas. Si ${\displaystyle G}$ es un grupo con la operación ${\displaystyle \ast }$, una relación de congruencia en ${\displaystyle G}$ es una relación de equivalencia ${\displaystyle \equiv }$ entre los elementos de ${\displaystyle G}$ satisfaciendo que

${\displaystyle g_{1}\equiv g_{2}\ \ \,}$ y ${\displaystyle \ \ \,h_{1}\equiv h_{2}\implies g_{1}\ast h_{1}\equiv g_{2}\ast h_{2}}$

para todo ${\displaystyle g_{1}}$, ${\displaystyle g_{2}}$, ${\displaystyle h_{1}}$, ${\displaystyle h_{2}\in G}$. Para una congruencia en un grupo, la clase de equivalencia que contiene el elemento identidad es siempre un subgrupo normal, y las otras clases de equivalencia son las clases laterales de este subgrupo. Juntas, estas clases de equivalencia son los elementos de un grupo cociente.

Cuando una estructura algebraica incluye más de una operación, se requiere que las relaciones de congruencia sean compatibles con cada operación. Por ejemplo, un anillo posee suma y multiplicación, y una relación de congruencia en un anillo debe satisfacer

${\displaystyle r_{1}+s_{1}\equiv r_{2}+s_{2}{\text{ and }}r_{1}s_{1}\equiv r_{2}s_{2}}$

cuando ${\displaystyle r_{1}\equiv r_{2}{\text{ and }}s_{1}\equiv s_{2}}$ . Para una congruencia en un anillo, la clase de equivalencia que contiene 0 es siempre un ideal de dos lados, y las dos operaciones en el conjunto de clases de equivalencia definen el anillo cociente correspondiente.

La noción general de una relación de congruencia puede tener una definición formal en el contexto del álgebra universal, un campo que estudia ideas comunes a todas las estructuras algebraicas. En este contexto, una relación de congruencia es una relación de equivalencia ${\displaystyle \equiv }$ en una estructura algebraica que satisface

${\displaystyle \mu \left(a_{1}{\text{, }}a_{2}{\text{, }}\ldots {}{\text{, }}a_{n}\right)\equiv \mu \left(a_{1}'{\text{, }}a_{2}'{\text{, }}\ldots {}{\text{, }}a_{n}'\right)}$

para cada operación ${\displaystyle n}$-aria ${\displaystyle \mu }$ y todos los elementos ${\displaystyle a_{1}{\text{, }}\ldots {}{\text{, }}a_{n}{\text{, }}a_{1}'{\text{, }}\ldots {}{\text{, }}a_{n}'}$ tales que ${\displaystyle a_{i}\equiv a_{i}'}$ para cada ${\displaystyle i=1,...,n.}$

Si ${\displaystyle f:A\,\rightarrow B}$ es un homomorfismo entre dos estructuras algebraicas (como el homomorfismo de grupos o una aplicación lineal entre espacios vectoriales), entonces la relación ${\displaystyle R}$ definida por

${\displaystyle a_{1}\,R\,a_{2}}$ si y solo si ${\displaystyle f\left(a_{1}\right)=f\left(a_{2}\right)}$

Es una relación de congruencia. Según el primer teorema del isomorfismo, la imagen de A bajo ${\displaystyle f}$ es una subestructura de B isomorfa al cociente de A por esta congruencia.

En el caso particular de los grupos, las relaciones de congruencia pueden describirse en términos elementales de la siguiente manera: si G es un grupo (con elemento de identidad e y operación *) y ~ es una relación binaria en G, entonces ~ es una congruencia siempre que:

1. Dado cualquier elemento a de G, a ~ a (reflexividad);
2. Teniendo en cuenta todos los elementos a y b de G, si a ~ b, entonces b ~ a (simetría);
3. Teniendo en cuenta todos los elementos a, b, y c de G, si a ~ b y b ~ c, entonces a ~ c (transitividad);
4. Dados los elementos a, a', b y b' de G, si a ~ a ' y b ~ b', entonces a * b ~ a' * b' ;
5. Dados los elementos a y a' de G, si a ~ a', entonces a⁻¹ ~ a' ⁻¹ (esto puede demostrarse a partir de las otras cuatro propiedades, por lo que es estrictamente hablando redundante).

Las condiciones 1, 2 y 3 dicen que ~ es una relación de equivalencia.

Una congruencia ~ está determinada completamente por el conjunto {a ∈ G : a ~ e} de aquellos elementos de G que son congruentes con el elemento identidad, y este conjunto es un subgrupo normal. Específicamente, a ~ b si y solo si b⁻¹ * a ~ e . Entonces, en lugar de hablar de congruencias sobre grupos, generalmente se habla en términos de subgrupos normales; de hecho, cada congruencia corresponde únicamente a algún subgrupo normal de G.

La idea se generaliza en el álgebra universal: una relación de congruencia en un álgebra A es un subconjunto del producto directo A × A que es una relación de equivalencia en A y un subalgebra de A×A.

El núcleo de un homomorfismo es siempre una congruencia. De hecho, cada congruencia surge como un núcleo. Para una congruencia dada ~ en A, al conjunto A/~ de clases de equivalencia se le puede dar la estructura de un álgebra de forma natural, el álgebra cociente. La función que asigna cada elemento de A a su clase de equivalencia es un homomorfismo, y el núcleo de este homomorfismo es ~.

La retícula Con(A) de todas las relaciones de congruencia en un álgebra A es algebraica.

John M. Howie describió cómo la teoría del semigrupo ilustra las relaciones de congruencia en el álgebra universal:

En un grupo, se determina una congruencia si se conoce una sola clase de congruencia, en particular si se conoce el subgrupo normal que es la clase que contiene la identidad. De manera similar, en un anillo se determina una congruencia si se conoce el ideal, que es la clase de congruencia que contiene el cero. En los semigrupos no existe un hecho tan afortunado y, por lo tanto, nos enfrentamos a la necesidad de estudiar congruencias como tales. Más que cualquier otra cosa, es esta necesidad la que le da a la teoría del semigrupo su aspecto característico. Los semigrupos son, de hecho, el primer y más simple tipo de álgebra a la que se deben aplicar los métodos de álgebra universal...[3]

• Tabla de congruencias
• Teorema de congruencia lineal
• Problema de la retícula de congruencia

• Horn and Johnson, Matrix Analysis, Cambridge University Press, 1985. ISBN 0-521-38632-2. (La Sección 4.5 discute la congruencia de las matrices)
• Rosen, Kenneth H (2012). Discrete Mathematics and Its Applications. McGraw-Hill Education. ISBN 978-0077418939. Rosen, Kenneth H (2012). Discrete Mathematics and Its Applications. McGraw-Hill Education. ISBN 978-0077418939. Rosen, Kenneth H (2012). Discrete Mathematics and Its Applications. McGraw-Hill Education. ISBN 978-0077418939.