Relación de equivalencia

En matemáticas , una relación de equivalencia es un relación binaria entre dos elementos de una establecer que los agrupa como "equivalente" de alguna manera. Sean a, b, yc son elementos arbitrarios de algún conjunto X. A continuación, "un ~ b" o "a ≡ b" denota que a es equivalente a b.

Una relación de equivalencia "~" es reflexiva, simétrica , y transitivo. En otras palabras, la siguiente debe mantener para "~" para ser una relación de equivalencia en X:

Una relación de equivalencia particiones de un conjunto en varias subconjuntos disjuntos, llamados clases de equivalencia. Todos los elementos de una clase de equivalencia dado son equivalentes entre sí, y ningún elemento es equivalente con cualquier elemento de una clase diferente.

• La reflexividad: un ~ a
• Simetría: si un ~ b entonces b ~ a
• La transitividad: si un ~ b y b ~ c, entonces a ~ c.

La una clase de equivalencia en "~", denotado [a], es el subconjunto de X cuyos elementos b son tales que a ~ b X. junto con "~" que se denomina una setoid.

Ejemplos de relaciones de equivalencia

Una relación de equivalencia es la ubicua igualdad ("=") relación entre los elementos de cualquier conjunto. Otros ejemplos incluyen:

• "Tiene el mismo cumpleaños que" en el conjunto de todas las personas, teniendo en cuenta la teoría de conjuntos ingenua.
• "Es similar a" o "congruente a" en el conjunto de todos los triángulos .
• "¿Es congruente con modulo n "en los números enteros .
• "Tiene el mismo imagen bajo una función "en los elementos de la dominio de la función.
• Equivalencia lógica de frases lógicas.
• "Es isomorfo "en la modelos de un conjunto de frases.
• En algunas teorías axiomática de conjuntos distintos de la canónica ZFC (por ejemplo, Nuevos Fundamentos y teorías afines):
  • La similitud en el universo de bien ordenamientos da lugar a clases de equivalencia que son los números ordinales .
  • Equinumerosity en el universo de:
    • Conjuntos finitos da lugar a clases de equivalencia que son los números naturales .
    • Conjuntos infinitos da lugar a la equivalencia clases que son el transfinitos números cardinales .
• Sean a, b, c, d ser números naturales , y dejar que (a, b) y (c, d) pares ordenados de tales números. Entonces la clases de equivalencia en virtud de la relación (a, b) ~ (c, d) son:
  • Los enteros si a + d = b + c;
  • Positivos números racionales si ad = bc.
• Deja que (r _n) y (s _n) ser cualquiera de los dos Secuencias de Cauchy de números racionales. Los números reales son las clases de equivalencia de la relación (r _n) ~ (s _n), si la secuencia (r _n - s _n) tiene límite 0.
• Las relaciones de verdes son cinco las relaciones de equivalencia sobre los elementos de un semigrupo.
• "Es paralelo a "en el conjunto de subespacios de un espacio afín.

Ejemplos de relaciones que no son equivalencias

• El "≥" relación entre los números reales es reflexiva y transitiva, pero no simétrica. Por ejemplo, 7 ≥ 5 no implica que 5 ≥ 7. Es, sin embargo, una orden parcial.
• 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. (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 R vacío en un no vacío conjunto X (es decir aRb nunca es cierto) se vacuamente simétrica y transitiva, pero no reflexiva. (Si X también está vacía, entonces R es reflexiva.)
• La relación "es aproximadamente igual a" entre los números reales u otras cosas, incluso si se define con mayor precisión, no es una relación de equivalencia, ya que si bien reflexiva y simétrica, no es transitiva, ya que múltiples cambios pequeños pueden acumular para convertirse en un gran cambio.
• La relación "es un hermano de" en el conjunto de todos los seres humanos no es una relación de equivalencia. Aunque siblinghood es simétrica (si A es hermano de B, entonces B es un hermano de A) no es ni reflexiva (nadie es un hermano de él mismo), ni transitiva (ya que si A es hermano de B, entonces B es un hermano de A, pero A no es un hermano de A). En lugar de ser transitivo, siblinghood es "casi transitiva", lo que significa que si A ~ B, y B ~ C y A ≠ C, entonces A ~ C.
• El concepto de paralelismo en la geometría ordenada no es simétrica y es, por lo tanto, no es una relación de equivalencia.
• Una relación de equivalencia en un conjunto no es nunca una relación de equivalencia en un superconjunto adecuado de ese conjunto. Por ejemplo R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3, 2), (3,3)} es una relación de equivalencia en {1,2,3}, pero no en {1,2,3,4} o en el número natural. El problema es que la reflexividad falla porque (4,4) no es miembro.

