Relación homogénea

En matemáticas , una relación homogénea (también llamada endorelació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 en X " ^[4] o "una relación (binaria) sobre X ". ^[5]^[6] Un ejemplo de relación homogénea es la relación de parentesco , donde la relación es entre personas.

Los tipos comunes de endorelaciones incluyen órdenes , gráficas y equivalencias . Los estudios especializados de teoría del orden y teoría de grafos han desarrollado la comprensión de las endorrelaciones. Para la descripción se utiliza terminología particular de la teoría de grafos, presumiéndose que un grafo ordinario (no dirigido) corresponde a una relación simétrica y una endorelación general correspondiente 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 xey en el gráfico, y a un 1 en la matriz cuadrada de R. Se llama matriz de adyacencia en terminología gráfica.

Relaciones particularmente homogéneas

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

relación vacía
$mi = \emptyset$ ;
es decir, $x 1 Ex 2$ nunca se cumple;
relación universal
$U = X \times X$ ;
es decir, $x 1 Ux 2$ siempre se cumple;
Relación de identidad (ver también Función de identidad )
$yo = {(x, x) | x\inX}$ ; $$
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 hay contacto. 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 números 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 casi reflexiva: para todo $x, y \in X$ , si $xRy$ entonces $xRx$ .
Derecha casi reflexiva: 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 sólo si, es cuasi-reflexiva tanto hacia la izquierda como hacia la 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 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) cuasi-reflexividad.

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 sólo 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 forma vacía (la condición en la definición es siempre falsa). ^[8]
Asimétrico: para todo $x, y \in X$ , si $xRy$ entonces no $yRx$ . Una relación es asimétrica si y sólo si es a la vez antisimétrica e irreflexiva. ^[9] Por ejemplo, > es una relación asimétrica, pero ≥ no lo es.

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

Transitivo: para todo $x, y, z \in X$ , si $xRy$ e $yRz$ entonces $xRz$ . Una relación transitiva es irreflexiva si y sólo si es asimétrica. ^[10] Por ejemplo, "es antepasado de" es una relación transitiva, mientras que "es padre de" no lo es.
Antitransitivo: para todo $x, y, z \in X$ , si $xRy$ e $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$ e $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 ocurre con $y$ y $z$ , entonces $x$ y $z$ también son incomparables con respecto a $R.$ Esto se utiliza en ordenamientos débiles .

Nuevamente, las cinco 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 los satisface trivialmente a todos.

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 densas .
Conectado: para todo $x, y \in X$ , si $x \neq y$ entonces $xRy$ o $yRx$ . Esta propiedad a veces ^{[ cita necesaria ]} se denomina "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 llama a veces ^{[ cita necesaria ]} "total", que es distinta de las definiciones de "total izquierdo/derecho" que se dan a continuación.
tricotómico: para todo $x, y \in X$ , se cumple exactamente uno de $xRy$ , $yRx$ o $x = y$ . Por ejemplo, > es una relación tricotómica en los números reales, mientras que la relación "divide" entre los números naturales no lo es. ^[11]
Euclidiano derecho (o simplemente euclidiano ): 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: cada subconjunto no vacío $S$ de $X$ contiene un elemento mínimo con respecto a $R$ . El fundamento 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 relaciones homogéneas:

en forma de conjunto: para todo $x \in X$ , la clase de todo $y$ tal que $yRx$ es un conjunto. (Esto sólo tiene sentido si se permiten relaciones entre clases adecuadas).
Único a la izquierda: 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 necesaria ]}
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 reflexiva y transitiva. Un preorden total , también llamado preorden lineal u orden débil , es una relación reflexiva, transitiva y conexa.

Un orden parcial , también llamado orden , ^{[ cita necesaria ]} es una relación reflexiva, antisimétrica y transitiva. Un orden parcial estricto , también llamado orden estricto , ^{[ cita necesaria ]} es una relación irreflexiva, antisimétrica y transitiva. Un orden total , también llamado orden lineal , orden simple o en cadena , es una relación 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 irreflexiva, antisimétrica, transitiva y conexa.

