Equivalencia

Equivalencia

Relación de equivalencia

En matemáticas , una relación de equivalencia es, vagamente, una relación que especifica la forma de partición de un conjunto de tal manera que cada elemento del conjunto es exactamente uno de los bloques en la partición, y la unión de todos los bloques es igual al conjunto original. Dos elementos del conjunto se consideran equivalentes (con respecto a la relación de equivalencia) si y sólo si se trata de elementos del mismo bloque.

Notación

A pesar de notaciones diferentes se utilizan en la literatura para denotar que dos elementos de una y b de un conjunto son equivalentes con respecto a una relación de equivalencia R , los más comunes son “ un ~ b “y” un ≡ b “, que se utilizan cuando R es la relación obvia que se hace referencia, y las variaciones de “ un ~ I b “,” un ≡ R b “, o” aRb “. [editar ] Definición

Una propuesta relación binaria ~ en un conjunto A se dice que es una relación de equivalencia si y sólo si es reflexiva, simétrica y transitiva. De manera equivalente, para todos uno , b y c en A :

un ~ una . ( reflexividad ) si un ~ b entonces b ~ una . ( simetría ) si un ~ b y b ~ c entonces un ~ c . ( Transitividad )

A junto con la relación ~ se llama setoid . La clase de equivalencia de un bajo ~, denotada [ uno ], se define como[a] = \b\in A .

La reflexividad se desprende de la simetría y la transitividad si para cada elemento de un ∈ A , existe otro elemento b ∈ A tal que un ~ b sostiene. Sin embargo, la reflexividad no se deduce de la simetría y la transitividad solo. Por ejemplo, dejar que un ser el conjunto de los enteros, y que dos elementos de un estar relacionado si ambos son números pares. Esta relación es claramente simétrica y transitiva, pero en vista de la existencia de números impares, no es reflexivo.

Por otra parte, que una el conjunto de los enteros, y que dos elementos de A están vinculadas si su diferencia es aún más. Esta es una relación de equivalencia, que las particiones de los enteros en dos clases de equivalencia, los pares e impares enteros. [ editar ] Ejemplos [ editar ] Relaciones de Equivalencia

A continuación se enumeran todas las relaciones de equivalencia:

“Tiene el mismo cumpleaños como” el conjunto de todas las personas. “Es similar a” o “congruente con” el conjunto de todos los triángulos . “¿Es congruente con módulo n “en la enteros . “Tiene la misma imagen en una función “en los elementos del dominio de la función . “Es paralelo a “en el conjunto de subespacios de un espacio afín .

[ editar ] Las relaciones que no son equivalencias

La relación “≥” entre los números reales es reflexiva y transitiva, pero no simétrica. Por ejemplo, 7 ≥ 5 no implica que el 5 ≥ 7. Es, sin embargo, un orden parcial . La relación “tiene un factor común mayor que 1 con “entre números naturales mayor que 1, es reflexiva y simétrica, pero no transitiva. (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, 2 y 3, pero no tienen un factor común mayor que 1). La relación vacía R en un no-vacío conjunto X (es decir, aRb no es cierto) es vacuamente simétrica y transitiva, pero no reflexiva. (Si X es también vacía, entonces R es reflexiva.) La relación “es aproximadamente igual a” entre los números reales, aunque con más precisión, no es una relación de equivalencia, porque si bien reflexiva y simétrica, no es transitiva, ya que varios pequeños cambios se pueden acumular para convertirse en un gran cambio. Sin embargo, si la aproximación se define asintóticamente, por ejemplo al decir que dos funciones f y g son aproximadamente iguales, cerca de un punto si el límite de f - g es 0 en ese punto, entonces esto define una relación de equivalencia. La relación “es un hermano de” (utilizado para connotar pares de personas distintas que tienen los mismos padres) en el conjunto de todos los seres humanos no es una relación de equivalencia. Aunque la hermandad es simétrica (si A es un hermano de B , entonces B es un hermano de A ) y transitiva en cualquier 3 personas diferentes (si A es un hermano de B y C es un hermano de B , entonces A es un hermano de C, proporcionan una no es C ), no es reflexiva ( A no puede ser un hermano de una ).

