stringtranslate.com

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 × 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. Se denomina matriz de adyacencia en la terminología de grafos.

Relaciones homogéneas particulares

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

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 xX , xRx . Por ejemplo, ≥ es una relación reflexiva pero > no lo es.
Irreflexivo (o estricto )
para todo xX , no xRx . Por ejemplo, > es una relación irreflexiva, pero ≥ no lo es.
Coreflexivo
para todo x , yX , 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 , yX , si xRy entonces xRx .
Cuasi-reflexivo derecho
para todo x , yX , si xRy entonces yRy .
Cuasi-reflexivo
para todo x , yX , 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 , yX , 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 , yX , 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 , yX , 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 simétrica ni antisimétrica, y mucho menos asimétrica.

Transitivo
para todo x , y , zX , 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 , zX , si xRy y yRz entonces nunca xRz .
Cotransitivo
si el complemento de R es transitivo. Es decir, para todo x , y , zX , si xRz , entonces xRy o yRz . Esto se utiliza en pseudoórdenes en matemáticas constructivas.
Cuasitransitivo
para todo x , y , zX , si xRy y yRz pero ni yRx ni zRy , entonces xRz pero no zRx .
Transitividad de la incomparabilidad
para todo x , y , zX , 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 , yX tal que xRy , existe algún zX tal que xRz y zRy . Esto se utiliza en órdenes densos .
Conectado
para todo x , yX , si xy 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 , yX , 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 , yX , 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 , zX , 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 , zX , 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 xX , la clase de todo y tal que yRx es un conjunto. (Esto sólo tiene sentido si se permiten relaciones sobre clases propias).
Izquierda única
para todo x , zX y todo yY , si xRy y zRy entonces x = z .
Univalente
para todo xX y todo y , zY , si xRy y xRz entonces y = z . [14]
Total (también llamado total izquierdo)
Para todo xX existe un yY 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 yY , existe un xX 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 ) | xX } ∪ 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 ) | xX } 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 × 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]

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:

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

Generalizaciones

Referencias

  1. ^ 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.
  2. ^ ME Müller (2012). Descubrimiento del conocimiento relacional . Cambridge University Press. pág. 22. ISBN 978-0-521-19021-3.
  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.
  4. ^ 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.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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).
  8. ^ 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
  9. ^ Nievergelt, Yves (2002), Fundamentos de lógica y matemáticas: aplicaciones a la informática y la criptografía , Springer-Verlag, pág. 158.
  10. ^ 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".
  11. ^ Dado que ni 5 divide a 3, ni 3 divide a 5, ni 3=5.
  12. ^ "Condición de bien fundado". ProofWiki . Archivado desde el original el 20 de febrero de 2019 . Consultado el 20 de febrero de 2019 .
  13. ^ 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 .
  14. ^ Gunther Schmidt y Thomas Strohlein (2012)[1987] Relaciones y gráficos , pág. 54, en Google Books
  15. ^ Joseph G. Rosenstein, Ordenamientos lineales , Academic Press, 1982, ISBN 0-12-597680-1 , pág. 4 
  16. ^ 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.