Conexión con otras relaciones

La Congruencia es una relación de equivalencia cuyo dominio X es también el conjunto subyacente de una estructura algebraica , y que respeta la estructura adicional. En general, las relaciones de congruencia juegan el papel de núcleos de homomorfismos, y el cociente de una estructura por una relación de congruencia se pueden formar. En muchos casos importantes relaciones de congruencia tienen una representación alternativa como subestructuras de la estructura sobre la que se definen. Por ejemplo, las relaciones de la congruencia en grupos corresponden a la subgrupos normales.

Solicitar y equivalencia relaciones son a la vez transitiva, pero sólo equivalencia relaciones son simétricas también. Si la simetría se debilita a antisimetría, el resultado es una orden parcial.

La relación de equivalencia parcial es transitiva y simétrica, pero no reflexiva.

• Transitiva y simétrica implican reflexiva si y sólo si para todo a, b ∈ X, a ~ b se define siempre.
  

La relación de dependencia es reflexiva y simétrica, pero no transitiva.
La preorden es reflexiva y transitiva, pero ni simétrica ni antisimétrica.
La orden parcial estricto es transitiva solo.

Relaciones de equivalencia por lo tanto puede ser visto como la culminación de una jerarquía de relaciones de orden.

Clase de equivalencia, conjunto cociente, partición

Sea X un conjunto no vacío con elementos típicos a y b. Algunas definiciones:

• El conjunto de todos los ayb para que un ~ b sostiene compensar un clase de equivalencia de X por ~. Deje que [a] =: {x ∈ X: x ~ a} denotar la clase de equivalencia a la que pertenece una. Luego todos los elementos de X equivalentes entre sí, son también elementos de la misma clase de equivalencia: ∀ a, b ∈ X (a ~ b ↔ [a] = [b]).
• El conjunto de todas las posibles clases de equivalencia de X por ~, denota X / ~ =: {[x]: x ∈ X}, es el cociente conjunto de X por ~. Si X es una espacio topológico, hay una manera natural de la transformación de X / ~ en un espacio topológico; ver espacio cociente para los detalles.
• La proyección de ~ es la función π: X → X / ~, definido por π (x) = [x], elementos de mapeo de X en sus respectivas clases de equivalencia de ~.
  

Teorema sobre proyecciones (Birkhoff y Mac Lane, 1999: 35, 19 Th.): Sea la función f: X → B sea tal que un ~ b → f (a) = f (b). Entonces existe una función g único: X / ~ → B, tal que f = g π. Si f es una surjection y un b ↔ ~ f (A) = f (b), entonces g es una biyección.

• El núcleo de la equivalencia de una función f es la relación de equivalencia, denota Ef, de tal manera que xEfy ↔ f (x) = f (y). El kernel de equivalencia de una inyección es la relación de identidad.
• La partición de X es un conjunto P de subconjuntos de X, de manera que cada elemento de X es un elemento de un solo elemento de P. Cada elemento de P es una célula de la partición. Además, los elementos de P son disjuntas dos a dos y su unión es X.

