Relación homogénea

En matemáticas , una relación homogénea (también llamada endorrelación ) sobre un conjunto X es una relación binaria entre X y sí mismo, es decir , es un subconjunto del producto cartesiano $X \times X.$ ^[1]^[2]^[3] Esto se expresa comúnmente como "una relación sobre X " ^[4] o "una relación (binaria) sobre X ". ^[5]^[6] Un ejemplo de una relación homogénea es la relación de parentesco , donde la relación es entre personas.

Los tipos comunes de endorelaciones incluyen órdenes , grafos y equivalencias . Los estudios especializados de la teoría de órdenes y la teoría de grafos han desarrollado la comprensión de las endorelaciones. Para la descripción se utiliza la terminología particular de la teoría de grafos, y se supone que un grafo ordinario (no dirigido) corresponde a una relación simétrica , y una endorelación general corresponde a un grafo dirigido . Una endorelación R corresponde a una matriz lógica de 0 y 1, donde la expresión xRy corresponde a una arista entre x e y en el grafo, y a un 1 en la matriz cuadrada de R. En la terminología de grafos, se denomina matriz de adyacencia .

Relaciones homogéneas particulares

Algunas relaciones homogéneas particulares sobre un conjunto X (con elementos arbitrarios $x 1$ , $x 2$ ) son:

Relación vacía
$E = \emptyset$ ;
es decir, $x 1 Ej 2$ nunca se cumple;
Relación universal
$U = X \times X$ ;
es decir, $x 1 Ux 2$ se cumple siempre;
Relación de identidad (ver también Función de identidad )
$I = {(x, x) | x \in X$ };
es decir, $x 1 Ix 2$ se cumple si y sólo si $x 1 = x 2$ .

Ejemplo

Quince grandes placas tectónicas de la corteza terrestre están en contacto entre sí en una relación homogénea. La relación se puede expresar como una matriz lógica en la que 1 indica contacto y 0 no. Este ejemplo expresa una relación simétrica.

Propiedades

Algunas propiedades importantes que puede tener una relación homogénea $R$ sobre un conjunto $X$ son:

Reflexivo: para todo $x \in X$ , $xRx$ . Por ejemplo, ≥ es una relación reflexiva pero > no lo es.
Irreflexivo (o estricto ): para todo $x \in X$ , no $xRx$ . Por ejemplo, > es una relación irreflexiva, pero ≥ no lo es.
Coreflexivo: para todo $x, y \in X$ , si $xRy$ entonces $x = y$ . ^[7] Por ejemplo, la relación sobre los enteros en la que cada número impar está relacionado consigo mismo es una relación correflexiva. La relación de igualdad es el único ejemplo de una relación tanto reflexiva como correflexiva, y cualquier relación correflexiva es un subconjunto de la relación de identidad.
Izquierda cuasi-reflexiva: para todo $x, y \in X$ , si $xRy$ entonces $xRx$ .
Cuasi-reflexivo derecho: para todo $x, y \in X$ , si $xRy$ entonces $yRy$ .
Cuasi-reflexivo: para todo $x, y \in X$ , si $xRy$ entonces $xRx$ e $yRy$ . Una relación es cuasi-reflexiva si, y solo si, es cuasi-reflexiva tanto por izquierda como por derecha.

Las 6 alternativas anteriores están lejos de ser exhaustivas; por ejemplo, la relación binaria $xRy$ definida por $y = x 2$ no es ni irreflexiva, ni correflexiva, ni reflexiva, ya que contiene el par $(0, 0)$ y $(2, 4)$ , pero no $(2, 2)$ , respectivamente. Los dos últimos hechos también descartan (cualquier tipo de) cuasireflexividad.

Simétrico: para todo $x, y \in X$ , si $xRy$ entonces $yRx$ . Por ejemplo, "es pariente consanguíneo de" es una relación simétrica, porque $x$ es pariente consanguíneo de $y$ si y solo si $y$ es pariente consanguíneo de $x$ .
Antisimétrico: para todo $x, y \in X$ , si $xRy$ e $yRx$ entonces $x = y$ . Por ejemplo, ≥ es una relación antisimétrica; también lo es >, pero de manera vacía (la condición en la definición siempre es falsa). ^[8]
Asimétrico: para todo $x, y \in X$ , si $xRy$ entonces no $yRx$ . Una relación es asimétrica si y solo si es antisimétrica e irreflexiva. ^[9] Por ejemplo, > es una relación asimétrica, pero ≥ no lo es.