[ editar ] Conexiones con otras relaciones

Un orden parcial es una relación que es reflexiva , antisimétrica y transitiva . Una relación de 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 desempeñar el papel de los núcleos de homomorfismos, y el cociente de una estructura por una relación de congruencia puede ser formado. En muchos casos importantes relaciones de congruencia tiene una representación alternativa como subestructuras de la estructura sobre la que se definen. Por ejemplo, las relaciones de congruencia en los grupos corresponden a los subgrupos normales . 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. Un orden parcial estricto es irreflexiva, transitiva y asimétrica . Una relación de equivalencia parcial es transitiva y simétrica. Transitiva y simétrica implican reflexiva si y sólo si para todo un ∈ X existe b ∈ X tal que un ~ b . Una relación con la tolerancia es reflexiva y simétrica. Un preorden es reflexiva y transitiva. [ editar ] Bueno-definedness en una relación de equivalencia

Si ~ es una relación de equivalencia en X y P ( x ) es una característica de los elementos de X , que como cada vez que x ~ y , P ( x ) es verdadera si P ( y ) es verdad, entonces la propiedad P se dice que estar bien definidos o un invariante de clase en la relación ~.

Un caso particular frecuente se produce cuando f es una función de X a otro conjunto Y , si x 1 ~ x 2 implica f ( x 1 ) = f ( x 2 ) entonces f se dice que es un morfismo de ~, un invariante de clase bajo ~ o, simplemente, invariante bajo ~. Esto ocurre, por ejemplo, en la teoría del carácter de los grupos finitos. El último caso con la función f puede ser expresada por un triángulo conmutativa. Véase también invariante . Algunos autores utilizan “compatible con ~” o simplemente “respeta ~” en lugar de “invariante bajo ~”.

De manera más general, un mapa puede equivalente argumentos de la función (en una relación de equivalencia ~ Un ) a valores equivalentes (en una relación de equivalencia ~ B ). Esta función se conoce como un morfismo de ~ A y ~ B . [ editar ] clase de equivalencia, juego de cociente, partición

Vamos X un conjunto no vacío, y dejar quea,b\in X. Algunas definiciones: [ editar ] clase de equivalencia Artículo principal: clases de equivalencia

El conjunto de todos uno y b para que un ~ b tiene conforman una clase de equivalencia de X por ~. Vamos a[a] := \x \in X denota la clase de equivalencia a la que uno pertenece. A continuación, todos los elementos de X equivalentes entre sí son también elementos de la misma clase de equivalencia. [ editar ] Coeficiente de conjunto Artículo principal: conjunto cociente

El conjunto de todas las clases de equivalencia posible de X por ~, denotada X/\sim := \[x] , Es el conjunto cociente de X por ~. Si X es un espacio topológico , no es una forma natural de la transformación de X / ~ en un espacio topológico, ver el espacio cociente de los detalles. [ editar ] Proyección Artículo principal: Proyección (álgebra relacional)

La proyección de ~ es la función\pi: X \to X/\sim definido por π ( x ) = [ x ​​] el cual los elementos de los mapas X en sus respectivas clases de equivalencia de ~.

Teorema de las proyecciones : [ 1 ] Sea la función f : X → B tal que un ~ b → f ( uno ) = f ( b ). Entonces hay una única función g : X / ~ → B , tal que f = g π. Si f es una surjection y un ~ b ↔ f ( uno ) = f ( b ), entonces g es una biyección .

[ editar ] Equivalencia del núcleo

El núcleo de la equivalencia de una función f es la relación de equivalencia ~ definida porx\sim y \iff f(x) = f(y). El núcleo de la equivalencia de una inyección es la relación de identidad . [ editar ] Partición Artículo principal: Partición de un conjunto

Una partición de X un conjunto P de subconjuntos no vacíos de X , de tal manera que cada elemento de X es un elemento de un solo elemento de P . Cada elemento de P es una celda de la partición. Por otra parte, los elementos de P son disjuntos por pares y su unión es X . [ editar ] Contar las posibles particiones

