En matemáticas, una relación binaria idempotente es una relación binaria R en un conjunto X (un subconjunto de producto cartesiano X × X ) para el que la composición de relaciones R ∘ R es el mismo que R . [1] [2] Esta noción generaliza la de función idempotente a las relaciones.
Definición
Como una taquigrafía, la notación 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 define mediante el establecimiento de XSZ ser cierto para un par de elementos x y z en X siempre existe y en X con xRy y yRz tanto cierto. R es idempotente si R = S .
De manera equivalente, la relación R es idempotente si y solo si las siguientes dos propiedades son verdaderas:
- 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 cierto.
- R ∘ R ⊇ R . De manera equivalente, en términos de elementos individuales, para cada x y z para los que xRz es cierto, existe y con xRy y yRz tanto cierto. Algunos autores llaman un ejemplo R una relación densa . [3]
Debido a que la idempotencia incorpora tanto la transitividad como la segunda propiedad anterior, es una propiedad más fuerte que la transitividad.
Ejemplos de
Por ejemplo, la relación
Por el contrario, la misma relación de ordenamiento
Un producto externo de vectores lógicos forma una relación idempotente. Tal relación puede estar contenida en una relación más compleja, en cuyo caso se le llama concepto en ese contexto más amplio. La descripción de relaciones en términos de sus conceptos se denomina análisis de concepto formal .
Usos
Las relaciones idempotentes se han utilizado como ejemplo para ilustrar la aplicación de la formalización mecanizada de las matemáticas utilizando el demostrador interactivo de teoremas Isabelle / HOL. Además de comprobar las propiedades matemáticas de las relaciones idempotentes finitas, se ha derivado en Isabelle / HOL un algoritmo para contar el número de relaciones idempotentes. [4] [5]
También se ha demostrado que las relaciones idempotentes definidas en espacios débilmente contables compactos satisfacen la "condición Γ": es decir, toda relación idempotente no trivial en dicho espacio contiene puntos para algunos . Esto se usa para mostrar que ciertos subespacios de un producto incontable de espacios, conocidos como productos de Mahavier, no pueden ser metrizables cuando se definen por una relación idempotente no trivial. [6]
Referencias
- ^ Florian Kammüller, JW Sanders (2004). Relación idempotente en Isabelle / HOL (PDF) (Informe técnico). TU Berlín. pag. 27. 2004-04. Archivado desde el original (PDF) el 12 de mayo de 2014 . Consultado el 10 de mayo de 2014 . Aquí: p.3
- ^ Florian Kammüller (2011). "Análisis mecánico de relaciones idempotentes finitas". Fundamenta Informaticae . 107 : 43–65. doi : 10.3233 / FI-2011-392 .
- ^ Gunter Schmidt (2011) Matemáticas relacionales , página 212, Cambridge University PressISBN 978-0-521-76268-7
- ^ Florian Kammüller (2006). "Número de relaciones idempotentes sobre n elementos etiquetados" . La Ecyclopedea en línea de secuencias enteras (A12137).
- ^ Florian Kammüller (2008). Contando Relaciones Idempotentes (PDF) (Informe técnico). TU Berlín. pag. 27. 2008-15.
- ^ Clontz, Steven; Varagona, Scott (2018). "Productos Mahavier, relaciones idempotentes y condición Γ". arXiv : 1805.06827 [ math.GN ].
Otras lecturas
- Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos y autómatas . Enciclopedia de Matemáticas y sus Aplicaciones. 129 . Cambridge: Cambridge University Press . pag. 330. ISBN 978-0-521-88831-8. Zbl 1187.94001 .