stringtranslate.com

Relación de equivalencia

Las 52 relaciones de equivalencia de un conjunto de 5 elementos se representan como matrices lógicas (los campos de colores, incluidos los de color gris claro, representan los unos; los campos de color blanco, los ceros). Los índices de fila y columna de las celdas que no son de color blanco son los elementos relacionados, mientras que los colores diferentes, distintos del gris claro, indican las clases de equivalencia (cada celda de color 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 una relación de equivalencia. Un ejemplo más simple es la igualdad. Cualquier número es igual a sí mismo (reflexiva). Si , entonces (simétrica). Si y , entonces (transitiva).

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 solo si pertenecen a la misma clase de equivalencia.

Notación

En la literatura se utilizan diversas notaciones para indicar que dos elementos y de un conjunto son equivalentes con respecto a una relación de equivalencia; las más comunes son " " y " ab ", que se utilizan cuando está implícito, y variaciones de " ", " aR b " o " " para especificar de forma explícita. La no equivalencia se puede escribir " ab " 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

Junto con la relación se denomina setoide . La clase de equivalencia de la denotada se define como [1] [2]

Definición alternativa utilizando álgebra relacional

En álgebra relacional , si y son relaciones, entonces la relación compuesta se define de modo que si y solo si existe un 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 pueden entonces reformularse de la siguiente manera:

Ejemplos

Ejemplo sencillo

En el conjunto , la relación es una relación de equivalencia. Los siguientes conjuntos son clases de equivalencia de esta relación:

El conjunto de todas las clases de equivalencia para es Este conjunto es una partición del conjunto con respecto a .

Relaciones de equivalencia

Las siguientes relaciones son todas relaciones de equivalencia:

Relaciones que no son equivalencias

Conexiones con otras relaciones

Bien definida bajo una relación de equivalencia

Si es una relación de equivalencia en y es una propiedad de elementos de tal que siempre que sea verdadero si es verdadero, entonces se dice que la propiedad está bien definida o es una clase invariante bajo la relación.

Un caso particular frecuente ocurre cuando es 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 con la función puede expresarse mediante un triángulo conmutativo. Véase también invariante . Algunos autores usan "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 ). Dicha 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ías clave:

Clase de equivalencia

Un subconjunto de tal que se cumple para todos y en , y nunca para dentro y fuera de , se llama clase de equivalencia de por . Sea la clase de equivalencia a la que pertenece. Todos los elementos de que son equivalentes entre sí también son elementos de la misma clase de equivalencia.

Conjunto cociente

El conjunto de todas las clases de equivalencia de por denotado es el conjunto cociente de por Si es un espacio topológico , existe una forma natural de transformarlo en un espacio topológico; consulte Espacio cociente para los 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 única función tal que Si es una sobreyección y entonces 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 , de modo 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. Como a cada relación de equivalencia sobre X le corresponde 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 n º número de Bell B n :

( Fórmula de Dobinski ).

Teorema fundamental de las relaciones de equivalencia

Un resultado clave vincula las relaciones de equivalencia y las particiones: [5] [6] [7]

En ambos casos, las celdas de la partición de X son las clases de equivalencia de X por ~. Como cada elemento de X pertenece a una celda única de cualquier partición de X , y como 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 lo 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 .

Comparación de 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 . Equivalentemente,

La relación de equivalencia de igualdad es la relación de equivalencia más fina en 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 el conjunto de todas las relaciones de equivalencia en un conjunto fijo es en sí misma una relación de orden parcial, lo que convierte al conjunto en una red geométrica . [8]

Generando relaciones 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, X misma.

Estructura algebraica

Gran parte de las matemáticas se basa en el estudio de las equivalencias y las relaciones de orden . La teoría de retículos capta 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 retículos, categorías y grupoides .

Teoría de grupos

Así como las relaciones de orden se fundamentan en conjuntos ordenados , conjuntos cerrados bajo el supremo y el ínfimo por pares , las relaciones de equivalencia se fundamentan en conjuntos particionados , que son conjuntos cerrados bajo biyecciones que preservan la estructura de partición. Dado que todas estas biyecciones asignan una clase de equivalencia sobre sí misma, dichas biyecciones también se conocen como permutaciones . Por lo tanto, los grupos de permutación (también conocidos como grupos de transformación ) y la noción relacionada de órbita arrojan luz sobre la estructura matemática de las relaciones de equivalencia.

Sea '~' una relación de equivalencia sobre un conjunto no vacío A , 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 conexos: [10]

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 de las relaciones de equivalencia por parte de un grupo de transformación difiere fundamentalmente de la forma en que las redes caracterizan las relaciones de orden. Los argumentos de las operaciones de la teoría de redes encuentro y unión 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 , AA .

Pasando a los 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 . Intercambiando a y b se obtienen las clases laterales izquierdas.

Se puede encontrar un pensamiento relacionado en Rosen (2008: cap. 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 cualesquiera dos elementos 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 un grupoide incluyen:

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 . La función canónica ker  : X ^ XCon X , relaciona el monoide X ^ X de todas las funciones en X y Con X . ker es sobreyectiva pero no inyectiva . De manera menos formal, la relación de equivalencia ker en X , lleva cada función f  : XX a su núcleo ker f . Del mismo modo, 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 ningún número cardinal mayor .

Una implicación de la teoría de modelos es que las propiedades que definen una relación pueden demostrarse independientes entre sí (y, por lo tanto, son partes necesarias de la definición) si y solo 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, las tres propiedades que definen las relaciones de equivalencia pueden demostrarse mutuamente independientes mediante los tres ejemplos siguientes:

Las propiedades definibles en lógica de primer orden que una relación de equivalencia puede o no poseer incluyen:

Véase también

Notas

  1. ^ 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.
  1. ^ Si: Dado, se mantiene usando totalidad, entonces por simetría, por lo tanto por transitividad. — Sólo si: Dado , se elige, entonces por reflexividad.
  1. ^ Weisstein, Eric W. "Clase de equivalencia". mathworld.wolfram.com . Consultado el 30 de agosto de 2020 .
  2. ^ abc «7.3: Clases de equivalencia». Matemáticas LibreTexts . 2017-09-20 . Consultado el 2020-08-30 .
  3. ^ Halmos, Paul Richard (1914). Teoría de conjuntos ingenua . Nueva York: Springer. pag. 41.ISBN 978-0-387-90104-6.
  4. ^ Garrett Birkhoff y Saunders Mac Lane , 1999 (1967). Álgebra , 3.ª ed., pág. 35, Th. 19. Chelsea.
  5. ^ Wallace, DAR, 1998. Grupos, anillos y campos . p. 31, Th. 8. Springer-Verlag.
  6. ^ Dummit, DS y Foote, RM, 2004. Álgebra abstracta , 3.ª ed., pág. 3, Prop. 2. John Wiley & Sons.
  7. ^ Karel Hrbacek y Thomas Jech (1999) Introducción a la teoría de conjuntos , 3.ª edición, páginas 29-32, Marcel Dekker
  8. ^ Birkhoff, Garrett (1995), Lattice Theory , Colloquium Publications, vol. 25 (3.ª ed.), American Mathematical Society, ISBN 9780821810255. Sección IV.9, Teorema 12, página 95
  9. ^ Garrett Birkhoff y Saunders Mac Lane , 1999 (1967). Álgebra , 3.ª ed., pág. 33, Th. 18. Chelsea.
  10. Rosen (2008), pp. 243–45. Menos claro es el §10.3 de Bas van Fraassen , 1989. Laws and Symmetry . Oxford Univ. Press.
  11. ^ Bas van Fraassen, 1989. Leyes y simetría . Oxford Univ. Press: 246.
  12. ^ Wallace, DAR, 1998. Grupos, anillos y campos . Springer-Verlag: 22, Th. 6.
  13. ^ Wallace, DAR, 1998. Grupos, anillos y campos . Springer-Verlag: 24, Th. 7.
  14. ^ Demostración . [11] Sea la función composición la que interpreta la multiplicación de grupos, y la función inversa la que interpreta la inversa de grupos. 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]
    • Existencia de la función identidad . La función identidad , I ( x ) = x , es un elemento obvio de G ;
    • Existencia de función inversa . Toda función biyectiva g tiene una inversa g −1 , tal que gg −1 = I ;
    • La composición asocia . 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 es también un grupo de transformación (y un grupo de automorfismos ) porque la composición de funciones preserva la partición de
  15. ^ Wallace, DAR, 1998. Grupos, anillos y campos . Springer-Verlag: 202, Th. 6.
  16. ^ Dummit, DS y Foote, RM, 2004. Álgebra abstracta , 3.ª ed. John Wiley & Sons: 114, Prop. 2.
  17. ^ Borceux, F. y Janelidze, G., 2001. Teorías de Galois , Cambridge University Press, ISBN 0-521-80309-8 

Referencias

Enlaces externos