Relación idempotente

En matemáticas, una relación binaria idempotente es una relación binaria R en un conjunto X (un subconjunto del producto cartesiano X  × X ) para la cual la composición de relaciones R ∘ R es la misma que R . ^{[ 1 ] [ 2 ]} Esta noción generaliza la de una función idempotente a las relaciones.   

Como notación abreviada, xRy indica que un par ( x , y ) pertenece a una relación R. La composición de relaciones R  ∘ R es la relación S definida al establecer xSz como verdadero para un par de elementos x y z en X siempre que exista y en X tal que xRy e yRz sean ambos verdaderos. R es idempotente si R = S.   

De forma equivalente, la relación R es idempotente si y solo si se cumplen las dos propiedades siguientes:

• R es una relación transitiva , lo que significa que R  ∘ R ⊆ R. De manera equivalente, en términos de elementos individuales, para cada x , y y z para los cuales xRy e yRz son ambos verdaderos, xRz también es verdadero.   
• R  ∘ R ⊇ R . De forma equivalente, en términos de elementos individuales, para cada x y z para los cuales xRz es verdadero, existe y tal que xRy e yRz son ambos verdaderos. Algunos autores denominan a dicha R una relación densa . ^{[ 3 ]}   

Debido a que la idempotencia incorpora tanto la transitividad como la segunda propiedad mencionada anteriormente, es una propiedad más fuerte que la transitividad.

Por ejemplo, la relación  < en los números racionales es idempotente. La relación de orden estricto es transitiva, y siempre que dos números racionales x y z cumplen la relación x  < z, necesariamente existe otro número racional y entre ellos (por ejemplo, su promedio) con x < y e y < z .     

Por el contrario, la misma relación de orden  <  sobre los enteros no es idempotente. Sigue siendo transitiva, pero no cumple la segunda propiedad de una relación idempotente. Por ejemplo, 1  <  2, pero no existe ningún otro entero y entre 1 y 2.

El producto exterior de vectores lógicos forma una relación idempotente. Dicha relación puede estar contenida en una relación más compleja, en cuyo caso se denomina concepto dentro de ese contexto más amplio. La descripción de las relaciones en términos de sus conceptos se denomina análisis formal de conceptos .

Las relaciones idempotentes se han utilizado como ejemplo para ilustrar la aplicación de la formalización mecanizada de las matemáticas mediante el demostrador de teoremas interactivo Isabelle/HOL. Además de comprobar las propiedades matemáticas de las relaciones idempotentes finitas, se ha derivado un algoritmo para contar el número de relaciones idempotentes en Isabelle/HOL. ^{[ 4 ] [ 5 ]}

También se ha demostrado que las relaciones idempotentes definidas en espacios débilmente numerablemente compactos satisfacen la "condición Γ": es decir, toda relación idempotente no trivial en dicho espacio contiene puntos${\displaystyle \langle x,x\rangle ,\langle x,y\rangle ,\langle y,y\rangle }$para algunos${\displaystyle x,y}$Esto se utiliza para demostrar que ciertos subespacios de un producto no numerable de espacios, conocidos como productos de Mahavier, no pueden ser metrizables cuando se definen mediante una relación idempotente no trivial. ^{[ 6 ]}

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos y autómatas . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  129. Cambridge: Cambridge University Press . p.  330. ISBN 978-0-521-88831-8. Zbl 1187.94001 .