Una relación de equivalencia parcial es una relación simétrica y transitiva. Una relación de equivalencia es una relación reflexiva, simétrica y transitiva. También es una relación 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 ⁼: Definido como $R = = {(x, x) | x \in X} \cup R$ o la relación reflexiva más pequeña sobre X que contiene R . Se puede demostrar que esto es igual a la intersección de todas las relaciones reflexivas que contienen R .
Reducción reflexiva , R ^≠: Definido como $R ≠ = R \ {( x , x ) | x ∈ X$ } o la relación irreflexiva más grande sobre X contenida en R .
Cierre transitivo , R ⁺: Definida como la relación transitiva más pequeña sobre X que contiene R. Se puede ver que esto es igual a la intersección de todas las relaciones transitivas que contienen R.
Cierre transitivo reflexivo , R *: Definido como $R * = (R +) =$ , el pedido anticipado más pequeño que contiene R .
Cierre simétrico transitivo reflexivo , R ^≡: Definida 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 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 booleana aumentada con la involución del mapeo de una relación con su relación inversa . Considerando la composición de relaciones como una operación binaria en , forma un monoide con involución donde el elemento de identidad es la relación de identidad. ^[dieciséis] ${\mathcal {B}}(X)$ ${\mathcal {B}}(X)$

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

Tenga en cuenta que S ( n , k ) se refiere a los 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 pedidos débiles estrictos es el mismo que el total de pedidos anticipados.
Los pedidos totales son los pedidos parciales que también son pedidos anticipados totales. El número de pedidos anticipados que no son ni parciales ni totales es, por tanto, el número de pedidos anticipados, menos el número de pedidos parciales, menos el número de pedidos anticipados 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. Los asimétricos se pueden agrupar en cuádruples (relación, complemento, inverso, complemento inverso).

Ejemplos

Relaciones de orden , incluidas órdenes estrictas :
- Mas grande que
- Mayor qué o igual a
- Menos que
- Menos que o igual a
- Divide (uniformemente)
- Subconjunto de
Relaciones de equivalencia :
- Igualdad
- Paralelo con (para espacios afines )
- Equinumerosidad o "está en biyección con"
- isomórfico
- 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 tiene por qué ser homogénea ; se define como un subconjunto R ⊆ X × Y para conjuntos arbitrarios X e Y.
Una relación finita es un subconjunto R ⊆ X ₁ × ... × X _n para algún número natural n y conjuntos arbitrarios X ₁ , ..., X _n , también se llama relación n -aria.

Referencias

^ Michael invierno (2007). Categorías de Goguen: un enfoque categórico de las relaciones L-difusas . Saltador. págs. ISBN 978-1-4020-6164-6.
^ ME Müller (2012). Descubrimiento de conocimiento relacional . Prensa de la Universidad de Cambridge. pag. 22.ISBN 978-0-521-19021-3.
^ Peter J. Pahl; Rudolf Damrath (2001). Fundamentos matemáticos de la ingeniería computacional: un manual . Medios de ciencia y negocios de Springer. pag. 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. Física. pag. 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. Medios de ciencia y negocios de Springer. pag. 41.ISBN 978-94-011-1190-4.
^ Meyer, Bertrand (29 de junio de 2009). Touch of Class: aprender a programar bien con objetos y contratos. Medios de ciencia y negocios de Springer. pag. 509.ISBN 978-3-540-92145-5.
^ Fonseca de Oliveira, JN y Pereira Cunha Rodrigues, CDJ (2004). Transposición de relaciones: de funciones Maybe a tablas hash. En Matemáticas de la construcción de programas (p. 337).
^ Smith, Douglas; Eggen, Mauricio; 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 la lógica y las matemáticas: aplicaciones a la informática y la criptografía , Springer-Verlag, p. 158.
^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Cierres Transitivos de Relaciones Binarias I (PDF) . Praga: Escuela de Matemáticas – Universidad Carolina de Física. pag. 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".
^ Ya que ni 5 divide a 3, ni 3 divide a 5, ni 3=5.
^ "Condición de fundamento". PruebaWiki . Archivado desde el original el 20 de febrero de 2019 . Consultado el 20 de febrero de 2019 .
^ Fraisse, R. (15 de diciembre de 2000). Teoría de las relaciones, volumen 145 - 1ª edición (1ª ed.). Elsevier. pag. 46.ISBN 9780444505422. Consultado el 20 de febrero de 2019 .
^ Gunther Schmidt y Thomas Strohlein (2012) [1987] Relaciones y gráficos , p. 54, en libros de Google
^ Joseph G. Rosenstein, Ordenamientos lineales , Academic Press, 1982, ISBN 0-12-597680-1 , p. 4
^ Schmidt, Gunther; Ströhlein, Thomas (1993). "Relaciones Homogéneas". Relaciones y gráficos: matemáticas discretas para informáticos . Berlín, Heidelberg: Springer. pag. 14. doi :10.1007/978-3-642-77968-8_2. ISBN 978-3-642-77968-8.