Que X es 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 posibles relaciones de equivalencia en X es igual al número de particiones distintas de X , que es el enésimo número de Bell B n :

B_n = \frac{1}ē\sum_{k=0}^\infty \frac{k^n}{k!},

donde la anterior es una de las formas de escribir el enésimo número de Bell. [ editar ] Teorema fundamental de las relaciones de equivalencia

Un resultado clave de los vínculos de relaciones de equivalencia y particiones: [ 2 ] [ 3 ]

Una relación de equivalencia ~ en un conjunto X particiones X . Por el contrario, corresponde a una 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 ~. Puesto que cada elemento de X pertenece a una única célula de cualquier partición de X , y ya que cada célula de la partición es idéntica a una clase de equivalencia de X por ~, cada elemento de X pertenece a una equivalencia de clase única de X por ~. Así pues, es natural biyección del conjunto de todas las posibles relaciones de equivalencia en X y el conjunto de todas las particiones de X . [ editar ] Comparación de las relaciones de equivalencia

Si ~ y ≈ dos relaciones de equivalencia en el mismo conjunto S , y un ~ b implica una ≈ b para todo uno , b ∈ S , entonces ≈ se dice que es una más gruesa que la relación ~ y ~ es una fina relación de ≈ . De manera equivalente,

~ Es más fina 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 más fina que ≈ si la partición creada por ~ es un refinamiento de la partición creada por ≈.

La relación con la igualdad de equivalencia es la mejor relación de equivalencia en cualquier conjunto, mientras que la relación trivial que hace que todos los pares de elementos relacionados es la más grosera.

La relación “~ es más fina que ≈” en la recopilación de todas las relaciones de equivalencia en un conjunto fijo es en sí una relación de orden parcial. [ editar ] Generación de las relaciones de equivalencia

Dado cualquier conjunto X , existe una relación de equivalencia sobre el conjunto [ X → X ] de todas las funciones posibles X → X . Dos funciones se consideran equivalentes cuando sus respectivos conjuntos de puntos fijos tienen la misma cardinalidad , correspondientes a los ciclos de una duración de una permutación . equivalente Funciones de esta manera formar una clase de equivalencia de [ X → X ], y estas clases de equivalencia partición [ X → X ].

Una relación de equivalencia ~ en X es el núcleo de la equivalencia de sus sobreyectiva proyección π: X → X / ~. [ 4 ] Por el contrario, cualquier surjection entre conjuntos determina una partición en su dominio , el conjunto de preimages de únicos en el codominio . Así, una relación de equivalencia en X una partición de X , y una proyección cuyo dominio es X , son tres formas equivalentes de especificar la misma cosa.

La intersección de cualquier colección de relaciones de equivalencia sobre X (visto como un subconjunto de X × X ) es también una relación de equivalencia. Esto proporciona una forma cómoda de generar una relación de equivalencia: dado cualquier relación binaria R sobre X , la relación de equivalencia generadas por R es la más pequeña relación de equivalencia que contiene R . En concreto, R genera la relación de equivalencia uno ~ b si y sólo si existen elementos x 1 , x 2 , …, x n en X tal que uno = 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 ~ generados por:

Cualquier orden total en X tiene exactamente una clase de equivalencia, X sí mismo, ya que x ~ y para todo x y y ; Cualquier subconjunto de la relación de identidad en X tiene clases de equivalencia que son los únicos de X .

las relaciones de equivalencia puede construir nuevos espacios de “pegar cosas juntos.” Que X es la unidad cartesiana cuadrado [0,1] × [0,1], y dejar que ~ la relación de equivalencia en X definida por ∀ uno , b ∈ [0,1] (( uno , 0) ~ ( uno , 1) ∧ (0, b ) ~ (1, b )). Entonces el espacio cociente X / ~ puede ser de origen natural identificado con un toro : tomar un trozo cuadrado de papel, doblar y pegar el borde superior e inferior para formar un cilindro, y doblar el cilindro resultante con el fin de aglutinar sus dos extremos abiertos , dando lugar a un toro.