Teorema ("teorema fundamental de las relaciones de equivalencia": Wallace 1998:. 31, Th 8; Dummit y Foote 2004:. 3, la Proposición 2):

• Una relación de equivalencia ~ tabiques X.
• A la inversa, correspondiente a cualquier partición de X, existe una relación de equivalencia ~ en X.

En ambos casos, las células de la partición de X son las clases de equivalencia de X por ~. Dado que cada elemento de X pertenece a una célula única de cualquier partición de X, y desde 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 no es un producto natural biyección entre el conjunto de todas las posibles relaciones de equivalencia en X y el conjunto de todas las particiones de X.

Contando posibles particiones. Sea X un conjunto finito con n elementos. Puesto que cada relación de equivalencia sobre X corresponde a una partición de X, y viceversa, el número de posibles relaciones de equivalencia en X es igual al número de particiones distintas de X, que es el n-ésimo Campana número B _n:

La generación de relaciones de equivalencia

• Dado cualquier conjunto X, existe una relación de equivalencia sobre el conjunto de todas las posibles funciones X → X. Dos de estas funciones se consideran equivalentes cuando sus respectivos conjuntos de puntos fijos tienen el mismo cardinalidad, correspondiente a los ciclos de longitud uno en una permutación . Funciones equivalentes de esta manera forman una clase de equivalencia en X ^2, y éstas clases de equivalencia partición X ^2.

• Una relación de equivalencia ~ en X es el núcleo de su equivalencia surjective π proyección: X → X / ~. (Birkhoff y Mac Lane, 1999: 33 Ju 18.). A la inversa, cualquier surjection entre series determina una partición en su dominio, el conjunto de preimages de únicos en el codominio. Por lo tanto una relación de equivalencia sobre X, una partición de X, y una proyección cuyo dominio es X, son tres formas equivalentes de la especificación de la misma cosa.

• La intersección de dos relaciones de equivalencia sobre X (visto como un subconjunto de X × X) también es una relación de equivalencia. Esto produce una forma conveniente de generar una relación de equivalencia: dado ninguna relación R binario en X, la relación de equivalencia generada por R es la relación de equivalencia más pequeña que contiene R. Concretamente, R genera la relación de equivalencia a ~ b si y sólo si existen elementos x _1, x _2, ..., x _n en X tal que a = x _1, b = x _n, y (x _i, x _{i + 1)} ∈ R o (x _{i 1,} x _i) ∈ R, i = 1, ..., n -1.

Tenga en cuenta que la relación de equivalencia generado de esta forma puede ser trivial. Por ejemplo, la relación de equivalencia ~ generado por:

• La relación ≤ binario tiene exactamente una clase de equivalencia, en sí X, ya que x ~ y para todo x e y;
• Una relación antisimétrica tiene clases de equivalencia que son el únicos de x.

• Sea r cualquier tipo de relación en la X. Entonces R ∪ r ^-1 es un relación simétrica. La transitiva cierre s de r ∪ r ^-1 asegura que s es transitiva y reflexiva. Por otra parte, s es la relación de equivalencia "más pequeño" que contiene r y r / s parcialmente pedidos X / s.

• Relaciones de equivalencia pueden construir nuevos espacios por "pegado cosas juntos." Sea X la unidad Cuadrado cartesiano [0,1] × [0,1], y dejar ~ ser la relación de equivalencia en X definida por ∀ a, b ∈ [0,1] ((a, 0) ~ (a, 1) ∧ (0 , b) ~ (1, b)). Entonces la espacio cociente X / ~ se pueden identificar de forma natural con un toro : tomar un pedazo cuadrado de papel, doblar y pegar juntos el borde superior e inferior para formar un cilindro, y doblar el cilindro resultante para pegar juntos sus dos extremos abiertos, lo que resulta en un toroide .

Estructura algebraica

Celosías modulares