De nuevo, las tres alternativas anteriores están lejos de ser exhaustivas; como ejemplo sobre los números naturales, la relación $xRy$ definida por $x > 2$ no es ni simétrica ni antisimétrica, y mucho menos asimétrica.

Transitivo: para todo $x, y, z \in X$ , si $xRy$ y $yRz$ entonces $xRz$ . Una relación transitiva es irreflexiva si y solo si es asimétrica. ^[10] Por ejemplo, "es ancestro de" es una relación transitiva, mientras que "es padre de" no lo es.
Antitransitivo: para todo $x, y, z \in X$ , si $xRy$ y $yRz$ entonces nunca $xRz$ .
Cotransitivo: si el complemento de R es transitivo. Es decir, para todo $x, y, z \in X$ , si $xRz$ , entonces $xRy$ o $yRz$ . Esto se utiliza en pseudoórdenes en matemáticas constructivas.
Cuasitransitivo: para todo $x, y, z \in X$ , si $xRy$ y $yRz$ pero ni $yRx$ ni $zRy$ , entonces $xRz$ pero no $zRx$ .
Transitividad de la incomparabilidad: para todo $x, y, z \in X$ , si $x$ e $y$ son incomparables con respecto a $R$ y si lo mismo es cierto para $y$ y $z$ , entonces $x$ y $z$ también son incomparables con respecto a $R$ . Esto se utiliza en ordenamientos débiles .

Nuevamente, las 5 alternativas anteriores no son exhaustivas. Por ejemplo, la relación $xRy$ si ( $y = 0$ o $y = x +1$ ) no satisface ninguna de estas propiedades. Por otro lado, la relación vacía las satisface trivialmente todas.

Denso: para todo $x, y \in X$ tal que $xRy$ , existe algún $z \in X$ tal que $xRz$ y $zRy$ . Esto se utiliza en órdenes densos .
Conectado: para todo $x, y \in X$ , si $x \neq y$ entonces $xRy$ o $yRx$ . Esta propiedad a veces se denomina ^{[ cita requerida ]} "total", que es distinta de las definiciones de "total izquierda/derecha" que se dan a continuación.
Fuertemente conectado: para todo $x, y \in X$ , $xRy$ o $yRx$ . Esta propiedad también se denomina a veces ^{[ cita requerida ]} "total", lo que es distinto de las definiciones de "total izquierda/derecha" que se dan a continuación.
Tricotómico: Para todo $x, y \in X$ , se cumple exactamente uno de los valores $xRy$ , $yRx$ o $x = y$ . Por ejemplo, > es una relación tricotómica sobre los números reales, mientras que la relación "divide" sobre los números naturales no lo es. ^[11]
Euclidiana derecha (o simplemente euclidiana ): para todo $x, y, z \in X$ , si $xRy$ y $xRz$ entonces $yRz$ . Por ejemplo, = es una relación euclidiana porque si $x = y$ y $x = z$ entonces $y = z$ .
Euclidiana izquierda: para todo $x, y, z \in X$ , si $yRx$ y $zRx$ entonces $yRz$ .
Bien fundado: todo subconjunto no vacío $S$ de $X$ contiene un elemento mínimo con respecto a $R$ . La fundamentación implica la condición de cadena descendente (es decir, no puede existir ninguna cadena infinita ... $x n R ... Rx 3 Rx 2 Rx 1$ ). Si se supone el axioma de elección dependiente , ambas condiciones son equivalentes. ^[12]^[13]

Además, todas las propiedades de las relaciones binarias en general también pueden aplicarse a las relaciones homogéneas:

Similar a un conjunto: para todo $x \in X$ , la clase de todo $y$ tal que $yRx$ es un conjunto. (Esto tiene sentido sólo si se permiten relaciones sobre clases propias).
Izquierda única: para todo $x, z \in X$ y todo $y \in Y$ , si $xRy$ y $zRy$ entonces $x = z$ .
Univalente: para todo $x \in X$ y todo $y, z \in Y$ , si $xRy$ y $xRz$ entonces $y = z$ . ^[14]
Total (también llamado total izquierdo): Para todo $x \in X$ existe un $y \in Y$ tal que $xRy$ . Esta propiedad es diferente de la definición de conexo (también llamado total por algunos autores). ^{[ cita requerida ]}
Sobreyectiva (también llamada total derecha): para todo $y \in Y$ , existe un $x \in X$ tal que xRy .

Un preorden es una relación que es reflexiva y transitiva. Un preorden total , también llamado preorden lineal u orden débil , es una relación que es reflexiva, transitiva y conexa.

Un orden parcial , también llamado orden , ^{[ cita requerida ]} es una relación que es reflexiva, antisimétrica y transitiva. Un orden parcial estricto , también llamado orden estricto , ^{[ cita requerida ]} es una relación que es irreflexiva, antisimétrica y transitiva. Un orden total , también llamado orden lineal , orden simple o cadena , es una relación que es reflexiva, antisimétrica, transitiva y conexa. ^[15] Un orden total estricto , también llamado orden lineal estricto , orden simple estricto o cadena estricta , es una relación que es irreflexiva, antisimétrica, transitiva y conexa.

Una relación de equivalencia parcial es una relación que es simétrica y transitiva. Una relación de equivalencia es una relación que es reflexiva, simétrica y transitiva. También es una relación que es simétrica, transitiva y total, ya que estas propiedades implican reflexividad.

Operaciones

Si R es una relación homogénea sobre un conjunto X entonces cada una de las siguientes es una relación homogénea sobre X :

Cierre reflexivo , R ⁼: Definida como $R = = {(x, x) | x \in X} \cup R$ o la relación reflexiva más pequeña sobre X que contiene a R . Se puede demostrar que es igual a la intersección de todas las relaciones reflexivas que contienen a R .
Reducción reflexiva , R ^≠: Se define como $R ≠ = R \ {( x , x ) | x ∈ X$ } o la mayor relación irreflexiva sobre X contenida en R .
Cierre transitivo , R ⁺: Se define como la relación transitiva más pequeña sobre X que contiene a R. Se puede observar que es igual a la intersección de todas las relaciones transitivas que contienen a R.
Cierre transitivo reflexivo , R *: Definido como $R * = (R +) =$ , el preorden más pequeño que contiene R .
Cierre simétrico transitivo reflexivo , R ^≡: Se define como la relación de equivalencia más pequeña sobre X que contiene R.

Todas las operaciones definidas en Relación binaria § Operaciones también se aplican a las relaciones homogéneas.

Enumeración

El conjunto de todas las relaciones homogéneas sobre un conjunto X es el conjunto $2$ $X$ $\times$ $X$ , que es un álgebra de Boole aumentada con la involución de la aplicación de una relación a su relación inversa . Considerando la composición de relaciones como una operación binaria sobre , forma un monoide con involución donde el elemento identidad es la relación identidad. ^[16] ${\mathcal {B}}(X)$ ${\mathcal {B}}(X)$

El número de relaciones homogéneas distintas en un conjunto de n elementos es $2 n 2$ (secuencia A002416 en la OEIS ):

Téngase en cuenta que S ( n , k ) se refiere a números de Stirling del segundo tipo .

Notas:

El número de relaciones irreflexivas es el mismo que el de relaciones reflexivas.
El número de órdenes parciales estrictos (relaciones transitivas irreflexivas) es el mismo que el de órdenes parciales.
El número de órdenes débiles estrictas es el mismo que el de pedidos anticipados totales.
Los pedidos totales son los pedidos parciales que también son prepedidos totales. El número de prepedidos que no son ni un pedido parcial ni un prepedido total es, por tanto, el número de prepedidos, menos el número de pedidos parciales, menos el número de prepedidos totales, más el número de pedidos totales: 0, 0, 0, 3 y 85, respectivamente.
El número de relaciones de equivalencia es el número de particiones , que es el número de Bell .

Las relaciones homogéneas se pueden agrupar en pares (relación, complemento ), excepto que para $n = 0$ la relación es su propio complemento. Las no simétricas se pueden agrupar en cuartetos (relación, complemento, inversa, complemento inverso).

