Relación homogénea

En matemáticas , una relación homogénea (también llamada endorrelación ) en 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 suele expresar como "una relación en 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 endorrelaciones incluyen órdenes , grafos y equivalencias . Los estudios especializados de la teoría del orden y la teoría de grafos han contribuido a la comprensión de las endorrelaciones. Para su descripción, se utiliza la terminología propia de la teoría de grafos, donde se presume que un grafo ordinario (no dirigido) corresponde a una relación simétrica y una endorrelación general corresponde a un grafo dirigido . Una endorrelación R corresponde a una matriz lógica de 0 y 1, donde la expresión xRy ( x está relacionado con y mediante R ) 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 .

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

Relación vacía

E = ∅ ;es decir, x ₁ Ex ₂ nunca se cumple;

Relación universal

U = X × X ;es decir, x ₁ Ux ₂ siempre se cumple;

Relación de identidad (véase también Función de identidad )

I = {( x , x ) | x ∈ X };es decir, x ₁ Ix ₂ se cumple si y solo si x ₁ = x ₂ .

Ejemplo

Dieciséis grandes placas tectónicas de la corteza terrestre se encuentran en contacto entre sí en una relación homogénea. Esta relación puede expresarse como una matriz lógica donde 1 (representado por " ") indica contacto y 0 (" ") ausencia de contacto. Este ejemplo expresa una relación simétrica.

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

Reflexivo

para todo x ∈ X , xRx . Por ejemplo, ≥ es una relación reflexiva pero > no lo es.

Irreflexivo (o estricto )

para todo x ∈ X , no xRx . Por ejemplo, > es una relación irreflexiva, pero ≥ no lo es.

Coreflexivo

Para todo x , y ∈ X , si xRy entonces x = y . ^{[ 7 ]} Por ejemplo, la relación sobre los enteros en la que cada número impar se relaciona consigo mismo es una relación coreflexiva. La relación de igualdad es el único ejemplo de una relación tanto reflexiva como coreflexiva, y cualquier relación coreflexiva es un subconjunto de la relación identidad.

Izquierda cuasirrefleja

para todo x , y ∈ X , si xRy entonces xRx .

cuasirreflexivo derecho

para todo x , y ∈ X , si xRy entonces yRy .

Cuasi-reflexivo

Para todo x , y ∈ X , si xRy, entonces xRx e yRy . Una relación es cuasirreflexiva si, y solo si, es cuasirreflexiva tanto por la izquierda como por la derecha.

Las seis alternativas anteriores distan mucho de ser exhaustivas; por ejemplo, la relación binaria xRy definida por y = x² no es ni irreflexiva, ni coreflexiva, ni reflexiva, puesto que contiene los pares (0, 0) ^y ( 2, 4) , pero no (2, 2) , respectivamente. Estos dos últimos hechos también descartan (cualquier tipo de) cuasirreflexividad.

Simétrico

para todo x , y ∈ 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 ∈ X , si xRy e yRx, entonces x = y . Por ejemplo, ≥ es una relación antisimétrica; también lo es >, pero trivialmente (la condición en la definición siempre es falsa). ^{[ 8 ]}

Asimétrico

Para todo x , y ∈ 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.

Nuevamente, 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 ∈ X , si xRy e yRz, entonces xRz . Una relación transitiva es irreflexiva si y solo si es asimétrica. ^{[ 10 ]} Por ejemplo, "es antecesor de" es una relación transitiva, mientras que "es padre de" no lo es.

Antitransitivo

para todo x , y , z ∈ X , si xRy e yRz entonces nunca xRz .

Cotransitivo

Si el complemento de R es transitivo. Es decir, para todo x , y , z ∈ X , si xRz , entonces xRy o yRz . Esto se utiliza en pseudoórdenes en matemáticas constructivas.

Cuasitransitivo

para todo x , y , z ∈ X , si xRy y yRz pero ni yRx ni zRy , entonces xRz pero no zRx .

Transitividad de la incomparabilidad

Para todo x , y , z ∈ 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 ordenaciones 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 las satisface todas trivialmente.

Denso

Para todo x , y ∈ X tal que xRy , existe algún z ∈ X tal que xRz y zRy . Esto se utiliza en órdenes densos .

Conectado