Las posibles relaciones de equivalencia en cualquier conjunto X, cuando ordenado por inclusión conjunto , forman un celosía modular, denominado Con X por convención. La canónica mapa ker: X ∧ X → Con X, relaciona el monoide X ^ X de todas las funciones de X y Con X. ker es surjective pero no inyectiva. Menos formalmente, el ker relación de equivalencia en X, toma cada función f: X → X a su kernel ker f. Del mismo modo, ker (ker) es una relación de equivalencia en X ^ X.

La teoría de grupos

Es muy bien conocido que la teoría de celosía captura la estructura matemática de relaciones de orden. Es menos conocido que grupos de transformación (algunos autores prefieren grupos de permutaciones) y su órbitas arrojan luz sobre la estructura matemática de las relaciones de equivalencia. Tal como relaciones de orden se basan en conjuntos ordenados, conjuntos cerrados bajo pairwise supremo y ínfimo, relaciones de equivalencia se basan en conjuntos de particiones, conjuntos cerrados bajo biyecciones preservando la estructura de partición. Dado que todos estos biyecciones asignar una clase de equivalencia sobre sí misma, tales biyecciones también se conocen como permutaciones .

Deje que '~' denota una relación de equivalencia sobre un conjunto no vacío A, llamado el universo o conjunto subyacente. Sea G denota el conjunto de funciones biyectivas sobre A que preservan la estructura de partición de A: ∀ x ∈ A ∀ g ∈ G (g (x) ∈ [x]). A continuación, los siguientes tres teoremas conectados tienen (Van Fraassen 1989: § 10.3):

• ~ Un particiones en clases de equivalencia. (Este es el teorema fundamental de las relaciones de equivalencia, mencionados anteriormente);
• Dada una partición de A, G es una grupo de transformación en virtud de la composición, cuya órbitas son la células de la partición ‡;
• Dada una grupo de transformaciones G sobre A, no existe una relación de equivalencia ~ sobre A, cuyas clases de equivalencia son los órbitas de G. (Wallace 1998: 202, Th 6; Dummit y Foote 2004:. 114, Prop. 2).

En suma, da una relación de equivalencia ~ sobre A, existe una grupo de transformaciones G sobre A cuya órbitas son las clases de equivalencia de A bajo ~.

Esta caracterización grupo transformación de las relaciones de equivalencia difiere fundamentalmente de la forma celosías caracterizan relaciones de orden. Los argumentos de las operaciones de la teoría reticular conocer y unirse son elementos de un universo A. Mientras tanto, los argumentos del Grupo de Operaciones de transformación composición y inversa son elementos de un conjunto de biyecciones, A → A.

Mudarse a grupos en general, sea H un subgrupo de algún grupo G. Vamos ~ haber una relación de equivalencia en G, tal que un ~ b ↔ (ab ^-1 ∈ H). Las clases de equivalencia de ~ -también llamados las órbitas de la acción de H en G -son la derecha clases laterales de H en G. Intercambiando ayb se obtienen las clases laterales izquierdos.

Para más información sobre la teoría de grupos y relaciones de equivalencia, véase Lucas (1973: § 31).

‡ Prueba (adaptado de Van Fraassen 1989: 246). Deje que la composición de funciones interpretar la multiplicación del grupo, y la función inversa interpretar inversa grupo. Entonces G es un grupo bajo composición, lo que significa que ∀ x ∈ A ∀ g ∈ G ([g (x)] = [x]), porque G satisface las siguientes cuatro condiciones:

• G es cerrado bajo la composición . Existe La composición de cualquiera de los dos elementos de G, porque la dominio y codomain de cualquier elemento de G es A. Además, la composición de biyecciones es biyectiva (Wallace 1998: 22, Th. 6);
• Existencia de elemento de identidad. La función identidad, I (x) = x, es un elemento evidente de G;
• Existencia de la función inversa . Cada función biyectiva g tiene una inversa g ^-1, de tal manera que gg ^-1 = I;
• Composición asociados . f (gh) = (fg) h. Esto es válido para todas las funciones más de todos los dominios (Wallace 1998:. 24, Th 7).

