Aritmética de segundo orden

El lenguaje de la aritmética de segundo orden es de dos tipos . El primer tipo de términos , y en particular las variables , generalmente denotadas con letras minúsculas, consiste en individuos , cuya interpretación prevista es la de números naturales. El otro tipo de variables, denominadas indistintamente "variables de conjunto", "variables de clase" o incluso "predicados", generalmente se denotan con letras mayúsculas. Se refieren a clases/predicados/propiedades de los individuos, por lo que pueden considerarse conjuntos de números naturales. Tanto los individuos como las variables de conjunto pueden cuantificarse universal o existencialmente . Una fórmula sin variables de conjunto ligadas (es decir, sin cuantificadores sobre variables de conjunto) se denomina aritmética . Una fórmula aritmética puede tener variables de conjunto libres y variables individuales ligadas.

Los términos individuales se forman a partir de la constante 0, la función unaria S (la función sucesora ) y las operaciones binarias + y${\displaystyle \cdot }$(suma y multiplicación). La función sucesora suma 1 a su entrada. Las relaciones = (igualdad) y < (comparación de números naturales) relacionan dos individuos, mientras que la relación ∈ (pertenencia) relaciona un individuo con un conjunto (o clase). Así, en notación, el lenguaje de la aritmética de segundo orden viene dado por la signatura${\displaystyle {\mathcal {L}}=\{0,S,+,\cdot ,=,<,\in \}}$.

Por ejemplo,${\displaystyle \forall n(n\in X\rightarrow Sn\in X)}$, es una fórmula bien formada de aritmética de segundo orden que es aritmética, tiene una variable de conjunto libre X y una variable individual ligada n (pero no variables de conjunto ligadas, como se requiere de una fórmula aritmética) — mientras que${\displaystyle \exists X\forall n(n\in X\leftrightarrow n<SSSSSS0\cdot SSSSSSS0)}$es una fórmula bien formada que no es aritmética, que tiene una variable de conjunto acotada X y una variable individual acotada n .

Son posibles varias interpretaciones diferentes de los cuantificadores. Si se estudia la aritmética de segundo orden utilizando la semántica completa de la lógica de segundo orden, entonces los cuantificadores de conjunto abarcan todos los subconjuntos del rango de las variables individuales. Si la aritmética de segundo orden se formaliza utilizando la semántica de la lógica de primer orden ( semántica de Henkin ), entonces cualquier modelo incluye un dominio sobre el cual las variables de conjunto pueden abarcar, y este dominio puede ser un subconjunto propio del conjunto potencia completo del dominio de las variables individuales. ^{[ 3 ]}

La teoría formal de la aritmética de segundo orden (en el lenguaje de la aritmética de segundo orden) consta de los axiomas básicos, el axioma de comprensión para cada fórmula φ (aritmética o de otro tipo) y el axioma de inducción de segundo orden. Esta teoría a veces se denomina aritmética completa de segundo orden para distinguirla de sus subsistemas, definidos más adelante. Dado que la semántica completa de segundo orden implica que existe todo conjunto posible, los axiomas de comprensión pueden considerarse parte del sistema deductivo cuando se emplea la semántica completa de segundo orden. ^{[ 3 ]}

Las funciones de primer orden que son demostrablemente totales en la aritmética de segundo orden son precisamente las mismas que las representables en el sistema F. ^{[ 4 ]} Casi equivalentemente, el sistema F es la teoría de funcionales que corresponde a la aritmética de segundo orden de manera paralela a como el sistema T de Gödel corresponde a la aritmética de primer orden en la interpretación de la Dialectica .

Cuando un modelo del lenguaje de la aritmética de segundo orden tiene ciertas propiedades, también se le puede llamar con estos otros nombres:

