Clausura transitiva

Relaciones binarias transitivas v t e
Simétrico Antisymmetric Conectado Bien fundada Has joineds Has meets Reflexivo Irreflexivo Asimétrica Total, Semiconnex Anti- reflexivo Equivalencia relación Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorden (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Orden parcial ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preordenado ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Orden total ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Bien ordenado ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Bien ordenado ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Orden parcial estricta ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden débil estricto ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden total estricta ✗ Y Y ✗ ✗ ✗ ✗ Y Y Simétrico Antisymmetric Conectado Bien fundada Has joineds Has meets Reflexivo Irreflexivo Asimétrica Definiciones, para todos a,b{displaystyle a,b} y Sل ل ∅ ∅ :{displaystyle Sneq varnothing:} aRb⇒ ⇒ bRa{displaystyle {begin{aligned}ducaRb\\\\\\\\\\\\\\\\\\\}}}}} aRbybRa⇒ ⇒ a=b{displaystyle {begin{aligned}aRb{text{ and } {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fn}}}}}}}} aل ل b⇒ ⇒ aRbobRa{displaystyle {begin{aligned}aneq {} {fn}} {fn} {fn}} {fn}} {fn}}}} {fn}}}}}} {fn}}}} minSexiste{displaystyle {begin{aligned}min} S\{text{exists}end{aligned}} aAlternativa Alternativa bexiste{displaystyle {begin{aligned}avee b{text{exists}end{aligned}}} a∧ ∧ bexiste{displaystyle {begin{aligned}awedge b\{text{exists}end{aligned}}} aRa{displaystyle aRa} noaRa{displaystyle {text{not }a Ra. aRb⇒ ⇒ nobRa{displaystyle {begin{aligned}aRb Rightarrow Raend{aligned}}
Y indica que la propiedad de la columna es siempre verdad el término de la fila (a la izquierda), mientras que ✗ indica que la propiedad no está garantizada en general (puede, o no, mantener). Por ejemplo, que cada relación de equivalencia es simétrica, pero no necesariamente antisimétrica, se indica por Y en la columna "Simétrica" y ✗ en la columna "Antisimétrica", respectivamente. Todas las definiciones requieren tácitamente la relación homogénea R{displaystyle R. ser transitivo: para todos a,b,c,{displaystyle a,b,c,} si aRb{displaystyle ARb! y bRc{displaystyle bRc} entonces aRc.{displaystyle aRc.} La definición de un término puede requerir propiedades adicionales que no se enumeran en esta tabla.

En matemáticas, el cierre transitivo R⁺ de una relación binaria homogénea R en un conjunto X es la relación más pequeña en X que contiene R y es transitiva. Para conjuntos finitos, "menor" puede tomarse en su sentido habitual, de tener la menor cantidad de pares relacionados; para conjuntos infinitos R⁺ es el superconjunto transitivo mínimo único de R .

Por ejemplo, si X es un conjunto de aeropuertos y x R y significa "hay un vuelo directo desde el aeropuerto x a aeropuerto y" (para x y y en X), luego el cierre transitivo de R en X es la relación R⁺ tal que x R⁺ y significa "es posible volar desde x a y en uno o más tramos".

Más formalmente, el cierre transitivo de una relación binaria R en un conjunto X es la relación transitiva más pequeña (w.r.t. ⊆) R⁺ en X tal que R ⊆ R⁺; ver Lidl & Pilz (1998, pág. 337). Tenemos R⁺ = R si, y solo si, R en sí misma es transitiva.

Por el contrario, la reducción transitiva aduce una relación mínima S a partir de una relación dada R tal que tienen el mismo cierre, es decir, S⁺ = R⁺; sin embargo, pueden existir muchas S diferentes con esta propiedad.

Tanto el cierre transitivo como la reducción transitiva también se utilizan en el área estrechamente relacionada de la teoría de grafos.

Relaciones transitivas y ejemplos

Una relación R sobre un conjunto X es transitiva si, para todo x, y, z en X, siempre que x R y y y R z luego x R z. Los ejemplos de relaciones transitivas incluyen la relación de igualdad en cualquier conjunto, el "menor que o igual" relación en cualquier conjunto linealmente ordenado, y la relación "x nació antes de y" en el plató de todas las personas. Simbólicamente, esto se puede denotar como: si x < y y y < z luego x < z.

Un ejemplo de una relación no transitiva es "se puede llegar a la ciudad x a través de un vuelo directo desde la ciudad y" en el plató de todas las ciudades. Simplemente porque hay un vuelo directo de una ciudad a una segunda ciudad, y un vuelo directo de la segunda ciudad a la tercera, no implica que haya un vuelo directo de la primera ciudad a la tercera. El cierre transitivo de esta relación es una relación diferente, a saber, "hay una secuencia de vuelos directos que comienza en la ciudad x y termina en la ciudad y". Toda relación se puede extender de manera similar a una relación transitiva.

Un ejemplo de una relación no transitiva con un cierre transitivo menos significativo es "x es el día de la semana después de y". El cierre transitivo de esta relación es "algún día x viene después de un día y en el calendario", lo cual es trivialmente cierto para todos los días de la semana x y y (y por lo tanto equivalente al cuadrado cartesiano, que es "x y y son ambos días de la semana").

Existencia y descripción

Para cualquier relación R, la clausura transitiva de R siempre existe. Para ver esto, observe que la intersección de cualquier familia de relaciones transitivas es nuevamente transitiva. Además, existe al menos una relación transitiva que contiene R, a saber, la trivial: X × X. La clausura transitiva de R viene dada por la intersección de todas las relaciones transitivas que contienen R.

Para conjuntos finitos, podemos construir el cierre transitivo paso a paso, comenzando desde R y agregando aristas transitivas. Esto da la intuición para una construcción general. Para cualquier conjunto X, puede probar que la clausura transitiva viene dada por la siguiente expresión

R+=⋃ ⋃ i=1JUEGO JUEGO Ri.{displaystyle R^{+}=bigcup ¿Qué?

Donde Ri{displaystyle R^{i} es i- el poder de R, definida inductivamente por

R1=R{displaystyle R^{1}=R}

y, para 0}" xmlns="http://www.w3.org/1998/Math/MathML">i■0{displaystyle i confía0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f49f2878fd68a89c3da37eb537198e887cf0293" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;"/>,

Ri+1=R∘ ∘ Ri{displaystyle R^{i+1}=Rcirc R^{i}

Donde ∘ ∘ {displaystyle circ } denota la composición de las relaciones.

Para mostrar que la definición anterior de R⁺ es la relación menos transitiva que contiene R, mostramos que contiene R , que es transitivo y que es el conjunto más pequeño con ambas características.

• R⊆ ⊆ R+{displaystyle Rsubseteq R^{+}: R+{displaystyle R^{+} contiene todo el Ri{displaystyle R^{i}, así en particular R+{displaystyle R^{+} contiene R{displaystyle R..
• R+{displaystyle R^{+} es transitivo: Si ()s1,s2),()s2,s3)▪ ▪ R+{displaystyle (s_{1},s_{2}),(s_{2},s_{3})in R^{+}}, entonces ()s1,s2)▪ ▪ Rj{displaystyle (s_{1},s_{2}in R^{j} y ()s2,s3)▪ ▪ Rk{displaystyle (s_{2},s_{3})in R^{k} para algunos j,k{displaystyle jk} por definición R+{displaystyle R^{+}. Puesto que la composición es asociativa, Rj+k=Rj∘ ∘ Rk{displaystyle R^{j+k}=R^{j}circ R^{k}; por lo tanto ()s1,s3)▪ ▪ Rj+k⊆ ⊆ R+{displaystyle (s_{1},s_{3})in R^{j+k}subseteq R^{+} por definición ∘ ∘ {displaystyle circ } y R+{displaystyle R^{+}.
• R+{displaystyle R^{+} es mínimo, es decir, T{displaystyle T} es cualquier relación transitiva que contenga R{displaystyle R., entonces R+⊆ ⊆ T{displaystyle R^{+}subseteq T}: Dado cualquiera T{displaystyle T}, inducción en i{displaystyle i} se puede utilizar para mostrar Ri⊆ ⊆ T{displaystyle R^{i}subseteq T} para todos i{displaystyle i} como sigue: Base: R1=R⊆ ⊆ T{displaystyle R^{1}=Rsubseteq T} por supuesto. Paso: Si Ri⊆ ⊆ T{displaystyle R^{i}subseteq T} y ()s1,s3)▪ ▪ Ri+1=R∘ ∘ Ri{displaystyle (s_{1},s_{3})in R^{i+1}=Rcirc R^{i}, entonces ()s1,s2)▪ ▪ R{displaystyle (s_{1},s_{2})in R} y ()s2,s3)▪ ▪ Ri{displaystyle (s_{2},s_{3})in R^{i} para algunos s2{displaystyle s_{2}, por definición ∘ ∘ {displaystyle circ }. Por lo tanto, ()s1,s2),()s2,s3)▪ ▪ T{displaystyle (s_{1},s_{2}),(s_{2},s_{3})in T} por suposición y por hipótesis de inducción. Por lo tanto ()s1,s3)▪ ▪ T{displaystyle (s_{1},s_{3})in T} por transitividad T{displaystyle T}; esto completa la inducción. Finalmente, Ri⊆ ⊆ T{displaystyle R^{i}subseteq T} para todos i{displaystyle i} implicación R+⊆ ⊆ T{displaystyle R^{+}subseteq T} por definición R+{displaystyle R^{+}.

Propiedades

La intersección de dos relaciones transitivas es transitiva.

La unión de dos relaciones transitivas no necesita ser transitiva. Para preservar la transitividad, se debe tomar la clausura transitiva. Esto ocurre, por ejemplo, al tomar la unión de dos relaciones de equivalencia o dos preórdenes. Para obtener una nueva relación de equivalencia o preorden se debe tomar la clausura transitiva (la reflexividad y la simetría —en el caso de las relaciones de equivalencia— son automáticas).

En teoría de grafos

En informática, el concepto de cierre transitivo se puede considerar como la construcción de una estructura de datos que hace posible responder preguntas de accesibilidad. Es decir, ¿se puede ir del nodo a al nodo d en uno o más saltos? Una relación binaria solo te dice que el nodo a está conectado al nodo b, y que el nodo b está conectado al nodo c, etc. Después de la se construye un cierre transitivo, como se muestra en la siguiente figura, en una operación O(1) se puede determinar que el nodo d es accesible desde el nodo a. La estructura de datos generalmente se almacena como una matriz booleana, por lo que si matrix[1][4] = true, entonces el nodo 1 puede llegar al nodo 4 a través de uno o más saltos.

El cierre transitivo de la relación de adyacencia de un gráfico acíclico dirigido (DAG) es la relación de accesibilidad del DAG y un orden parcial estricto.

El cierre transitivo de un grafo no dirigido produce un grafo de conglomerados, una unión disjunta de camarillas. Construir el cierre transitivo es una formulación equivalente del problema de encontrar los componentes del gráfico.

En lógica y complejidad computacional

El cierre transitivo de una relación binaria no puede, en general, expresarse en lógica de primer orden (FO). Esto significa que no se puede escribir una fórmula usando los símbolos de predicado R y T que se cumplirán en cualquier modelo si y solo si T es la clausura transitiva de R. En la teoría de modelos finitos, la lógica de primer orden (FO) extendida con un operador de cierre transitivo generalmente se denomina lógica de cierre transitivo y se abrevia FO(TC) o simplemente TC. TC es un subtipo de lógica de punto fijo. El hecho de que FO(TC) sea estrictamente más expresivo que FO fue descubierto por Ronald Fagin en 1974; el resultado fue luego redescubierto por Alfred Aho y Jeffrey Ullman en 1979, quienes propusieron utilizar la lógica de punto fijo como lenguaje de consulta de base de datos. Con los conceptos más recientes de la teoría de modelos finitos, la prueba de que FO(TC) es estrictamente más expresiva que FO se deriva inmediatamente del hecho de que FO(TC) no es local de Gaifman.

En la teoría de la complejidad computacional, la clase de complejidad NL corresponde precisamente al conjunto de oraciones lógicas expresables en TC. Esto se debe a que la propiedad de cierre transitiva tiene una estrecha relación con el problema NL-completo STCON para encontrar caminos dirigidos en un gráfico. De manera similar, la clase L es lógica de primer orden con el cierre transitivo conmutativo. Cuando se agrega el cierre transitivo a la lógica de segundo orden, se obtiene PSPACE.

En lenguajes de consulta de base de datos

Desde la década de 1980, Oracle Database ha implementado una extensión SQL patentada CONNECT BY... START WITH que permite el cálculo de un cierre transitivo como parte de una consulta declarativa. El estándar SQL 3 (1999) agregó una construcción WITH RECURSIVE más general que también permite que los cierres transitivos se calculen dentro del procesador de consultas; a partir de 2011, este último se implementa en IBM Db2, Microsoft SQL Server, Oracle, PostgreSQL y MySQL (v8.0+). SQLite lanzó soporte para esto en 2014.

Datalog también implementa cálculos de cierre transitivos.

MariaDB implementa expresiones de tabla comunes recursivas, que se pueden usar para calcular cierres transitivos. Esta función se introdujo en la versión 10.2.2 de abril de 2016.

Algoritmos

En Nuutila (1995) se pueden encontrar algoritmos eficaces para calcular el cierre transitorio de la relación adyacencia de un gráfico. Reducir el problema a las multiplicaciones de matrices adjacency logra la menor complejidad del tiempo, es decir, la de la multiplicación de matriz (Munro 1971, Fischer & Meyer 1971), que es O()n2.3728596){displaystyle O(n^{2.3728596} a diciembre de 2020. Sin embargo, este enfoque no es práctico ya que tanto los factores constantes como el consumo de memoria para gráficos escasos son altos (Nuutila 1995, págs. 22 a 23, secc.2.3.3). El problema también puede ser resuelto por el algoritmo Floyd-Warshall en O()n3){displaystyle O(n^{3}}, o por repetida búsqueda de la primera amplitud o búsqueda de la primera profundidad a partir de cada nodo del gráfico.

Para gráficos dirigidos, el algoritmo de Purdom resuelve el problema por primera vez computando su condensación DAG y su cierre transitivo, luego levantarlo al gráfico original. Es hora de correr. O()m+μ μ n){displaystyle O(m+mu n)}, donde μ μ {displaystyle mu } es el número de bordes entre sus componentes fuertemente conectados.

Investigaciones más recientes han explorado formas eficientes de calcular el cierre transitivo en sistemas distribuidos basados en el paradigma MapReduce.