Relación de equivalencia parcial

Concepto matemático para comparar objetos.

En matemáticas , una relación de equivalencia parcial (a menudo abreviada como PER , en la literatura antigua también llamada relación de equivalencia restringida ^[1] ) es una relación binaria homogénea que es simétrica y transitiva . Si la relación también es reflexiva , entonces la relación es una relación de equivalencia .

Definición

Formalmente, una relación en un conjunto es un PER si se cumple para todo eso: ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle a,b,c\in X}$

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

Otra definición más intuitiva es que en un conjunto es un PER si hay algún subconjunto de tal que y es una relación de equivalencia en . Se considera que las dos definiciones son equivalentes si se toma . ^[2] ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle R\subseteq Y\times Y}$ ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle Y=\{x\in X\mid x\,R\,x\}}$

Propiedades y aplicaciones

Las siguientes propiedades son válidas para una relación de equivalencia parcial en un conjunto : ${\displaystyle R}$ ${\displaystyle X}$

• ${\displaystyle R}$es una relación de equivalencia en el subconjunto . ^{[nota 1]} ${\displaystyle Y=\{x\in X\mid x\,R\,x\}\subseteq X}$
• difuncional : la relación es el conjunto de dos funciones parciales y algún conjunto de indicadores ${\displaystyle \{(a,b)\mid fa=gb\}}$ ${\displaystyle f,g:X\rightharpoonup Y}$ ${\displaystyle Y}$
• Euclidiano derecho e izquierdo : Para , e implica y de manera similar para euclidiano izquierdo e implican ${\displaystyle a,b,c\in X}$ ${\displaystyle aRb}$ ${\displaystyle aRc}$ ${\displaystyle bRc}$ ${\displaystyle bRa}$ ${\displaystyle cRa}$ ${\displaystyle bRc}$
• cuasi reflexivo : si y , entonces y . ^{[3] [nota 2]} ${\displaystyle x,y\in X}$ ${\displaystyle xRy}$ ${\displaystyle xRx}$ ${\displaystyle yRy}$

Ninguna de estas propiedades es suficiente para implicar que la relación es un PER. ^{[nota 3]}

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 ^[4] ; en estos contextos, los PER se utilizan más comúnmente, particularmente 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. ^[5]

Ejemplos

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=\emptyset }$ ${\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 está definido en , está definido 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 existe tal aquello . De ello se deduce inmediatamente que el subconjunto más grande de on cual es una relación de equivalencia es precisamente el subconjunto on cual está definido. ${\displaystyle f}$ ${\displaystyle \approx }$ ${\displaystyle f(x)}$ ${\displaystyle x\not \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) . Para , definir significa: ${\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 . Por lo tanto, el PER captura tanto la idea de definición de 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 punto flotante IEEE

El estándar IEEE 754:2008 para números de punto flotante define una relación "EQ" para valores de punto flotante. Este predicado es simétrico y transitivo, pero no reflexivo debido a la presencia de valores de NaN que no son EQ en sí mismos. ^{[ cita necesaria ]}

Notas

1. Por construcción, es reflexivo y, por tanto, una relación de equivalencia . ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle Y}$
2. Esto se sigue ya que si , entonces por simetría, entonces y por transitividad. También es consecuencia de las propiedades euclidianas. ${\displaystyle xRy}$ ${\displaystyle yRx}$ ${\displaystyle xRx}$ ${\displaystyle yRy}$
3. Para la relación de equivalencia, considere el conjunto y la relación . es una relación de equivalencia en pero no una PER en ya que no es simétrica ( , pero no ) ni transitiva ( y , pero no ). Para el carácter euclidiano, xRy en números naturales, definido por 0 ≤ x ≤ y +1 ≤ 2, es euclidiano derecho, pero no es simétrico (ya que, por ejemplo, 2 R 1, pero no 1 R 2) ni transitivo (ya que, por ejemplo, 2 R 1 y 1 R 0, pero no 2 R 0). ${\displaystyle E=\{a,b,c,d\}}$ ${\displaystyle R=\{a,b,c\}^{2}\cup \{(d,a)\}}$ ${\displaystyle R}$ ${\displaystyle \{a,b,c\}}$ ${\displaystyle E}$ ${\displaystyle dRa}$ ${\displaystyle aRd}$ ${\displaystyle dRa}$ ${\displaystyle aRb}$ ${\displaystyle dRb}$

Referencias

1. Scott, Dana (septiembre de 1976). "Tipos de datos como celosías". Revista SIAM de Computación . 5 (3): 560. doi : 10.1137/0205037.
2. Mitchell, John C. (1996). Fundamentos de los lenguajes de programación . Cambridge, Massachusetts: MIT Press. págs. 364–365. ISBN 0585037892.
3. Enciclopedia Británica (EB); aunque la noción de cuasi-reflexividad de EB es la noción de Wikipedia de cuasi-reflexividad de izquierda, coinciden para las relaciones simétricas.
4. Salveson, A.; Smith, JM (1988). "La fuerza del tipo de subconjunto en la teoría de tipos de Martin-Lof". [1988] Actas. Tercer Simposio Anual de Información sobre Lógica en Informática . págs. 384–391. doi :10.1109/LICS.1988.5135. ISBN 0-8186-0853-6. S2CID  15822016.
5. J. Lambek (1996). "La mariposa y la serpiente". En Aldo Ursini; Paulo Agliano (eds.). Lógica y Álgebra . Prensa CRC. págs. 161–180. ISBN 978-0-8247-9606-8.