Las 52 relaciones de equivalencia en un conjunto de 5 elementos se representan como matrices lógicas (los campos de colores, incluidos los de gris claro, representan unos; los campos blancos, ceros). Los índices de filas y columnas de las celdas que no son blancas son los elementos relacionados, mientras que los diferentes colores, distintos del gris claro, indican las clases de equivalencia (cada celda gris claro es su propia clase de equivalencia).
En matemáticas , una relación de equivalencia es una relación binaria que es reflexiva , simétrica y transitiva . La relación de equipolencia entre segmentos de línea en geometría es un ejemplo común de relación de equivalencia. Un ejemplo más simple es la igualdad. Cualquier número es igual a sí mismo (reflexivo). Si , entonces (simétrico). Si y , entonces (transitivo).
Cada relación de equivalencia proporciona una partición del conjunto subyacente en clases de equivalencia disjuntas . Dos elementos del conjunto dado son equivalentes entre sí si y sólo si pertenecen a la misma clase de equivalencia.
Notación
En la literatura se utilizan varias notaciones para indicar que dos elementos de un conjunto son equivalentes con respecto a una relación de equivalencia, las más comunes son " " y " a ≡ b ", que se usan cuando está implícito, y variaciones de " ". " a ≡ R b ", o " " para especificar explícitamente. La no equivalencia puede escribirse " a ≁ b " o " ".
Definición
Una relación binaria en un conjunto se dice que es una relación de equivalencia, si y sólo si es reflexiva, simétrica y transitiva. Es decir, para todos y en
En álgebra relacional , si y son relaciones, entonces la relación compuesta se define de modo que si y sólo si existe tal que y . [nota 1] Esta definición es una generalización de la definición de composición funcional . Las propiedades definitorias de una relación de equivalencia en un conjunto se pueden reformular de la siguiente manera:
Dado un número natural , "es congruente con, módulo " sobre los números enteros . [2]
Dada una función , "tiene la misma imagen que " en los elementos de su dominio . Por ejemplo, y tenga la misma imagen debajo , a saber. .
"Tiene el mismo valor absoluto que" en el conjunto de los números reales
"Tiene el mismo coseno que" en el conjunto de todos los ángulos.
Relaciones que no son equivalencias
La relación "≥" entre números reales es reflexiva y transitiva, pero no simétrica. Por ejemplo, 7 ≥ 5 pero no 5 ≥ 7.
La relación "tiene un factor común mayor que 1 con" entre números naturales mayores que 1, es reflexiva y simétrica, pero no transitiva. Por ejemplo, los números naturales 2 y 6 tienen un factor común mayor que 1, y 6 y 3 tienen un factor común mayor que 1, pero 2 y 3 no tienen un factor común mayor que 1.
La relación vacía R (definida de modo que aRb nunca sea verdadera) en un conjunto X es vagamente simétrica y transitiva; sin embargo, no es reflexivo (a menos que X esté vacío).
La relación "es aproximadamente igual a" entre números reales, incluso si se define con mayor precisión, no es una relación de equivalencia, porque aunque reflexiva y simétrica, no es transitiva, ya que múltiples cambios pequeños pueden acumularse para convertirse en un gran cambio. Sin embargo, si la aproximación se define asintóticamente, por ejemplo diciendo que dos funciones f y g son aproximadamente iguales cerca de algún punto si el límite de f − g es 0 en ese punto, entonces esto define una relación de equivalencia.
La igualdad es a la vez una relación de equivalencia y un orden parcial. La igualdad es también la única relación en un conjunto que es reflexiva, simétrica y antisimétrica. En expresiones algebraicas , las variables iguales se pueden sustituir entre sí, una función que no está disponible para variables relacionadas con equivalencia. Las clases de equivalencia de una relación de equivalencia pueden sustituirse entre sí, pero no los individuos dentro de una clase.
Una relación de equivalencia parcial es transitiva y simétrica. Tal relación es reflexiva si y sólo si es total , es decir, si para todos existe algo [prueba 1]. Por lo tanto, una relación de equivalencia puede definirse alternativamente como una relación simétrica, transitiva y total.
Una relación de congruencia es una relación de equivalencia cuyo dominio es también el conjunto subyacente de una estructura algebraica , y que respeta la estructura adicional. En general, las relaciones de congruencia desempeñan el papel de núcleos de homomorfismos y se puede formar el cociente de una estructura mediante una relación de congruencia. En muchos casos importantes, las relaciones de congruencia tienen una representación alternativa como subestructuras de la estructura en la que se definen (por ejemplo, las relaciones de congruencia en grupos corresponden a los subgrupos normales ).
Si es una relación de equivalencia y es una propiedad de elementos de tal que siempre que sea verdadera si es verdadera, entonces se dice que la propiedad está bien definida o es una clase invariante bajo la relación
Un caso particular frecuente ocurre cuando una función de a otro conjunto si implica entonces se dice que es un morfismo para una clase invariante bajo o simplemente invariante bajo. Esto ocurre, por ejemplo, en la teoría de caracteres de grupos finitos. El último caso de la función se puede expresar mediante un triángulo conmutativo. Véase también invariante . Algunos autores utilizan "compatible con " o simplemente "respeta " en lugar de "invariante bajo ".
De manera más general, una función puede asignar argumentos equivalentes (bajo una relación de equivalencia ) a valores equivalentes (bajo una relación de equivalencia ). Esta función se conoce como morfismo de a
Definiciones importantes relacionadas
Sea , y una relación de equivalencia. A continuación se presentan algunas definiciones y terminología clave:
Clase de equivalencia
Un subconjunto de tales que se cumple para todos y dentro , y nunca para dentro y fuera , se denomina clase de equivalencia de por . Denotemos la clase de equivalencia a la que pertenece. Todos los elementos equivalentes entre sí son también elementos de la misma clase de equivalencia.
conjunto de cocientes
El conjunto de todas las clases de equivalencia de by denotado es el conjunto cociente de by Si es un espacio topológico , existe una forma natural de transformarse en un espacio topológico; consulte Espacio cociente para obtener más detalles.
Proyección
La proyección de es la función definida por la cual asigna elementos de a sus respectivas clases de equivalencia mediante
Teorema sobre proyecciones : [4] Sea la función tal que si entonces Entonces existe una función única tal que If es una sobreyección y luego es una biyección .
Núcleo de equivalencia
El núcleo de equivalencia de una función es la relación de equivalencia ~ definida por El núcleo de equivalencia de una inyección es la relación de identidad .
Dividir
Una partición de X es un conjunto P de subconjuntos no vacíos de X , tal que cada elemento de X es un elemento de un único elemento de P. Cada elemento de P es una celda de la partición. Además, los elementos de P son disjuntos por pares y su unión es X.
Contando particiones
Sea X un conjunto finito con n elementos. Dado que cada relación de equivalencia sobre X corresponde a una partición de X , y viceversa, el número de relaciones de equivalencia sobre X es igual al número de particiones distintas de X , que es el enésimo número de Bell B n :
Teorema fundamental de las relaciones de equivalencia.
Un resultado clave vincula las relaciones de equivalencia y las particiones: [5] [6] [7]
Una relación de equivalencia ~ en un conjunto X particiones X .
Por el contrario, correspondiente a cualquier partición de X , existe una relación de equivalencia ~ en X.
En ambos casos, las celdas de la partición de X son las clases de equivalencia de X por ~. Dado que cada elemento de X pertenece a una celda única de cualquier partición de X , y dado que cada celda de la partición es idéntica a una clase de equivalencia de X por ~, cada elemento de X pertenece a una clase de equivalencia única de X por ~. Por tanto , existe una biyección natural entre el conjunto de todas las relaciones de equivalencia en X y el conjunto de todas las particiones de X.
Comparar relaciones de equivalencia
Si y son dos relaciones de equivalencia en el mismo conjunto , y implica para todos , entonces se dice que es una relación más burda que y es una relación más fina que . De manera equivalente,
es mejor que si cada clase de equivalencia de es un subconjunto de una clase de equivalencia de y, por lo tanto, cada clase de equivalencia de es una unión de clases de equivalencia de .
es mejor que si la partición creada por es un refinamiento de la partición creada por .
La relación de equivalencia de igualdad es la relación de equivalencia más fina de cualquier conjunto, mientras que la relación universal, que relaciona todos los pares de elementos, es la más burda.
La relación " es más fina que " en la colección de todas las relaciones de equivalencia en un conjunto fijo es en sí misma una relación de orden parcial, lo que hace que la colección sea una red geométrica . [8]
Generando relaciones de equivalencia
Dado cualquier conjunto, se puede obtener una relación de equivalencia sobre el conjunto de todas las funciones de la siguiente manera. Dos funciones se consideran equivalentes cuando sus respectivos conjuntos de puntos fijos tienen la misma cardinalidad , correspondiente a ciclos de longitud uno en una permutación .
Una relación de equivalencia es el núcleo de equivalencia de su proyección sobreyectiva [9] Por el contrario, cualquier sobreyección entre conjuntos determina una partición en su dominio, el conjunto de preimágenes de singletons en el codominio . Por tanto, una relación de equivalencia sobre una partición de y una proyección cuyo dominio es son tres formas equivalentes de especificar la misma cosa.
La intersección de cualquier colección de relaciones de equivalencia sobre X (relaciones binarias vistas como un subconjunto de ) también es una relación de equivalencia. Esto produce una forma conveniente de generar una relación de equivalencia: dada cualquier relación binaria R en X , la relación de equivalencia generada por R es la intersección de todas las relaciones de equivalencia que contienen R (también conocida como la relación de equivalencia más pequeña que contiene R ). Concretamente, R genera la relación de equivalencia
si existe un número natural y elementos tales que , , y o , para
La relación de equivalencia generada de esta manera puede ser trivial. Por ejemplo, la relación de equivalencia generada por cualquier orden total en X tiene exactamente una clase de equivalencia, la propia X.
Las relaciones de equivalencia pueden construir nuevos espacios "pegando cosas". Sea X el cuadrado cartesiano unitario y sea ~ la relación de equivalencia en X definida por para todos y para todos. Entonces el espacio cociente se puede identificar naturalmente ( homeomorfismo ) con un toro : tome una hoja de papel cuadrada, dóblela y peguela borde superior e inferior para formar un cilindro, luego doble el cilindro resultante para pegar sus dos extremos abiertos, lo que dará como resultado un toroide.
estructura algebraica
Gran parte de las matemáticas se basa en el estudio de equivalencias y relaciones de orden . La teoría de celosías captura la estructura matemática de las relaciones de orden. Aunque las relaciones de equivalencia son tan omnipresentes en matemáticas como las relaciones de orden, la estructura algebraica de las equivalencias no es tan conocida como la de los órdenes. La primera estructura se basa principalmente en la teoría de grupos y, en menor medida, en la teoría de redes, categorías y grupoides .
Sea '~' una relación de equivalencia sobre algún conjunto A no vacío , llamado universo o conjunto subyacente. Sea G el conjunto de funciones biyectivas sobre A que preservan la estructura de partición de A , lo que significa que para todos y Entonces se cumplen los siguientes tres teoremas conectados: [10]
~ divide A en clases de equivalencia. (Este es el Teorema Fundamental de las Relaciones de Equivalencia , mencionado anteriormente);
Dada una partición de A , G es un grupo de transformación bajo composición, cuyas órbitas son las celdas de la partición; [14]
Dado un grupo de transformación G sobre A , existe una relación de equivalencia ~ sobre A , cuyas clases de equivalencia son las órbitas de G. [15] [16]
En resumen, dada una relación de equivalencia ~ sobre A , existe un grupo de transformación G sobre A cuyas órbitas son las clases de equivalencia de A bajo ~.
Esta caracterización del grupo de transformación de las relaciones de equivalencia difiere fundamentalmente de la forma en que las redes caracterizan las relaciones de orden. Los argumentos de las operaciones de la teoría de la red se encuentran y se unen son elementos de algún universo A. Mientras tanto, los argumentos de las operaciones del grupo de transformación composición e inversa son elementos de un conjunto de biyecciones , A → A.
Pasando a grupos en general, sea H un subgrupo de algún grupo G. Sea ~ una relación de equivalencia en G , tal que Las clases de equivalencia de ~ (también llamadas órbitas de la acción de H sobre G ) son las clases laterales derechas de H en G . Al intercambiar a y b se obtienen las clases laterales izquierdas.
Se puede encontrar un pensamiento relacionado en Rosen (2008: capítulo 10).
Categorías y grupoides
Sea G un conjunto y sea "~" una relación de equivalencia sobre G . Entonces podemos formar un grupoide que represente esta relación de equivalencia de la siguiente manera. Los objetos son los elementos de G , y para dos elementos cualesquiera x e y de G , existe un morfismo único de x a y si y solo si
Las ventajas de considerar una relación de equivalencia como un caso especial de grupoide incluyen:
Mientras que la noción de "relación de equivalencia libre" no existe, la de un grupoide libre en un gráfico dirigido sí existe. Por tanto, tiene sentido hablar de una "presentación de una relación de equivalencia", es decir, una presentación del grupoide correspondiente;
Conjuntos de grupos, acciones grupales , conjuntos y relaciones de equivalencia pueden considerarse casos especiales de la noción de grupoide, un punto de vista que sugiere una serie de analogías;
En muchos contextos, los "cocientes" y, por tanto, las relaciones de equivalencia apropiadas, a menudo llamadas congruencias , son importantes. Esto lleva a la noción de un grupoide interno en una categoría . [17]
Celosías
Las relaciones de equivalencia en cualquier conjunto X , cuando se ordenan por inclusión de conjuntos , forman una red completa , llamada Con X por convención. El mapa canónico ker : X ^ X → Con X , relaciona el monoide X ^ X de todas las funciones en X y Con X . ker es sobreyectivo pero no inyectivo . De manera menos formal, la relación de equivalencia ker en X lleva cada función f : X → X a su núcleo ker f . Asimismo, ker(ker) es una relación de equivalencia en X ^ X .
Relaciones de equivalencia y lógica matemática.
Las relaciones de equivalencia son una fuente fácil de ejemplos o contraejemplos. Por ejemplo, una relación de equivalencia con exactamente dos clases de equivalencia infinitas es un ejemplo sencillo de una teoría que es ω- categórica , pero no categórica para cualquier número cardinal mayor .
Una implicación de la teoría de modelos es que se puede demostrar que las propiedades que definen una relación son independientes entre sí (y por lo tanto son partes necesarias de la definición) si y sólo si, para cada propiedad, se pueden encontrar ejemplos de relaciones que no satisfacen la propiedad dada pero satisfacen todas las demás propiedades. Por lo tanto, se puede demostrar que las tres propiedades que definen las relaciones de equivalencia son mutuamente independientes mediante los tres ejemplos siguientes:
Reflexiva y simétrica : La relación R sobre Z , definida como aRb ↔ " a − b es divisible por al menos uno de 2 o 3". O cualquier relación de dependencia .
Las propiedades definibles en lógica de primer orden que una relación de equivalencia puede poseer o no incluyen:
El número de clases de equivalencia es finito o infinito;
El número de clases de equivalencia es igual al número natural (finito) n ;
Todas las clases de equivalencia tienen cardinalidad infinita ;
El número de elementos en cada clase de equivalencia es el número natural n .
Hasta – Declaración matemática de unicidad, excepto para una estructura equivalente (relación de equivalencia)
Notas
^ A veces, la composición se escribe como o como ; en ambos casos, es la primera relación que se aplica. Consulte el artículo sobre Composición de relaciones para obtener más información.
^ Si: Dado , mantengamos usando la totalidad, entonces por simetría, por lo tanto, por transitividad. — Sólo si: Dado elige entonces por reflexividad.
^ Weisstein, Eric W. "Clase de equivalencia". mathworld.wolfram.com . Consultado el 30 de agosto de 2020 .
^ abc "7.3: Clases de equivalencia". Matemáticas LibreTexts . 2017-09-20 . Consultado el 30 de agosto de 2020 .
^ Halmos, Paul Richard (1914). Teoría de conjuntos ingenua . Nueva York: Springer. pag. 41.ISBN978-0-387-90104-6.
^ Prueba . [11] Deje que la composición de funciones interprete la multiplicación de grupos y la función inversa interprete la inversa de grupo. Entonces G es un grupo bajo composición, lo que significa que y porque G satisface las siguientes cuatro condiciones:
G está cerrado bajo composición . La composición de dos elementos cualesquiera de G existe, porque el dominio y codominio de cualquier elemento de G es A. Además, la composición de las biyecciones es biyectiva ; [12]
Asociados de composición . f ( gh ) = ( fg ) h . Esto es válido para todas las funciones en todos los dominios. [13]
Sean f y g dos elementos cualesquiera de G . En virtud de la definición de G , [ g ( f ( x ))] = [ f ( x )] y [ f ( x )] = [ x ], de modo que [ g ( f ( x ))] = [ x ]. Por lo tanto, G también es un grupo de transformación (y un grupo de automorfismo ) porque la composición de funciones preserva la partición de
^ Dummit, DS y Foote, RM, 2004. Álgebra abstracta , 3ª ed. John Wiley & Sons: 114, Proposición 2.
^ Borceux, F. y Janelidze, G., 2001. Teorías de Galois , Cambridge University Press, ISBN 0-521-80309-8
Referencias
Brown, Ronald, 2006. Topología y grupoides. Librosurge LLC. ISBN 1-4196-2722-8 .
Castellani, E., 2003, "Simetría y equivalencia" en Brading, Katherine y E. Castellani, eds., Simetrías en física: reflexiones filosóficas . Universidad de Cambridge. Prensa: 422–433.
Robert Dilworth y Crawley, Peter, 1973. Teoría algebraica de celosías . Prentice Hall. Capítulo. 12 analiza cómo surgen las relaciones de equivalencia en la teoría de redes .
Higgins, PJ, 1971. Categorías y grupoides. Van Nostrand. Descargable desde 2005 como reimpresión TAC.
John Randolph Lucas , 1973. Tratado sobre el tiempo y el espacio . Londres: Methuen. Sección 31.
Rosen, Joseph (2008) Reglas de simetría: cómo la ciencia y la naturaleza se basan en la simetría . Springer-Verlag. Principalmente capítulos. 9,10.
Raymond Wilder (1965) Introducción a los fundamentos de las matemáticas, segunda edición, capítulos 2-8: Axiomas que definen la equivalencia, págs. 48-50, John Wiley & Sons .