Sea f yg dos elementos 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 una grupo de automorfismos) debido a la composición de funciones conserva la partición de A.

Teoría de la categoría

La composición de morfismos centrales teoría de la categoría, que se denota aquí por concatenación, generaliza la composición de funciones centrales de grupos de transformación. Los axiomas de la teoría de categorías afirmar que la composición de Morfismos asociados, y que la izquierda y la derecha existen morfismos identidad. Si todos los morfismos en una categoría eran tener "inversas", la categoría se asemejaría a un grupo de transformación, cuya estrecha relación con la equivalencia relaciones apenas se ha explicado. Un morfismo f se puede decir que tiene una inversa cuando f es una automorphism, es decir, el dominio y codominio de f son idénticos, y no existe un morfismo g tal que morfismo fg = gf = identidad. De ahí que el concepto teórico-categoría más cercana a una relación de equivalencia es una categoría cuyos morfismos son todos los automorfismos.

Relaciones de equivalencia y la lógica matemática

Relaciones de equivalencia son una fuente de ejemplos o contraejemplos. Por ejemplo, una relación de equivalencia con exactamente dos clases de equivalencia infinitos es un ejemplo sencillo de una teoría que es ω- categórica, pero no categórico para cualquier mayor número cardinal .

Una implicación de la teoría de modelos es que las propiedades que definen una relación pueden ser probadas independientes entre sí (y por tanto necesarias partes de la definición) si y sólo si, para cada propiedad, se pueden encontrar ejemplos de las relaciones que no correspondan a la propiedad dada al tiempo que satisface todos los demás propiedades. De ahí que los tres la definición de propiedades de las relaciones de equivalencia puede demostrarse mutuamente independiente por los tres ejemplos siguientes:

• Reflexiva y transitiva: La relación ≤ en N. O cualquier hacer un pedido;
• Simétrica y transitiva: La relación R en N, definida como aRb ↔ ab ≠ 0. O cualquier relación de equivalencia parcial;
• Reflexiva y simétrica: La relación R en Z, definido como aRb ↔ "a - b es divisible por al menos uno de 2 ó 3." O cualquier relación de dependencia.

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

• El número de clases de equivalencia es finito o infinito;
• El número de clases de equivalencia es igual a la (finito) número natural n;
• Todas las clases de equivalencia tienen infinita cardinalidad;
• El número de elementos de cada clase de equivalencia es el número natural n.

Equivalencia prevista Euclid

Euclides 's The Elements incluye lo siguiente "Noción común 1":

Las cosas que son iguales a la misma cosa también son iguales entre sí.

Hoy en día, la propiedad descrita por Noción común 1 se llama Euclidiana (en sustitución de "igual" por "están en relación con"). Los siguientes conecta teorema Relaciones euclidianas y las relaciones de equivalencia:

Teorema. Si una relación es euclidiana y reflexivo, también es simétrica y transitiva.

Prueba:

• (Arc ∧ BRC) → aRb [a / c] = (Ara ∧ BRA) → aRb [reflexiva; borrar T ∧] = bRa → aRb. Por lo tanto R es simétrica .
• (Arc ∧ BRC) → aRb [simetría] = (Arc ∧ CRB) → aRb. Por lo tanto R es transitivo.

Por lo tanto una relación de equivalencia es una relación que es euclidiano y reflexivo. Los elementos no menciona ni la simetría ni reflexividad, y Euclides probablemente hubiese considerado que la reflexividad de la igualdad demasiado obvio como para justificar una mención explícita. Si esto (y teniendo la "igualdad" como una relación abstracta de uso múltiple) se concede, una lectura benéfica de Noción común 1 acreditaría Euclides con ser el primero en concebir las relaciones de equivalencia y su importancia en sistemas deductivos.