Tanto la lógica de segundo orden( $\mathsf{SOL}$ ) y la lógica de primer orden infinita $\frak{L}_{\infty,\infty}$ son extensiones propias de la lógica de primer orden( $\mathsf{FOL}$ ), es decir, son extensiones de un $\mathsf{FOL}$ y también estrictamente más fuerte que ella en poder expresivo. Es natural preguntarse si son comparables. Si es así, ¿cuál es más potente?
Respuestas
¿Demasiados anuncios?
ManuelSchneid3r
Puntos
116
Mientras que Lógica teórica de modelos es, en efecto, una fuente maravillosa, para esta pregunta en particular es exagerada. La lógica $\mathfrak{L}_{\infty,\infty}$ y $SOL$ son incomparable en un sentido preciso.
Una dirección es fácil. $\mathfrak{L}_{\infty,\infty}$ fija cada estructura hasta el isomorfismo: si $\mathcal{A}$ tiene cardinalidad $\kappa$ entonces hay un $\mathfrak{L}_{\kappa^+,\kappa^+}$ -sentencia $\varphi_\mathcal{A}$ cuyos modelos son exactamente aquellas estructuras isomorfas a $\mathcal{A}$ .
- Tenga en cuenta que en el caso $\kappa=\omega$ tenemos una importante mejora en Teorema del isomorfismo de Scott que dice que $\mathfrak{L}_{\omega_1,\omega}$ (que se comporta mucho mejor que $\mathfrak{L}_{\omega_1,\omega_1}$ ) es suficiente. Eso no es cierto en general más allá de $\omega$ Sin embargo.
Por el contrario, $SOL$ no lo hace por el simple hecho de que es demasiado pequeño - aunque es bastante difícil encontrar una estructura que SOL no pueda precisar, sabemos que debe haber una (de hecho, tiene que haber una de cardinalidad $\le 2^{\aleph_0}$ ).
De manera más general, $\mathfrak{L}_{\infty,\infty}$ es demasiado grande para ser un sublogo de cualquier set-sized lógica.
También se da el caso de que $SOL$ no es un sublogo de $\mathfrak{L}_{\infty,\infty}$ Aunque esto requiere un poco más de reflexión.
La clave es:
Si $\varphi$ es un $\mathfrak{L}_{\infty,\infty}$ -en el lenguaje vacío, entonces hay una $\kappa$ de manera que $\varphi$ es válida para toda estructura de cardinalidad $>\kappa$ o $\varphi$ falla de toda estructura de cardinalidad $>\kappa$ .
Este es un buen ejercicio, y de hecho podemos tomar $\kappa=\vert\varphi\vert+\aleph_0$ .
Por el contrario, esto es claramente falso para $SOL$ . Por ejemplo, hay un $SOL$ -sentencia en el lenguaje vacío que es verdadera exactamente en aquellas estructuras cuya cardinalidad es un cardinal sucesor infinito: "El dominio es infinito y hay algún subconjunto $A$ del dominio no en biyección con el conjunto tal que todo subconjunto del dominio que contenga $A$ está en biyección con $A$ o en biyección con todo el dominio".
Dicho esto, si bien ninguna de las dos lógicas contiene a la otra, no cabe duda de que podemos establecer comparaciones. En general, yo diría que $SOL$ recoge mucha más teoría de conjuntos que $\mathfrak{L}_{\infty,\infty}$ y, por lo tanto, en ese sentido es posiblemente más potente (y con menos comportamiento); por otro lado, la relación de equivalencia lógica para $\mathfrak{L}_{\infty,\infty}$ es más fino que el de $SOL$ (es sólo $\cong$ al fin y al cabo), por lo que cuando nos centramos en estructuras individuales en lugar de en clases de estructuras o en hechos teóricos de conjuntos de fondo $\mathfrak{L}_{\infty,\infty}$ domina por completo.
Sé que a veces puede ser un poco irritante dar referencias de libros aquí, cuando pueden no estar fácilmente disponibles. Pero el libro de Barwise y Feferman Lógica teórica de modelos es ahora disponible gratuitamente en el Proyecto Euclides y contiene una gran cantidad de información sobre las lógicas infinitas y de segundo orden. El capítulo 9 de el libro clásico sobre lógica de segundo orden de Stewart Shapiro que lamentablemente no está disponible de forma tan gratuita, resume muchos resultados (son bastante sensibles a la cardinalidad de los lenguajes infinitos).
0 votos
Este pregunta relacionada se pregunta si la lógica de segundo orden es más expresiva que la lógica infinita y, en caso afirmativo, cómo se pueden traducir oraciones arbitrarias de la lógica infinita a oraciones de la lógica de segundo orden.