¿Existe una lógica tan poderosa que defina todas las estructuras hasta el isomorfismo?

Question

Definiciones. Por a estructura me refiero a un conjunto dotado de algunas operaciones y relaciones finitarias. Por modelo no estándar de una estructura $X$ con respecto a una lógica, me refiero a un modelo de la teoría completa (en el sentido de esa lógica) de $X$ que no sea isomorfo a $X$ . Definamos que una lógica alfileres $X$ si $X$ no tiene modelos no estándar con respecto a esa lógica.

(Se trata de definiciones vagas, por supuesto, ya que no he definido el término "lógica").

Pregunta. ¿Existe una lógica tan poderosa que defina todas las estructuras hasta el isomorfismo?

Antecedentes.

Es bien sabido que la lógica de primer orden a menudo no fija estructuras hasta el isomorfismo. Por ejemplo, $\mathbb{N}$ tiene modelos de primer orden no estándar, lo que significa que existen modelos de la teoría de primer orden de $\mathbb{N}$ que no sean isomorfas a $\mathbb{N}$ . Por lo que he leído, son importantes en el planteamiento de Abraham Robinson sobre el análisis no estándar (del que no sé casi nada).

A la lógica de segundo orden le va un poco mejor. Por ejemplo, $\mathbb{R}$ no tiene modelos de segundo orden no estándar; más precisamente, los axiomas de un campo totalmente ordenado Dedekind-completo tienen precisamente un modelo hasta el isomorfismo, a saber $\mathbb{R}.$ Pero la lógica de segundo orden no determina todas las estructuras, ver aquí . De ahí la pregunta.

Answer 1

Creo que la forma más directa de responder a su pregunta es la siguiente lógica infinita .

Cardenales dados $\kappa, \lambda$ - con $\kappa\ge\lambda$ (ya verá por qué) - dejamos que $\mathcal{L}_{\kappa\lambda}$ sea la lógica que se obtiene tomando la lógica de primer orden y

• cierre bajo $(<\kappa)$ conjunciones -arias, y

• permitiendo la cuantificación sobre $(<\lambda)$ -tuplas de variables.

Por ejemplo, $$\bigvee_{n\in\omega} e=x*. . . *x \mbox{ ($ n $-many "$ * $"s)}$$ es una fórmula de $\mathcal{L}_{\omega_1\omega}$ en el lenguaje de los grupos que afirman que $x$ tiene orden finito.

Las "superlógicas" (no es un término técnico, sino mío) del tamaño de una clase $\mathcal{L}_{\infty\omega}$ y $\mathcal{L}_{\infty\infty}$ se definen de la manera obvia. (Del mismo modo, podemos definir $\mathcal{L}_{\infty\lambda}$ para $\lambda$ arbitraria, pero generalmente son los dos extremos los más interesantes).

Ejercicio . Para cada estructura (del tamaño de un conjunto) $\mathcal{A}$ hay una sola frase $\varphi\in \mathcal{L}_{\infty\infty}[\Sigma]$ (donde $\Sigma$ es el lenguaje de $\mathcal{A}$ ) tal que $\varphi$ caracteriza $\mathcal{A}$ hasta isomorfismo.

---

Ahora, puede que mires esto y pienses: "Eso es algo trivial". Deja que te convenza de que, de hecho, ¡es genial!

En primer lugar, obsérvese que el tamaño propio de la clase de $\mathcal{L}_{\infty\infty}$ es inevitable, ya que hay muchas estructuras del tamaño de un conjunto, incluso de un lenguaje fijo (bueno, no vacío :P). Así que el hecho de que $\mathcal{L}_{\infty\omega}$ es grande no es una evasiva, sino un aspecto necesario.

En segundo lugar, tenga en cuenta que $\mathcal{L}_{\infty\infty}$ es la lógica infinita "más pequeña" que tiene esta propiedad. Para cada $\kappa$ podemos encontrar dos estructuras no isomórficas $\mathcal{A}$ y $\mathcal{B}$ que son $\mathcal{L}_{\infty\kappa}$ -equivalente. Este es un buen ejercicio.

EDITAR : En realidad, hay es un sentido en el que la lógica mucho más débil $\mathcal{L}_{\infty\omega}$ captura toda estructura hasta el isomorfismo: por un teorema de Karp (y una observación de Barwise), $\mathcal{A}\equiv_{\infty\omega}\mathcal{B}$ si existe alguna extensión forzosa en la que $\mathcal{A}\cong\mathcal{B}$ ¡! Así que $\mathcal{L}_{\infty\omega}$ captura toda estructura hasta el "isomorfismo potencial" (que es un concepto rico; véase, por ejemplo. http://arxiv.org/abs/math/9301208 para un análisis de lo difícil que puede ser hacer dos $\mathcal{L}_{\infty\omega}$ -estructuras equivalentes isomorfas, y http://www.jstor.org/stable/1997774?seq=1#page_scan_tab_contents para un bello resultado de que no existe una caracterización similar de $\mathcal{L}_{\infty\lambda}$ para $\lambda$ incontable).

En tercer lugar, estas lógicas infinitas son realmente interesantes en sí mismas. La más interesante con diferencia es $\mathcal{L}_{\omega_1\omega}$ que, junto con su contable razonablemente cerrado fragmentos - tiene profundas conexiones con la teoría descriptiva de conjuntos, la teoría de modelos y la teoría de la computabilidad.

En cuarto y último lugar, nótese que la(s) lógica(s) infinita(s) proporciona(n) una forma realmente agradable de afilar tu pregunta. Puede preguntar:

Para $\mathcal{A}, \mathcal{B}$ estructuras no isomórficas en el mismo lenguaje, ¿tan difícil es distinguirlas?

Una forma de responder a esto es preguntando:

Para qué lógicas infinitas $\mathcal{L}_{\kappa\lambda}$ ¿tenemos $\mathcal{A}\not\equiv_{\kappa\lambda}\mathcal{B}$ ?

Hay un montón de investigación en esta y otras direcciones relacionadas; permítanme empezar con un resultado fundamental sobre contable estructuras:

( Teorema del isomorfismo de Scott .) Para $\mathcal{A}$ una estructura contable en un lenguaje contable, hay una única $\varphi\in\mathcal{L}_{\omega_1\omega}$ - la Sentencia Scott de $\mathcal{A}$ - tal que $\varphi$ caracteriza $\mathcal{A}$ hasta isomorfismo.

Observando fragmentos $\mathcal{L}_{\alpha\omega}$ de $\mathcal{L}_{\omega_1\omega}$ para $\alpha$ a ordinal contable (nótese que la definición dada anteriormente no funciona; mi notación es puramente sugestiva), podemos afinar este teorema, y adjuntar a cada estructura contable un ordinal contable, llamado el Rango de Scott que mide lo difícil que es determinar la estructura hasta el isomorfismo.

Observación 1: ¡Las sentencias Scott y los rangos también tienen sentido para estructuras incontables!

Observación 2: Lamentablemente, existen varias definiciones diferentes no equivalentes del rango de Scott; todas son básicamente iguales, salvo que a veces difieren, por ejemplo, en +1. Véase https://math.berkeley.edu/~antonio/papers/scottRank.pdf .