Demostrar que el cierre transitivo de una relación es transitivo sin utilizar la recursión

Question

En el libro de Kunen Teoría de conjuntos (desde 2013) el cierre transitivo de una relación $R$ en $A$ se define como $$ R^* = \{ (x,y) \in A^2 : \text{there is an $ R $-path from $ x $ to $ y $} \} $$ donde un $R$ -ruta de $x$ a $y$ es simplemente una función $s : n+1 \to A$ para algunos $n \in \omega$ tal que $s(0) = x$ y $s(n) = y$ y $s(i) \,R\, s(i+1)$ para todos $i < n$ . Esta es la definición I.9.4 del libro.

Ahora se afirma en el Lemma I.9.5 que $R^*$ es transitiva, la prueba es que esto se ve "fácilmente combinando caminos".

Sin embargo, no puedo averiguar cómo combinar dos caminos sin apelar a la validez de las definiciones recursivas para $\omega$ . La forma en que se presenta en el libro sugiere de alguna manera que esto debería ser posible. De hecho, el objetivo del capítulo parece ser demostrar el principio de recursión para conjuntos bien fundados sin tener que demostrar la recursión para $\omega$ primero.

¿Hay alguna forma de combinar rutas sin tener que usar la recursividad que esté pasando por alto?

También agradecería que alguien me indicara otra prueba del principio de recursividad bien fundamentada en la que no se asuma que ya se conoce la recursividad para $\omega$ .

Answer 1

El cierre transitivo de la relación binaria $R$ se define típicamente como lo siguiente (porque no requiere el axioma del infinito)

$$R^{\mathsf{t}}:=\bigcap\{S'\in\mathscr{P}(\mathrm{fld}(R)\times\mathrm{fld}(R)):R\subseteq S'\,\wedge\,S'\circ S'\subseteq S'\}$$

Si permitimos el axioma del infinito (es decir, la existencia de $\omega$ ) y asumimos que hemos probado la recursión en $\omega$ entonces por Teorema de Kleene tenemos $$\bigcup_{n\in\omega}R_n=R^{\mathsf{t}},$$ donde $R_n$ se define por $R_0=R$ y $R_{n+1}=R_n\cup(R_n\circ R_n)$ . Esta es la otra definición potencial del cierre transitivo. La definición que te han proporcionado es algo más compleja (introduciendo la noción de caminos).

Creo que tienes razón en que la inducción y la recursión en $\omega$ debe asumirse si se proporciona la definición compleja del cierre transitivo. Para ser precisos, lo que se necesita es el siguiente resultado (fácilmente demostrable por inducción) $$\omega=\{n\in\omega:n\sim(n+m)\setminus m\}\qquad(\text{for fixed }m\in\omega)$$ Aquí $\sim$ es la noción de que dos conjuntos son equinuméricos (es decir, existe una biyección entre los dos conjuntos). Por supuesto, la recursividad es necesaria para definir la suma $+:\omega^2\to\omega$ . Con ese resultado, se pueden concatenar fácilmente dos caminos.

Para una buena exposición de la inducción y la recursión transfinitas (sin tener necesariamente el axioma del infinito--recuerdo que el autor da una formulación equivalente de la definición de una relación binaria para estar bien fundada utilizando tanto el axioma de elección como el del infinito: "no hay ninguna secuencia infinitamente descendente"; esta definición no es necesaria y puede olvidarse si no se está interesado en el axioma del infinito) ver Enderton's Elementary Set Theory Chapter 9. Es la primera sección titulada Relaciones bien fundadas .