Supongamos que tengo un lenguaje con dos símbolos de relación binaria $R$ y $R^\ast$ . Supongamos que tengo una teoría de primer orden $T$ que dice algunas cosas sobre $R$ , pero nada sobre $R^\ast$ . ¿Existe un conjunto de axiomas que pueda añadir a $T$ que dicen que $R^\ast$ es el cierre reflexivo y transitivo de $R$ ? (Lo ideal sería que los axiomas hicieran que esto fuera realmente cierto en el modelo; pero también sería interesante algún tipo de solución que se quedara corta). Está claro que esto se puede hacer en lógica de segundo orden; pero ¿se puede hacer en lógica de primer orden? Supongo que no se puede, pero en ese caso sería muy interesante ver una prueba de imposibilidad.
Respuestas
¿Demasiados anuncios?
Es bastante obvio que $R^*$ se puede axiomatizar en la lógica $L_{\omega_1 \omega}$ utilizando un $\omega$ -pero de hecho no puede ser axiomatizada en la lógica de primer orden finitaria.
Considere la siguiente teoría $\mathbb{T}$ :
-
Hay un elemento único $z$ de tal manera que no no existe un elemento $y$ tal que $y \mathrel{R} z$ .
-
Para cada elemento $x$ hay un elemento único $y$ tal que $x \mathrel{R} y$ .
-
$R^*$ es el cierre reflexivo-transitivo de $R$ .
-
Para $z$ como en el axioma 1, para todos los elementos $x$ , $z \mathrel{R^*} x$ .
Dejemos que $M$ sea un modelo de $\mathbb{T}$ . Claramente, $M$ es contablemente infinito: de hecho tiene que ser un modelo de aritmética de segundo orden. Por lo tanto, si $\mathbb{T}$ fueran axiomatizables en la lógica de primer orden finitaria, entonces esto contradiría el teorema ascendente de Löwenheim-Skolem.
JoshL
Puntos
290
Depende completamente del lenguaje de primer orden que se utilice. Si quieres usar sólo el lenguaje con los símbolos $R$ y $R^*$ se puede expresar que $R^*$ es una relación transitiva reflexiva que extiende $R$ pero no se puede expresar en este idioma que $R^*$ es la relación más pequeña que extiende $R$ . La prueba de que esto no se puede hacer utiliza el teorema de la compacidad, y es un ejercicio algo estándar para la gente acostumbrada a estos ejercicios. Lo pongo a continuación, por si no se ve cómo hacerlo.
Si se pasa al lenguaje de primer orden de la teoría de conjuntos, entonces sí se puede expresar que $R^*$ es el cierre reflexivo y transitivo de $R$ . Quiero señalar esto porque muestra que la cuestión es totalmente sobre el lenguaje y los axiomas, no sobre el término "de primer orden".
Aquí está la prueba de compacidad. Sólo nos preocuparemos por el cierre transitivo, para simplificar. Recordemos que el cierre transitivo $R^*$ es la unión de una secuencia de relaciones $$ R = R_0 \subseteq R_1 \subseteq \cdots $$ donde $R_{i+1}$ incluye un par $(a,c)$ si hay un $b$ tal que $(a,b)$ y $(b,c)$ están en $R_{i}$ . En otras palabras, ver el original $R$ como un gráfico, $R_{i}(a,b)$ se mantiene si y sólo si existe un camino de longitud $\leq i+1$ de $a$ a $b$ en el gráfico.
Dejemos que $\Gamma$ sea cualquier conjunto de oraciones en el lenguaje $(R,R^*)$ que se satisface cuando $R^*$ es el cierre transitivo de $R$ . Añade dos nuevos símbolos constantes $a$ y $b$ al lenguaje, y añadir axiomas que establezcan que $R^*(a,b)$ sostiene y $R(a,b)$ no lo hace. Finalmente, añade una secuencia infinita de axiomas que dice que $R_1(a,b)$ es falso, $R_2(a,b)$ es falso, etc. A continuación se explica cómo hacer esto para $R_1$ y $R_3$ puedes ver el patrón: $$ R_1(a,b) \equiv (\exists x)[R(a,x) \land R(x,b)] $$ $$ R_3(a,b) \equiv (\exists x)( \exists y)(\exists z)[R(a,x) \land R(x,y) \land R(y,z) \land R(z,b)] $$
Ahora la teoría resultante $T = \Gamma \cup \{\lnot R(a,b), R^*(a,b), \lnot R_1(a,b), \lnot R_2(a,b),\ldots\}$ es finitamente satisfacible, porque cualquier subconjunto finito se satisface empezando por $R$ a partir de un gráfico lineal finito de longitud suficiente, dejando que $a$ y $b$ sean los puntos finales y $R^*$ sea el cierre transitivo. Por tanto, toda la teoría es satisfacible. En un modelo de $T$ , $R^*$ no es el cierre transitivo de $R$ porque $R^*(a,b)$ se mantiene pero, por construcción, $(a,b)$ no está en el cierre transitivo de $R$ en ese modelo. Así, $\Gamma$ no aseguró que $R^*$ es el cierre transitivo de $R$ .