• Cuando M es el conjunto usual de números naturales con sus operaciones usuales,${\displaystyle {\mathcal {M}}}$se denomina modelo ω . En este caso, el modelo puede identificarse con D , su colección de conjuntos de números naturales, porque este conjunto es suficiente para determinar completamente un modelo ω. El único completo${\displaystyle \omega }$El modelo -, que es el conjunto usual de números naturales con su estructura usual y todos sus subconjuntos, se denomina modelo previsto o estándar de la aritmética de segundo orden. ^{[ 5 ]}
• Un modelo${\displaystyle {\mathcal {M}}}$del lenguaje de la aritmética de segundo orden se llama modelo β si${\displaystyle {\mathcal {M}}\prec _{1}^{1}{\mathcal {P}}(\omega )}$, es decir, las sentencias Σ ¹ ₁ con parámetros de${\displaystyle {\mathcal {M}}}$que se satisfacen por${\displaystyle {\mathcal {M}}}$son las mismas que las que satisface el modelo completo. ^{[ 6 ]} Algunas nociones que son absolutas con respecto a los modelos β incluyen "${\displaystyle A\subseteq \omega \times \omega }$codifica un " bien ordenado " ^{[ 7 ]} y "${\displaystyle A\subseteq \omega \times \omega }$es un árbol ". ^{[ 6 ]}
• El resultado anterior se ha extendido al concepto de un modelo β _n para${\displaystyle n\in \mathbb {N} }$, que tiene la misma definición que la anterior excepto${\displaystyle \prec _{1}^{1}}$es reemplazado por${\displaystyle \prec _{n}^{1}}$, es decir${\displaystyle \Sigma _{1}^{1}}$es reemplazado por${\displaystyle \Sigma _{n}^{1}}$. ^{[ 6 ]} Usando esta definición, los modelos β ₀ son lo mismo que los modelos ω. ^{[ 8 ]}

Muchos de los subsistemas estudiados están relacionados con las propiedades de cierre de los modelos. Por ejemplo, se puede demostrar que todo ω-modelo de aritmética de segundo orden completa es cerrado bajo el salto de Turing , pero no todo ω-modelo cerrado bajo el salto de Turing es un modelo de aritmética de segundo orden completa. El subsistema ACA ₀ incluye los axiomas suficientes para capturar la noción de cierre bajo el salto de Turing.

ACA ₀ se define como la teoría que consta de los axiomas básicos, el esquema del axioma de comprensión aritmética (es decir, el axioma de comprensión para cada fórmula aritmética φ ) y el axioma de inducción de segundo orden ordinario. Sería equivalente incluir también todo el esquema del axioma de inducción aritmética, es decir, incluir el axioma de inducción para cada fórmula aritmética φ .

Se puede demostrar que una colección S de subconjuntos de ω determina un modelo ω de ACA ₀ si y solo si S es cerrada bajo el salto de Turing, la reducibilidad de Turing y la unión de Turing. ^{[ 10 ]}

El subíndice 0 en ACA ₀ indica que no todas las instancias del esquema del axioma de inducción se incluyen en este subsistema. Esto no supone ninguna diferencia para los modelos ω, que satisfacen automáticamente todas las instancias del axioma de inducción. Sin embargo, es importante en el estudio de los modelos que no son ω. El sistema que consiste en ACA ₀ más la inducción para todas las fórmulas se denomina a veces ACA sin subíndice.

El sistema ACA ₀ es una extensión conservadora de la aritmética de primer orden (o axiomas de Peano de primer orden), definida como los axiomas básicos, más el esquema de axiomas de inducción de primer orden (para todas las fórmulas φ que no involucran variables de clase, estén o no ligadas), en el lenguaje de la aritmética de primer orden (que no permite variables de clase en absoluto). En particular, tiene el mismo ordinal de teoría de la demostración ε ₀ que la aritmética de primer orden, debido al esquema de inducción limitado.

Una fórmula se denomina aritmética acotada , o Δ ⁰ ₀ , cuando todos sus cuantificadores son de la forma ∀ n < t o ∃ n < t (donde n es la variable individual que se cuantifica y t es un término individual), donde

${\displaystyle \forall n<t(\cdots )}$

representa

${\displaystyle \forall n(n<t\rightarrow \cdots )}$

y

${\displaystyle \exists n<t(\cdots )}$

representa

${\displaystyle \exists n(n<t\land \cdots )}$.

