La aritmética sucesora no es finitamente axiomatizable

¡Este es un gran ejemplo del poder de la compacidad!

Dado que la lógica de primer orden es compacta, es suficiente para mostrar que ninguna sub-axiomatización finita de la axiomatización estándar dada en su pregunta anterior hará el trabajo (ver, por ejemplo, aquí ). Y esto es algo que podemos hacer concretamente: dejar$\mathcal{M}_n$ser la estructura sucesora consistente en una copia de$\mathbb{N}$como de costumbre y luego por separado$n$-ciclo, puede comprobar rápidamente que cada$\mathcal{M}_n$satisface la primera$n$-muchos axiomas de la teoría, pero ninguno$\mathcal{M}_n$satisface toda la teoría.

Mientras tanto, tenga en cuenta que nada como esto puede ser muy útil para$\mathsf{PA}$o$\mathsf{ZFC}$, cada uno de los cuales tiene subteorías finitamente axiomatizadas sin modelos "simplemente descriptibles". Y, por supuesto, toda la idea se derrumbaría si estuviéramos trabajando en una lógica no compacta : mostrar que una teoría de segundo orden dada, por ejemplo, no es finitamente axiomatizable suele ser extremadamente difícil ya que no podemos simplificar las cosas centrándonos en una sola familia bien entendida de axiomatizaciones finitas candidatas.

La compacidad se mencionó en otra respuesta, pero la compacidad es un poco una pista falsa aquí. Podemos hacer todo usando el$\vdash$noción de probabilidad y el teorema de solidez.

El primer paso es probar que los axiomas de la forma$\forall x (S^n(x) \neq x)$y los axiomas$\forall x (0 \neq S(x))$y$\forall x \forall y (S(x) = S(y) \to x = y)$están en$Th(\mathbb{N}, 0, S)$. Esto es bastante sencillo.

La parte difícil es mostrar que los axiomas anteriores generan$Th(\mathbb{N}, 0, S)$. En otras palabras, debemos demostrar que todo enunciado verdadero sobre$\mathbb{N}$es demostrable a partir de los axiomas anteriores. No analizaré eso aquí a menos que se solicite, pero este es el paso crítico.

A continuación, mostramos que ningún subconjunto finito de los axiomas anteriores es suficiente para generar$Th(\mathbb{N})$. Esto implica considerar modelos de la forma$\mathbb{N} \cup C_{n + 1}$, dónde$C_{n + 1}$es un ciclo de longitud$n + 1$.

Finalmente, suponga que existe una lista finita$a_1, \ldots, a_n \in Th(\mathbb{N})$. Entonces cada uno$a_i$puede demostrarse a partir de un número finito de los axiomas anteriores y, por lo tanto, podemos tomar un subconjunto finito$Q$de los axiomas anteriores que implica todos los$a_i$. Pero como hemos mostrado arriba, hay algún elemento de$Th(\mathbb{N})$que no se sigue de$Q$y por lo tanto no se sigue de la$a_i$. Entonces$Th(\mathbb{N})$no es finitamente axiomatizable.