Relación de equivalencia parcial - Partial equivalence relation

En matemáticas , una relación de equivalencia parcial (a menudo abreviada como PER , en la literatura más antigua también llamada relación de equivalencia restringida ) en un conjunto es una relación binaria que es simétrica y transitiva . En otras palabras, vale para todo eso: ${\ Displaystyle R}$${\ Displaystyle X}$${\ Displaystyle a, b, c \ en X}$

1. si , entonces (simetría)${\ Displaystyle aRb}$${\ displaystyle bRa}$
2. si y , entonces (transitividad)${\ Displaystyle aRb}$${\ displaystyle bRc}$${\ Displaystyle aRc}$

Si también es reflexivo , entonces es una relación de equivalencia . ${\ Displaystyle R}$${\ Displaystyle R}$

Propiedades y aplicaciones

Si una relación en un conjunto es un PER, entonces es una relación de equivalencia en el subconjunto . Sin embargo, dado un conjunto y un subconjunto , una relación de equivalencia en no necesita ser un PER en ; por ejemplo, considerando el conjunto , la relación sobre caracterizada por el conjunto es una relación de equivalencia en pero no una PER en ya que no es simétrica ni transitiva en . ${\ Displaystyle R}$${\ Displaystyle X}$${\ Displaystyle R}$${\ Displaystyle Y = \ {x \ in X \ mid x \, R \, x \} \ subseteq X}$${\ Displaystyle X}$${\ Displaystyle Y \ subseteq X}$${\ Displaystyle Y}$${\ Displaystyle X}$${\ Displaystyle E = \ {a, b, c, d \}}$${\ Displaystyle E}$${\ Displaystyle R = \ {a, b, c \} ^ {2} \ cup \ {(d, a) \}}$${\ Displaystyle \ {a, b, c \}}$${\ Displaystyle E}$${\ Displaystyle E}$

Toda relación de equivalencia parcial es una relación difuncional , pero lo contrario no se cumple.

Cada relación de equivalencia parcial es una relación euclidiana recta . Lo contrario no es válido: por ejemplo, xRy en números naturales, definido por 0 ≤ x ≤ y +1 ≤ 2, es euclidiana derecha, pero no simétrica (ya que, por ejemplo, 2 R 1, pero no 1 R 2) ni transitiva (desde por ejemplo, 2 R 1 y 1 R 0, pero no 2 R 0). De manera similar, cada relación de equivalencia parcial es una relación euclidiana izquierda, pero no al revés. Cada relación de equivalencia parcial es cuasi reflexiva , como consecuencia de ser euclidiana.

En entornos sin teoría de conjuntos

En la teoría de tipos , las matemáticas constructivas y sus aplicaciones a la informática , la construcción de análogos de subconjuntos suele ser problemática; en estos contextos, los PER se utilizan con más frecuencia, en particular para definir setoides , a veces llamados setoides parciales. Formar un setoide parcial a partir de un tipo y un PER es análogo a formar subconjuntos y cocientes en las matemáticas clásicas de la teoría de conjuntos.

La noción algebraica de congruencia también puede generalizarse a equivalencias parciales, dando como resultado la noción de subcongruencia , es decir, una relación homomórfica que es simétrica y transitiva, pero no necesariamente reflexiva.

Ejemplos de

Un ejemplo simple de un PER que no es una relación de equivalencia es la relación vacía , si no está vacía. ${\ Displaystyle R = \ conjunto vacío}$${\ Displaystyle X}$

Núcleos de funciones parciales

Si es una función parcial en un conjunto , entonces la relación definida por ${\ Displaystyle f}$${\ Displaystyle A}$${\ Displaystyle \ approx}$

${\ Displaystyle x \ approx y}$si se define en , se define en y${\ Displaystyle f}$${\ Displaystyle x}$${\ Displaystyle f}$${\ Displaystyle y}$${\ Displaystyle f (x) = f (y)}$

es una relación de equivalencia parcial, ya que es claramente simétrica y transitiva.

Si no está definido en algunos elementos, entonces no es una relación de equivalencia. No es reflexivo ya que si no está definido entonces - de hecho, para tal no hay tal que . De ello se deduce inmediatamente que el subconjunto más grande de sobre el que existe una relación de equivalencia es precisamente el subconjunto sobre el que se define. ${\ Displaystyle f}$${\ Displaystyle \ approx}$${\ Displaystyle f (x)}$${\ Displaystyle x \ no \ approx x}$${\ Displaystyle x}$${\ Displaystyle y \ in A}$${\ Displaystyle x \ approx y}$${\ Displaystyle A}$${\ Displaystyle \ approx}$${\ Displaystyle f}$

Funciones que respetan las relaciones de equivalencia

Sean X e Y conjuntos equipados con relaciones de equivalencia (o PER) . Por , defina para significar: ${\ Displaystyle \ approx _ {X}, \ approx _ {Y}}$${\ Displaystyle f, g: X \ to Y}$${\ Displaystyle f \ approx g}$

${\ Displaystyle \ forall x_ {0} \; x_ {1}, \ quad x_ {0} \ approx _ {X} x_ {1} \ Rightarrow f (x_ {0}) \ approx _ {Y} g (x_ {1})}$

entonces significa que f induce una función bien definida de los cocientes . Así, el PER captura tanto la idea de definición en los cocientes como de dos funciones que inducen la misma función en el cociente. ${\ Displaystyle f \ approx f}$${\ Displaystyle X / {\ approx _ {X}} \; \ to \; Y / {\ approx _ {Y}}}$${\ Displaystyle \ approx}$

Igualdad de valores de coma flotante IEEE

El estándar de coma flotante IEEE 754: 2008 define una relación "EQ" para valores de coma flotante. Este predicado es simétrico y transitivo, pero no reflexivo debido a la presencia de valores NaN que no son EQ para sí mismos.

Notas

Referencias

• Mitchell, John C. Fundamentos de los lenguajes de programación. Prensa del MIT, 1996.
• DS Scott. "Tipos de datos como celosías". Diario SIAM. Computación. , 3: 523-587, 1976.