[ editar ] Estructura algebraica

Gran parte de las matemáticas se basa en el estudio de equivalencias y relaciones de orden . teoría de red captura la estructura matemática de las relaciones de orden. A pesar de que las relaciones de equivalencia son tan ubicuos en las matemáticas como las relaciones de orden, la estructura algebraica de equivalencias no es tan conocido como el de los pedidos. La antigua 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 . [ editar ] Teoría de grupos

Así como para las relaciones se basan en conjuntos ordenados , conjuntos cerrados en pares supremo y ínfimo relaciones de equivalencia, se basan en conjuntos de particiones , que son conjuntos cerrados bajo biyecciones y preservar la estructura de la partición. Puesto que todas las biyecciones como asignar una clase de equivalencia sobre sí mismo, biyecciones como también se conocen como las permutaciones . Por lo tanto los grupos de permutaciones (también conocido como grupos de transformación ) y la noción relacionada de la órbita de arrojar luz sobre la estructura matemática de las relaciones de equivalencia.

Vamos a ~ ‘indican una relación de equivalencia sobre algunas conjunto no vacío A , llamado el universo o conjunto subyacente. Que G denota el conjunto de funciones biyectiva más de una que preservan la estructura de particiones de un : ∀ x ∈ A ∀ g ∈ G ( g ( x ) ∈ [ x ]). A continuación, los siguientes tres teoremas relacionada espera: [ 5 ]

~ Particiones A en clases de equivalencia. (Este es el teorema fundamental de las relaciones de equivalencia, mencionado más arriba); Dada una partición de A , G es un grupo de transformaciones en la composición, cuyas órbitas son las células de la partición ‡; Dado un grupo de transformaciones G sobre una , existe una relación de equivalencia ~ sobre una , cuyas clases de equivalencia son las órbitas de G . [ 6 ] [ 7 ]

En resumen, dada una relación de equivalencia ~ sobre una , existe un grupo de transformaciones G sobre un cuyas órbitas son las clases de equivalencia de un bajo ~.

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

Pasando a los grupos en general, que H sea un subgrupo de algunos grupos G . Vamos a ~ ser una relación de equivalencia en G , tal que un ~ b ↔ ( ab −1 ∈ H ). Las clases de equivalencia de ~-también llamado de las órbitas de la acción de H en G -son el derecho de clases laterales de H en G . Intercambiar una y b se obtiene la clases por la izquierda.

‡ prueba . [ 8 ] Que la composición de la función interpretar la multiplicación de grupo, y la función inversa interpretar inversa grupo. Entonces G es un grupo bajo la composición, lo que significa que ∀ x ∈ A ∀ g ∈ G ([ g ( x )] = [ x ​​]), ya que G cumple los cuatro requisitos siguientes:

G es cerrado bajo la composición . La composición de dos elementos de G existe, porque el dominio y el codominio de cualquier elemento de G es un . Por otra parte, la composición de biyecciones es biyectiva ; [ 9 ] Existencia de elemento de identidad . La función de la identidad , que ( x ) = x , es un elemento obvio de G ; Existencia de una función inversa . Cada función biyectiva g tiene una inversa g −1 , de manera que gg −1 = I ; Composición de los asociados . f ( gh ) = ( fg ) h . Esto es válido para todas las funciones en todos los dominios. [ 10 ] Que f y g se cualquiera de los 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 un grupo de transformación (y un grupo de automorfismos ), ya que la composición de la función conserva la partición de una .\square

pensamiento relacionados se pueden encontrar en Rosen (2008: chpt 10.). [ editar ] Categorías y grupoides

La composición de morfismos central en la teoría de categorías , que se denota aquí por concatenación, generaliza la composición de funciones centrales a los grupos de transformación. Los axiomas de la teoría de la categoría afirman que la composición de morfismos asociados, y que la izquierda y la derecha morfismos identidad existe para cualquier morfismo.