Para todo x , y ∈ X , si x ≠ y, entonces xRy o yRx . Esta propiedad a veces se denomina "total", lo cual es distinto de las definiciones de "total izquierdo/derecho" que se dan a continuación.

Fuertemente conectados

para todo x , y ∈ X , xRy o yRx . Esta propiedad también se denomina a veces "total", lo cual es distinto de las definiciones de "total izquierdo/derecho" que se dan a continuación.

Tricotómico

Para todo x , y ∈ X , se cumple exactamente una de las siguientes condiciones: xRy , yRx o x = y . Por ejemplo, > es una relación tricotómica en los números reales, mientras que la relación "divide" en los números naturales no lo es. ^{[ 11 ]}

Euclidiano recto (o simplemente euclidiano )

para todo x , y , z ∈ X , si xRy y xRz entonces yRz . Por ejemplo, = es una relación euclidiana porque si x = y y x = z entonces y = z .

Euclidiano izquierdo

para todo x , y , z ∈ 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 buena fundamentación implica la condición de cadena descendente (es decir, no puede existir una cadena infinita ... x _n R ... Rx ₃ Rx ₂ Rx ₁  ). Si se asume 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:

Como un conjunto

Para todo x ∈ X , la clase de todos los y tales que yRx es un conjunto. (Esto solo tiene sentido si se permiten relaciones sobre clases propias).

Exclusivo de la izquierda

para todo x , z ∈ X y todo y ∈ Y , si xRy y zRy entonces x = z .

Univalente

para todo x ∈ X y todo y , z ∈ Y , si xRy y xRz entonces y = z . ^{[ 14 ]}

Total (también llamado total izquierdo)

Para todo x ∈ X existe un y ∈ Y tal que xRy . Esta propiedad es diferente de la definición de conexo (también llamado total por algunos autores).

Sobreyectiva (también llamada total derecha)

para todo y ∈ Y , existe un x ∈ 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 , es una relación que es reflexiva, antisimétrica y transitiva. Un orden parcial estricto , también llamado orden estricto , 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 simétrica y transitiva. Una relación de equivalencia es una relación reflexiva, simétrica y transitiva. Además, es una relación simétrica, transitiva y total, ya que estas propiedades implican reflexividad.

Una relación univalente también puede denominarse función parcial . Una función (total) es una función parcial que es total por la izquierda. Una función inyectiva (o parcial) es aquella cuya inversa es univalente. Una función sobreyectiva es aquella que es total por la derecha.

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 ∈ X } ∪ R o la relación reflexiva más pequeña sobre X que contiene a R . Se puede demostrar que esto es igual a la intersección de todas las relaciones reflexivas que contienen a R .

Reducción reflexiva , R ^≠

Definido como R ^≠ = R \ {( x , x ) | x ∈ X } o la mayor relación irreflexiva sobre X contenida en R .

Cierre transitivo , R ⁺

Definida como la relación transitiva más pequeña sobre X que contiene a R. Se puede ver que esto 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 a R .

Cierre simétrico transitivo reflexivo , R ^≡

Definida como la relación de equivalencia más pequeña sobre X que contiene a R.

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

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

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

Nótese que S ( n , k ) se refiere a los números de Stirling de segundo tipo .

Notas:

• El número de relaciones irreflexivas es el mismo que el de relaciones reflexivas.
• El número de órdenes parciales estrictas (relaciones transitivas irreflexivas) es el mismo que el de órdenes parciales.
• El número de pedidos débiles estrictos es el mismo que el de pedidos anticipados totales.
• Los pedidos totales son los pedidos parciales que también son pedidos anticipados totales. Por lo tanto, el número de pedidos anticipados que no son ni pedidos parciales ni pedidos anticipados totales es 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. Las relaciones no simétricas se pueden agrupar en cuádruples (relación, complemento, inversa , complemento inverso).

• Relaciones de orden , incluyendo órdenes estrictas :
  • Más que
  • Mayor o igual que
  • Menos que
  • Menor o igual que
  • Divide (en partes iguales)
  • Subconjunto de
• Relaciones de equivalencia :
  • Igualdad
  • Paralelo con (para espacios afines )
  • Equinumerosidad o "está en biyección con"
  • Isomórfico
  • segmentos de línea equipolent
• 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

• 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 denomina relación n -aria.