Dejemos que $S$ sea un conjunto, y que $R$ sea una relación con $\operatorname{dom}(R) = \operatorname{ran}(R) = S$ . Por lo tanto, $R \subseteq S \times S$ . Sea $T$ sea el cierre transitivo de $R$ definida como la menor relación transitiva que contiene $R$ . O, simbólicamente: $$T = \bigcap\, \{U: R \subseteq U\subseteq S\times S \; \wedge \; U\,\mathrm{is\;transitive} \}.$$
(Ya que $S \times S$ es una relación transitiva, el argumento de la $\bigcap$ operador anterior es no vacío).
Hace poco me encontré con la siguiente afirmación, que creo que es correcta, pero que me cuesta probar.
Reclamación: Si $x, y \in S$ y $xTy$ Entonces, o bien $xRy$ o existe un $z \in S$ tal que $xTz$ y $zRy$ .
Creo que esta afirmación es cierta, porque visualizo el proceso de creación del cierre transitivo de una relación como uno de "añadir recursivamente el par $(a, c)$ siempre que los pares $(a, b)$ y $(b, c)$ están disponibles, hasta que no se puedan añadir más pares". Por lo tanto, si (1) el cierre transitivo $T$ de $R$ incluye el par $(a, c)$ y (2) es no el caso de que $a R c$ entonces debe existir algún $b \in S$ tal que $aTb$ y $bTc$ . Esto no está muy lejos de la afirmación más fuerte de que el $b$ es tal que no sólo $bTc$ pero que $bRc$ .
Pero todo esto es un juego de manos, basado en mi visión intuitiva de algún "proceso" imaginario por el que se "genera" el cierre transitivo de una relación.
El problema de demostrar la afirmación anterior se hace aún más difícil por el hecho de que me encontré con ella en el curso de la resolución de un problema sobre los ordinales de Zermelo en un libro de texto de teoría de conjuntos, y este problema se produjo antes de el autor había llegado a describir incluso una relación de orden para los ordinales de Zermelo, por no hablar de un buen ordenamiento para ellos, o cualquier noción de inducción o recursión basada en ellos 1 .
De hecho, para el problema del libro de texto, lo único que se podría asumir es el Axioma del Infinito original de Zermelo (es decir $\exists w [\varnothing \in w \ \wedge \ \forall x\in w (\{x\} \in w)]$ ) junto con los restantes axiomas de ZF actualmente estándar 2 .
Sin recursión, inducción, ordenación, etc. No sé ni por dónde empezar a demostrar la afirmación anterior.
Por supuesto, entiendo que $(R \subseteq T) \leftrightarrow ((x, y) \in R \to (x, y) \in T) \leftrightarrow (xRy \to xTy)$ . Por lo tanto, veo que si $xTy$ Una posibilidad es que $xRy$ . Mi problema es demostrar que $$(xTy \wedge \lnot xRy)\to \exists z \in S(xTz \wedge zRy)$$
EDITAR: Una forma diferente de plantear el mismo problema utiliza la noción de composición de relaciones. La página web composición $G \circ F$ de las relaciones $G$ y $F$ se define como $$G \circ F := \{(x, y) \in \operatorname{dom}(F) \times \operatorname{ran}(G): \exists z[(x, z) \in F \wedge (z, y) \in G]\}.$$
Esta notación permite la siguiente caracterización de la transitividad: una relación $U$ es transitivo si $U\circ U \subseteq U$ .
Esta notación también se puede utilizar para dar una formulación equivalente de la afirmación anterior como una afirmación sobre la inclusión de conjuntos: $$ T \subseteq R \cup (R \circ T).$$
No es difícil mostrar la inclusión contraria: $$R \subseteq T \to R\circ T \subseteq T \circ T = T \to R \cup (R \circ T) \subseteq T,$$
...así que probar la conclusión deseada equivale a probar que
$$ T = R \cup (R \circ T).$$
1 De hecho, la afirmación sobre cierres transitivos de la que trata este post surgió en el contexto de demostrar que el cierre transitivo de la $\in$ podría servir para ordenar bien el conjunto $z$ de los ordinales de Zermelo. A diferencia de lo que ocurre con los ordinales de von Neumman, ahora estándar, donde para dos distintos cualesquiera de ellos, $m$ y $n$ , ya sea $m \in n$ o $n \in m$ con los ordinales de Zermelo, el $\in$ La relación sólo es válida entre dicho ordinal $n$ y su sucesor $\{n\}$ . Por lo tanto, $\in\!\!|_z\subseteq z \times z$ ni siquiera es un parcial para $z$ (ya que no es transitiva), y mucho menos un ordenamiento adecuado para ella.
2 Extensionalidad, Fundamentación, Comprensión/Separación, Emparejamiento, Unión, Sustitución y Conjunto de Poderes.
