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 una PER si se cumple para todo lo que: ${\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 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] ${\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 se cumplen 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 indicador ${\displaystyle \{(a,b)\mid fa=gb\}}$ ${\displaystyle f,g:X\rightharpoonup Y}$ ${\displaystyle Y}$
• Euclidiana derecha e izquierda : Para , e implica y de manera similar para la euclidiana izquierda e implica ${\displaystyle a,b,c\in X}$ ${\displaystyle aRb}$ ${\displaystyle aRc}$ ${\displaystyle bRc}$ ${\displaystyle bRa}$ ${\displaystyle cRa}$ ${\displaystyle bRc}$
• cuasi-reflexiva : 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 una PER. ^{[nota 3]}

En entornos que no son de 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] ; 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]

Ejemplos

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=\emptyset }$ ${\displaystyle X}$

Núcleos de funciones parciales

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}$

Funciones que respetan relaciones de equivalencia

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 }$

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

Notas

1. Por construcción, es reflexivo en y por lo tanto una relación de equivalencia en . ${\displaystyle R}$ ${\displaystyle Y}$ ${\displaystyle Y}$
2. Esto se deduce porque si , entonces por simetría, entonces y por transitividad. También es una 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 la euclideanidad, xRy en números naturales, definidos por 0 ≤ x ≤ y +1 ≤ 2, es euclidiana recta, pero no simétrica (ya que p. ej. 2 R 1, pero no 1 R 2) ni transitiva (ya que p. ej. 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 retículos". 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, Mass.: MIT Press. pp. 364–365. ISBN 0585037892.
3. Enciclopedia Británica (EB); aunque la noción de cuasireflexividad de EB es la noción de cuasireflexividad izquierda de Wikipedia, 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 Ciencias de la Computación . págs. 384–391. doi :10.1109/LICS.1988.5135. ISBN 0-8186-0853-6.S2CID15822016  .​
5. J. Lambek (1996). "La mariposa y la serpiente". En Aldo Ursini; Paulo Agliano (eds.). Lógica y álgebra . CRC Press. págs. 161–180. ISBN 978-0-8247-9606-8.
6. Goldberg, David (1991). "Lo que todo informático debería saber sobre aritmética de punto flotante". ACM Computing Surveys . 23 (1): 5–48. doi :10.1145/103162.103163.Vea la página 33.