Ejemplos

Relaciones de órdenes , incluidas las órdenes estrictas :
- Más que
- Mayor o igual a
- Menos que
- Menor o igual a
- Divide (uniformemente)
- Subconjunto de
Relaciones de equivalencia :
- Igualdad
- Paralelo con (para espacios afines )
- Equinumerosidad o "está en biyección con"
- Isomorfo
- Segmentos de línea equipolentes
Relación de tolerancia , una relación reflexiva y simétrica:
- Relación de dependencia , una relación de tolerancia finita
- Relación de independencia , el complemento de alguna relación de dependencia
Relaciones de parentesco

Generalizaciones

Una relación binaria en general no necesita ser homogénea, se define como un subconjunto R ⊆ X × Y para conjuntos arbitrarios X e Y.
Una relación finitaria es un subconjunto R ⊆ X ₁ × ... × X _n para algún número natural n y conjuntos arbitrarios X ₁ , ..., X _n , también se denomina relación n -aria.

Referencias

^ Michael Winter (2007). Categorías de Goguen: un enfoque categórico de las relaciones L-difusas . Springer. pp. x–xi. ISBN 978-1-4020-6164-6.
^ ME Müller (2012). Descubrimiento del conocimiento relacional . Cambridge University Press. pág. 22. ISBN 978-0-521-19021-3.
^ Peter J. Pahl; Rudolf Damrath (2001). Fundamentos matemáticos de la ingeniería computacional: un manual . Springer Science & Business Media. pág. 496. ISBN 978-3-540-67995-0.
^ Mordeson, John N.; Nair, Premchand S. (8 de noviembre de 2012). Matemáticas difusas: una introducción para ingenieros y científicos. Physica. p. 2. ISBN 978-3-7908-1808-6.
^ Tanaev, V.; Gordon, W.; Shafransky, Yakov M. (6 de diciembre de 2012). Teoría de la programación. Sistemas de una sola etapa. Springer Science & Business Media. pág. 41. ISBN 978-94-011-1190-4.
^ Meyer, Bertrand (29 de junio de 2009). Touch of Class: Aprendiendo a programar bien con objetos y contratos. Springer Science & Business Media. pág. 509. ISBN 978-3-540-92145-5.
^ Fonseca de Oliveira, JN, y Pereira Cunha Rodrigues, CDJ (2004). Relaciones de transposición: de funciones Maybe a tablas hash. En Matemáticas de construcción de programas (p. 337).
^ Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006), Una transición a las matemáticas avanzadas (6.ª ed.), Brooks/Cole, pág. 160, ISBN 0-534-39900-2
^ Nievergelt, Yves (2002), Fundamentos de lógica y matemáticas: aplicaciones a la informática y la criptografía , Springer-Verlag, pág. 158.
^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Cierres transitivos de relaciones binarias I (PDF) . Praga: Facultad de Matemáticas – Física de la Universidad Charles. p. 1. Archivado desde el original (PDF) el 2 de noviembre de 2013.Lema 1.1 (iv). Esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
^ Dado que ni 5 divide a 3, ni 3 divide a 5, ni 3=5.
^ "Condición de bien fundado". ProofWiki . Archivado desde el original el 20 de febrero de 2019 . Consultado el 20 de febrero de 2019 .
^ Fraisse, R. (15 de diciembre de 2000). Theory of Relations, Volumen 145 - 1.ª edición (1.ª ed.). Elsevier. pág. 46. ISBN 9780444505422. Recuperado el 20 de febrero de 2019 .
^ Gunther Schmidt y Thomas Strohlein (2012)[1987] Relaciones y gráficos , pág. 54, en Google Books
^ Joseph G. Rosenstein, Ordenamientos lineales , Academic Press, 1982, ISBN 0-12-597680-1 , pág. 4
^ Schmidt, Gunther; Ströhlein, Thomas (1993). "Relaciones homogéneas". Relaciones y gráficos: matemáticas discretas para científicos informáticos . Berlín, Heidelberg: Springer. pág. 14. doi :10.1007/978-3-642-77968-8_2. ISBN 978-3-642-77968-8.