Una fórmula se llama Σ ⁰ ₁ (o a veces Σ ₁ ), respectivamente Π ⁰ ₁ (o a veces Π ₁ ) cuando tiene la forma ∃ mφ , respectivamente ∀ mφ donde φ es una fórmula aritmética acotada y m es una variable individual (que es libre en φ ). De manera más general, una fórmula se llama Σ ⁰ _n , respectivamente Π ⁰ _n cuando se obtiene al agregar cuantificadores individuales existenciales, respectivamente universales, a una fórmula Π ⁰ _{n − 1} , respectivamente Σ ⁰ _{n − 1} (y Σ ⁰ ₀ y Π ⁰ ₀ son ambos iguales a Δ ⁰ ₀ ). Por construcción, todas estas fórmulas son aritméticas (ninguna variable de clase está ligada) y, de hecho, al poner la fórmula en forma de prenexo de Skolem se puede ver que toda fórmula aritmética es lógicamente equivalente a una fórmula Σ ⁰ _n o Π ⁰ _n para todo n suficientemente grande .

El subsistema RCA ₀ es un sistema más débil que ACA ₀ y se usa a menudo como sistema base en matemáticas inversas . Consta de: los axiomas básicos, el esquema de inducción Σ ⁰ ₁ y el esquema de comprensión Δ ⁰ _1. El primer término es claro: el esquema de inducción Σ ⁰ ₁ es el axioma de inducción para cada fórmula Σ ⁰ ₁ φ . El término "comprensión Δ ⁰ ₁ " es más complejo, porque no existe tal cosa como una fórmula Δ ⁰ _{1. El esquema de comprensión Δ} ⁰ ₁ afirma, en cambio, el axioma de comprensión para cada fórmula Σ ⁰ ₁ que es lógicamente equivalente a una fórmula Π ⁰ _1. Este esquema incluye, para cada fórmula Σ ⁰ ₁ φ y cada fórmula Π ⁰ ₁ ψ , el axioma:

${\displaystyle \forall m\forall X((\forall n(\varphi (n)\leftrightarrow \psi (n)))\rightarrow \exists Z\forall n(n\in Z\leftrightarrow \varphi (n)))}$

El conjunto de consecuencias de primer orden de RCA ₀ es el mismo que el del subsistema I Σ ₁ de la aritmética de Peano en la que la inducción se restringe a fórmulas Σ ⁰ _1. A su vez, I Σ ₁ es conservador sobre la aritmética recursiva primitiva (PRA) para${\displaystyle \Pi _{2}^{0}}$oraciones. Además, el ordinal de la teoría de la demostración de${\displaystyle \mathrm {RCA} _{0}}$es ω ^ω , lo mismo que el de PRA.

Se observa que una colección S de subconjuntos de ω determina un modelo ω de RCA ₀ si y solo si S es cerrado bajo la reducibilidad de Turing y la unión de Turing. En particular, la colección de todos los subconjuntos computables de ω da lugar a un modelo ω de RCA _0. Esta es la razón del nombre de este sistema: si se puede demostrar la existencia de un conjunto utilizando RCA ₀ , entonces el conjunto es recursivo (es decir, computable).

A veces se desea un sistema aún más débil que RCA _0. Uno de esos sistemas se define de la siguiente manera: primero hay que aumentar el lenguaje de la aritmética con un símbolo de función exponencial (en sistemas más fuertes la exponencial se puede definir en términos de suma y multiplicación mediante el truco habitual, pero cuando el sistema se vuelve demasiado débil esto ya no es posible) y los axiomas básicos con los axiomas obvios que definen la exponenciación inductivamente a partir de la multiplicación; entonces el sistema consiste en los axiomas básicos (enriquecidos), más la comprensión Δ ⁰ ₁ , más la inducción Δ ⁰ ₀ .

Sobre ACA ₀ , cada fórmula de aritmética de segundo orden es equivalente a una fórmula Σ ¹ _n o Π ¹ _n para todo n suficientemente grande . El sistema Π ¹ ₁ -comprensión es el sistema que consta de los axiomas básicos, más el axioma de inducción de segundo orden ordinario y el axioma de comprensión para cada ( negrita ^{[ 11 ]} ) fórmula Π ¹ ₁ φ . Esto es equivalente a Σ ¹ ₁ -comprensión (por otro lado, Δ ¹ ₁ -comprensión, definida de forma análoga a Δ ⁰ ₁ -comprensión, es más débil).