Relación de equivalencia parcial

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 .

Formalmente, una relación en un conjunto es una PER si se cumple para todo lo que: ${\estilo de visualización R}$${\estilo de visualización X}$${\displaystyle a,b,c\en X}$

1. Si , entonces (simetría)${\estilo de visualización aRb}$${\estilo de visualización bRa}$
2. si y , entonces (transitividad)${\estilo de visualización aRb}$${\estilo de visualización bRc}$${\estilo de visualización aRc}$

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

Las siguientes propiedades se cumplen para una relación de equivalencia parcial en un conjunto : ${\estilo de visualización R}$${\estilo de visualización X}$

• ${\estilo de visualización R}$es una relación de equivalencia en el subconjunto . ^{[nota 1]}${\displaystyle Y=\{x\en X\mid x\,R\,x\}\subseteq X}$
• difuncional : la relación es el conjunto de dos funciones parciales y algún conjunto indicador${\displaystyle \{(a,b)\mid fa=gb\}}$ ${\displaystyle f,g:X\rightharpoonup Y}$${\estilo de visualización Y}$
• Euclidiana derecha e izquierda : Para , e implica y de manera similar para la euclidiana izquierda e implica${\displaystyle a,b,c\en X}$${\estilo de visualización aRb}$${\estilo de visualización aRc}$${\estilo de visualización bRc}$${\estilo de visualización bRa}$${\estilo de visualización cRa}$${\estilo de visualización bRc}$
• cuasi-reflexiva : Si y , entonces y . ^{[3] [nota 2]}${\displaystyle x,y\en X}$${\estilo de visualización xRy}$${\estilo de visualización xRx}$${\estilo de visualización yRy}$

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

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] ; por lo tanto, 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 teoría de conjuntos.

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

Un ejemplo simple de una 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}$${\estilo de visualización X}$

Si es una función parcial sobre 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 reflexiva ya que si no está definido entonces —de hecho, para tal no existe tal que . Se sigue inmediatamente que el subconjunto más grande de en el cual es una relación de equivalencia es precisamente el subconjunto en el 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}$

Sean X e Y conjuntos dotados de relaciones de equivalencia (o PER) . Para , definamos que 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, la 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 }$

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 es reflexivo debido a la presencia de valores NaN que no son EQ entre sí. ^[6]