¿Por qué no se puede expresar la alcanzabilidad en lógica de primer orden?

Question

Me pregunto por qué no podemos expresar la alcanzabilidad de los grafos en la lógica de primer orden prácticamente de la misma manera que la expresamos en la lógica existencial de segundo orden. Para SOL, una definición es :

1 . L es un orden lineal sobre un subconjunto de vértices :

$$\begin{align} \psi_1 = &\forall u \neg L(u,u) \\ &\wedge \forall u\forall v (L(u,v) \Rightarrow \neg L(v,u)) \\ & \wedge \forall u\forall v \forall w(L(u,v) \wedge L(v,w) \Rightarrow L(u,w)) \end{align} $$

2 . Dos vértices consecutivos cualesquiera en el orden deben estar unidos por una arista en G:

$$\begin{align} \psi_2 = &\forall u\forall v ((L(u,v) \ \wedge \forall w(\neg L(u,w) \vee \neg L(w,v))) \\ & \Rightarrow E(u,v)). \end{align} $$

3 . El primer vértice del orden es x y el último es y y x, y están en el orden:

$$\begin{align} \psi_3 = &(\forall u\ \neg L(u,x)) \wedge (\forall v\ \neg L(y,v)) \ \wedge L(x,y) \end{align} $$

y finalmente la expresión para la alcanzabilidad es

4 . $\phi(x,y) =\exists L (x=y) \vee (\psi_1 \wedge \psi_2 \wedge \psi_3))$

Pero, ¿por qué no podemos usar lo mismo en lógica de primer orden (es decir, no hay cuantificación existencial sobre L) :

$\phi(x,y) =(x=y) \vee (\psi_1 \wedge \psi_2 \wedge \psi_3))$

Esto se interpretaría sobre el vocabulario con modelos M que tienen dos relaciones binarias : E (borde) y L (alcanzable), y el universo de todos los nodos. Seguramente cualquier modelo que satisfaga la expresión 5 anterior tendrá su relación L expresando un ordenamiento lineal de los nodos, con dos elementos consecutivos cualesquiera siendo adyacentes en E - en otras palabras, será la relación "Alcanzable", (y el modelo mapeará las variables libres x e y a los nodos N1 y N2, con (N1,N2) en L, lo que significa que N2 es alcanzable desde N1).

¿Por qué no funciona? En concreto, ¿fracasaría la prueba de no expresabilidad de la alcanzabilidad para ello?

La prueba de la no expresabilidad de la alcanzabilidad en FOL es así:

---

Supongamos que existe una expresión FOL p, con variables libres x e y, que expresa la alcanzabilidad.

Tenemos $s_1 \equiv \forall x \forall y \ p$ que indica que todos los nodos son alcanzables desde todos los nodos, es decir, que el grafo está fuertemente conectado.

A continuación, añadimos dos frases sobre E, $s_2$ (diciendo que cada nodo del grafo tiene un grado menor que uno), y $s_3$ (que cada nodo tiene indegree uno). La conjunción de las tres frases anteriores

$s_4 = s_1 \wedge \ s_2 \wedge \ s_3$ ,

entonces afirma que el grafo está fuertemente conectado y que todos los nodos tienen indegree y outdegree uno - es decir, es un ciclo.

Como hay ciclos finitos con tantos nodos como se desee, s4 tiene modelos finitos arbitrariamente grandes. Por lo tanto, por el teorema de Lowenheim-Skolem, también tiene un modelo infinito. Pero los ciclos infinitos no existen, por lo que nuestra suposición de que existe una p que expresa la alcanzabilidad se contradice.

---

Si nuestra expresión FOL (5) se toma como la expresión p de la prueba, todos los pasos de la prueba se pueden llevar a cabo igual, y nos llevarán al mismo resultado, a saber, que (5) no expresa la alcanzabilidad. Pero, ¿por qué no? Ciertamente tiene todos los elementos..

Answer 1

El problema está en la terminología. Usted puede expresar la alcanzabilidad en la lógica de primer orden; por ejemplo, se puede expresar en el lenguaje de la teoría de conjuntos cuantificando sobre los caminos en el gráfico, y la teoría de conjuntos es una teoría de primer orden.

No se puede expresar la alcanzabilidad en el lenguaje particular donde las únicas relaciones disponibles son la relación de incidencia en el grafo y la igualdad, y donde la cuantificación sólo se permite sobre los elementos del grafo. Así que la cuestión tiene muy poco que ver con la "lógica de primer orden", y todo que ver con el lenguaje particular que se permite. La tradición dice que esta situación se formula como "la alcanzabilidad no puede expresarse en lógica de primer orden", aunque esa frase podría interpretarse de otras maneras.

Ignorando las cuestiones terminológicas, puede ser realmente útil saber que la alcanzabilidad no puede expresarse sin cuantificar sobre conjuntos o caminos de alguna manera. Por ejemplo, este hecho significa que si el grafo se almacena en una base de datos SQL de forma natural, será más difícil codificar una consulta SQL que diga si un par arbitrario de nodos tiene un camino que si esa relación pudiera expresarse en el lenguaje limitado mencionado anteriormente.

Por cierto, así es como se demuestra que no hay fórmula $\phi(a,b)$ expresando la alcanzabilidad. Tomemos el lenguaje de la teoría de grafos mencionado anteriormente y añadamos dos nuevas constantes $C$ y $D$ . Tomemos el conjunto infinito de axiomas "no hay ningún camino de longitud $1$ de $C$ a $D$ ", "no hay ningún camino de longitud dos desde $C$ a $D$ ", ... Entonces cualquier finito conjunto de estos axiomas es consistente con $\phi(a,b)$ como se puede ver observando un gráfico con un camino infinitamente largo y tomando $C$ y $D$ para estar lo suficientemente separados. Así, por el teorema de la compacidad, el conjunto de todos esos axiomas es consistente con $\phi(C,D)$ . Pero si todos esos axiomas son verdaderos en un grafo, no hay ningún camino desde $C$ a $D$ en ese gráfico, por lo que $\phi$ no expresó correctamente esa propiedad.

Answer 2

"Seguramente cualquier modelo que satisfaga la expresión 5 anterior tendrá su relación L expresando un ordenamiento lineal de los nodos, con dos elementos consecutivos cualesquiera siendo adyacentes en E" - esto es cierto, pero la definición de expresabilidad de primer orden (con respecto a algún lenguaje fijo) es una equivalencia, y no una implicación. El otro lado de la implicación, es decir, " $(\mathbb{G}, a,b)$ satisface la accesibilidad => satisface la expresión 5" es falso. Recuerde que si su lenguaje contiene la relación $L$ entonces en cualquier estructura $\mathbb{G}$ para esa lengua, la interpretación $L^\mathbb{G}$ es fijo. Ahora, para ver que la implicación no se cumple, tomemos cualquier gráfico conectado $\mathbb{G}$ con $L^\mathbb{G} = \{(a,a): a \in G\}$ . Ahora, por ejemplo, para cualquier gráfico que sea realmente un ciclo de tamaño al menos 2 que esté conectado la estructura $(\mathbb{G}, L^\mathbb{G})$ es obviamente conectado (como un grafo), por lo que cada dos nodos son alcanzables, sin embargo para cualquier $a \neq b$ la estructura $(\mathbb{G}, L^\mathbb{G}, a, b)$ no satisface la expresión 5.

La causa de este problema es que, efectivamente, hay que cuantificar sobre las relaciones binarias para elegir el $L$ para expresar la accesibilidad (o la conectividad).