Si un morfismo f tiene una inversa, f es un isomorfismo , es decir, existe un morfismo g de tal manera que las composiciones fg y gf igualdad de los morfismos de identidad adecuados. De ahí el concepto de la teoría de la categoría más cercana a una relación de equivalencia es un pequeño) categoría (cuyos morfismos son isomorfismos. grupoide es otro nombre para una categoría pequeña de este tipo.

Vamos a G como un conjunto y dejar que “~” denotan una relación de equivalencia en G . Entonces podemos formar un grupoide que representa esta relación de equivalencia de la siguiente manera. Los objetos son los elementos de G , y para cualquier par de elementos x e y de G , existe un único morfismo desde x a y si y sólo si x ~ y . Los elementos x y y son “equivalentes”, si hay un elemento g de la grupoide de x de y . Es posible que muchos de estos g , cada uno de ellos puede ser considerado como un claro “prueba” de que x y y son equivalentes.

Las ventajas de considerar una relación de equivalencia como un caso especial de un grupoide incluyen:

Considerando que la noción de “relación de equivalencia libre” no existe, la de un grupoide libre en un grafo dirigido hace. Por lo tanto, tiene sentido hablar de una “presentación de una relación de equivalencia”, es decir, una presentación de la grupoide correspondientes; Los bloques de grupos, las acciones de grupo , juegos, y las relaciones de equivalencia se puede considerar como casos especiales de la noción de grupoide, un punto de vista que sugiere una serie de analogías; En muchos contextos “quotienting”, y por lo tanto, la equivalencia de relaciones adecuadas a menudo llamadas congruencias , son importantes. Esto lleva a la noción de un grupoide interior de una categoría. [ 11 ]

[ editar ] Rejas

La equivalencia de las relaciones posibles en cualquier conjunto X , cuando es ordenado por la inclusión conjunto , forman una red completa , llamada 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 sobreyectiva pero no inyectiva . Menos formalmente, la relación de equivalencia ker en X , toma cada función f : X → X a su núcleo ker f . Del mismo modo, ker (ker) es una relación de equivalencia en X ^ X . [ editar ] Relaciones de equivalencia y la lógica matemática

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

Una implicación de la teoría de modelos es que las propiedades que definen una relación se puede probar independientes entre sí (y por lo tanto las partes necesarias de la definición) si y sólo si, para cada propiedad, se pueden encontrar ejemplos de relaciones que no satisfagan los bienes entregados al tiempo que satisface todas las otras propiedades. Por lo tanto las tres propiedades que definen las relaciones de equivalencia se puede demostrar independientes entre sí por los siguientes tres ejemplos:

Reflexiva y transitiva : La relación de ≤ N . O de cualquier orden previo ; 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 , definida como aRb ↔ “ uno - b es divisible por lo menos uno de los 2 o 3. “ O cualquier relación de dependencia .

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

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

[ editar ] Relaciones euclidiana

Euclides ‘s The Elements incluye lo siguiente “una noción común”:

Las cosas que igual lo mismo también son iguales entre sí.

Hoy en día, la propiedad descrita por una noción común se llama euclidiana (en sustitución de “igualdad” por “en relación con”). El teorema siguiente conecta las relaciones euclidiana y las relaciones de equivalencia:

Teorema . Si una relación es euclídea y reflexiva , también es simétrica y transitiva.

Prueba :

( arco ∧ bRc ) → aRb [ a / c ] = ( aRa ∧ bRa ) → aRb [ reflexiva ; borrar T ∧] = bRa → aRb . Por lo tanto R es simétrica . ( arco ∧ bRc ) → aRb [ simetría ] = ( arco ∧ CRB ) → aRb . Por lo tanto R es transitiva .\square

Por lo tanto una relación de equivalencia es una relación que es euclídea y reflexiva . Los elementos no menciona ni simetría, ni reflexión, y Euclides probablemente hubiese considerado que la reflexividad de la igualdad demasiado obvio para merecer una mención explícita.

Equivalence relation. (2011, February 28). In Wikipedia, The Free Encyclopedia. Retrieved 22:50, May 14, 2011, from http://en.wikipedia.org/w/index.php?title=Equivalence_relation&oldid=416460297


Mis sitios nuevos:
Emprendedores
Politica de Privacidad