Aritmética de segundo orden

En lógica matemática, la aritmética de segundo orden es una colección de sistemas axiomáticos que formalizan los números naturales y sus subconjuntos. Es una alternativa a la teoría de conjuntos axiomática como base para gran parte de las matemáticas, pero no para todas.

David Hilbert y Paul Bernays introdujeron un precursor de la aritmética de segundo orden que involucra parámetros de tercer orden en su libro Grundlagen der Mathematik. La axiomatización estándar de la aritmética de segundo orden se denota por Z₂.

La aritmética de segundo orden incluye, pero es significativamente más fuerte, su contraparte de primer orden, la aritmética de Peano. A diferencia de la aritmética de Peano, la aritmética de segundo orden permite la cuantificación de conjuntos de números naturales, así como de los números mismos. Debido a que los números reales se pueden representar como conjuntos (infinitos) de números naturales de formas bien conocidas, y debido a que la aritmética de segundo orden permite la cuantificación de tales conjuntos, es posible formalizar los números reales en aritmética de segundo orden. Por esta razón, a la aritmética de segundo orden a veces se le llama "análisis".

La aritmética de segundo orden también puede verse como una versión débil de la teoría de conjuntos en la que cada elemento es un número natural o un conjunto de números naturales. Aunque es mucho más débil que la teoría de conjuntos de Zermelo-Fraenkel, la aritmética de segundo orden puede demostrar esencialmente todos los resultados de las matemáticas clásicas expresables en su lenguaje.

Un subsistema de aritmética de segundo orden es una teoría en el lenguaje de la aritmética de segundo orden, cada axioma del cual es un teorema de la aritmética de segundo orden completo (Z₂). Estos subsistemas son esenciales para invertir las matemáticas, un programa de investigación que investiga qué parte de las matemáticas clásicas se puede derivar de ciertos subsistemas débiles de diferente potencia. Gran parte de las matemáticas básicas se pueden formalizar en estos subsistemas débiles, algunos de los cuales se definen a continuación. Las matemáticas inversas también aclaran hasta qué punto y de qué manera las matemáticas clásicas son no constructivas.

Definición

Sintaxis

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

Los términos individuales se forman a partir de la constante 0, la función no deseada S ( función sucesor), y las operaciones binarias + y ${\displaystyle \cdot }$ (addición y multiplicación). La función sucesora añade 1 a su entrada. Las relaciones = (igualdad) y (comparación de números naturales) se relacionan con dos individuos, mientras que la relación divisa (menorización) se relaciona con un individuo y un conjunto (o clase). Así en la notación el lenguaje de la aritmética de segundo orden es dado por la firma ${\displaystyle {\mathcal {}=\{0,S,+,\cdot=,traducido,\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 juego libre X y una variable individual fija n (pero no hay variables fijas, como se requiere de una fórmula aritmética)—como ${\displaystyle \exists X\forall n(n\in X\leftrightarrow n madeSS0\cdot SSSSS0)}$ es una fórmula bien formada que no es aritmética, teniendo una variable de conjunto atado X y una variable individual fija n.

Semántica

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 conjuntos 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 en el que oscilan las variables del conjunto, y este dominio puede ser un subconjunto adecuado del conjunto de poderes completo del dominio de variables individuales. variables.

Axiomas

Básico

Los siguientes axiomas son conocidos como axiomas básicos, o a veces Axiomas Robinson. La teoría resultante de primer orden, conocida como Robinson aritmética, es esencialmente peano aritmético sin inducción. El dominio del discurso para las variables cuantificadas es el número natural, denotado colectivamente por N, e incluyendo al distinguido miembro ${\displaystyle 0}$, llamado "cero".

Las funciones primitivas son la única función sucesor, denotada por prefijo ${\displaystyle S.$, y dos operaciones binarias, adición y multiplicación, denotado por el operador de infix "+" y "${\displaystyle \cdot }$", respectivamente. También hay una relación binaria primitiva llamada orden, denotada por el operador del infijo "tratado".

Axiomas que rigen la función sucesora y el cero:

1. ${\displaystyle \forall m[Sm=0\rightarrow \bot].}$ ("el sucesor de un número natural nunca es cero")

2. ${\displaystyle \forall m\forall n[Sm=Sn\rightarrow m=n].}$ ("la función sucesor es inyectable")

3. ${\displaystyle \forall n[0=n\lor \exists m[Sm=n].}$ ("todo número natural es cero o un sucesor")

Suma definida recursivamente:

4. ${\displaystyle \forall m[m+0=m].}$

5. ${\displaystyle \forall m\forall n[m+Sn=S(m+n)].}$

Multiplicación definida recursivamente:

6. ${\displaystyle \forall m[m\cdot 0=0].}$

7. ${\displaystyle \forall m\forall n[m\cdot Sn=(m\cdot n)+m].}$

Axiomas que gobiernan la relación orden "seguido":

8. ${\displaystyle \forall m[miere0\rightarrow\bot].}$ ("ningún número natural es menor que cero")

9. ${\displaystyle \forall n\forall m[m madeSn\leftrightarrow (m maden\lor m=n)].}$

10. ${\displaystyle \forall n[0=n\lor 0 obtenidos].}$ ("todo número natural es cero o más grande que cero")

11. ${\displaystyle \forall m\forall n[(Sm maden\lor Sm=n)\leftrightarrow m maden].}$

Estos axiomas son todas declaraciones de primera orden. Es decir, todas las variables varían sobre los números naturales y no los establece, un hecho aún más fuerte que su ser aritmética. Además, sólo hay un cuantificador existencial, en Axiom 3. Axioms 1 y 2, junto con un esquema de inducción axioma conforman la definición habitual de Peano-Dedekind N. Añadir a estos axiomas cualquier tipo de esquema de inducción del axioma hace redundante los axiomas 3, 10 y 11.

Esquema de inducción y comprensión

Si φ(n) es una fórmula de aritmética de segundo orden con una variable individual libre n y posiblemente otro individuo o conjunto libre variables (escrito m₁,...,m_k y X₁,...,X_l), el axioma de inducción para φ es el axioma:

${\displaystyle \forall m_{1}\dots m_{k}\forall X_{1}\dots X_{l}(\varphi (0)\land \forall n(\varphi (n)\rightarrow \varphi (Sn)))\rightarrow \forall n\varphi (n)}}}$

El (completo) esquema de inducción de segundo orden consta de todos los casos de este axioma, sobre todas las fórmulas de segundo orden.

Un caso particularmente importante del plan de inducción es cuando φ es la fórmula "${\displaystyle n\in X}$" expresando el hecho de que n es miembro de X ()X ser una variable de juego libre: en este caso, el axioma de inducción para φ es

${\displaystyle \forall X(0\in X\land \forall n(n\in X\rightarrow Sn\in X)\rightarrow \forall n(n\in X)}$

Esta oración se llama axioma de inducción de segundo orden.

Si φ(n) es una fórmula con una variable libre n y posiblemente otras variables libres, pero no la variable Z, el axioma de comprensión para φ es la fórmula

${\displaystyle \exists Z\forall n(n\in Z\leftrightarrow \varphi (n)}$

Este axioma hace posible formar el conjunto ${\displaystyle Z=\{n detained\varphi (n)}}$ de números naturales satisfactorios φ()n). Hay una restricción técnica que la fórmula φ puede no contener la variable Z, por lo contrario la fórmula ${\displaystyle n\not \in Z}$ conduciría a la comprensión del axioma

${\displaystyle \exists Z\forall n(n\in Z\leftrightarrow n\not \in Z)}$,

lo cual es inconsistente. Esta convención se asume en el resto de este artículo.

El sistema completo

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 no), 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, que se definen a continuación. Debido a 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.

Modelos

Esta sección describe aritmética de segundo orden con semántica de primer orden. Así como modelo ${\displaystyle {\fnMithcal}}$ de la lengua de la aritmética de segundo orden consiste en un conjunto M (que forma el rango de variables individuales) junto con un elemento de 0 constante M), una función S desde M a M, dos operaciones binarias + y · en M, una relación binaria M, y una colección D of subsets of M, que es el rango de las variables establecidas. Omitting D produce un modelo del lenguaje de la aritmética de primer orden.

Cuando D es la potencia completa de M, el modelo ${\displaystyle {\fnMithcal}}$ se llama modelo completo. El uso de semántica de segundo orden es equivalente a limitar los modelos de aritmética de segundo orden a los modelos completos. De hecho, los axiomas de la aritmética de segundo orden tienen sólo un modelo completo. Esto se deriva del hecho de que los axiomas Peano con el axioma de inducción de segundo orden tienen sólo un modelo bajo semántica de segundo orden.

Funciones definibles

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. Casi de manera equivalente, el sistema F es la teoría de funcionales correspondiente a la aritmética de segundo orden de una manera paralela a cómo El sistema T de Gödel corresponde a la aritmética de primer orden en la interpretación de Dialectica.

Más tipos de modelos

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 habitual de números naturales con sus operaciones habituales, ${\displaystyle {\fnMithcal}}$ se llama ω-model. En este caso, el modelo puede ser identificado con D, su colección de conjuntos de naturales, porque este conjunto es suficiente para determinar completamente un modelo ω. El único completo ${\displaystyle \omega }$-model, que es el conjunto habitual de números naturales con su estructura habitual y todos sus subconjuntos, se llama el para fines previstos o estándar modelo de segunda orden aritmética.
• Un modelo ${\displaystyle {\fnMithcal}}$ de la lengua de la aritmética de segundo orden se llama a β-model si ${\displaystyle {\fnMitcal}\prec} ¿Por qué?$, es decir, los estados de la ev11 con parámetros ${\displaystyle {\fnMithcal}}$ que están satisfechos ${\displaystyle {\fnMithcal}}$ son los mismos que los satisfechos por el modelo completo. Algunas nociones que son absolutas con respecto a los modelos β incluyen "${\displaystyle A\subseteq \omega \times \omega }$ codifica un bien ordenado y "${\displaystyle A\subseteq \omega \times \omega }$ es un árbol".
• El resultado mencionado se ha ampliado al concepto de un β_n-modelo para ${\displaystyle n\in \mathbb {N}$, que tiene la misma definición que la anterior ${\displaystyle \prec ¿Qué?$ es reemplazado por ${\displaystyle \prec _{n} {1}}$, es decir. ${\displaystyle \Sigma ¿Qué?$ es reemplazado por ${\displaystyle \Sigma _{n} {1}}$. Usando esta definición β₀- Los modelos son los mismos que los modelos ω.

Subsistemas

Hay muchos subsistemas de aritmética de segundo orden con nombre.

Un subíndice 0 en el nombre de un subsistema indica que incluye sólo una porción restringida del esquema completo de inducción de segundo orden. Tal restricción reduce significativamente la fuerza de la teoría de prueba del sistema. Por ejemplo, el sistema ACA₀ que se describe a continuación es equiconsistente con la aritmética de Peano. La teoría correspondiente ACA, que consta de ACA₀ más el esquema de inducción de segundo orden completo, es más sólida que la aritmética de Peano.

Comprensión aritmética

Muchos de los subsistemas bien estudiados están relacionados con las propiedades de cierre de los modelos. Por ejemplo, se puede demostrar que todo modelo ω de aritmética completa de segundo orden está cerrado bajo el salto de Turing, pero no todo modelo ω cerrado bajo el salto de Turing es un modelo de aritmética completa de segundo orden. El subsistema ACA₀ incluye suficientes axiomas 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 (en otras palabras, el axioma de comprensión para cada axioma de comprensión). i> fórmula φ) y el axioma de inducción ordinario de segundo orden. 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 sólo si S es cerrado bajo el salto de Turing, la reducibilidad de Turing y la unión de Turing.

El subíndice 0 en ACA₀ indica que no todas las instancias del esquema del axioma de inducción están incluidas en este subsistema. Esto no supone ninguna diferencia para los modelos ω, que satisfacen automáticamente todos los casos del axioma de inducción. Sin embargo, es importante en el estudio de modelos que no son ω. El sistema que consta de ACA₀ más inducción para todas las fórmulas a veces se denomina 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 los axiomas de primer orden. esquema de axioma de inducción (para todas las fórmulas φ que no involucran ninguna variable de clase, ligada o no), en el lenguaje de la aritmética de primer orden (que no permite ninguna variable de clase). En particular, tiene el mismo ordinal de teoría de prueba ε0 que la aritmética de primer orden, debido al esquema de inducción limitado.

La jerarquía aritmética de las fórmulas

Una fórmula se llama aritmética acotada, o Δ⁰₀, cuando todas sus Los cuantificadores tienen la forma ∀n<t o ∃n<t (donde n es la variable individual que se está cuantificando y t es un término individual), donde

${\displaystyle \forall n wont(\cdots)}$

significa

${\displaystyle \forall n(n interpretadot\rightarrow \cdots)}$

y

${\displaystyle \exists n made(\cdots)}$

significa

${\displaystyle \exists n(n made\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 Π^{0< /sup>_n cuando se obtiene sumando cuantificadores individuales existenciales, respectivamente universales, a un Π0< /sup>_n−1, respectivamente Σ0_n−1 fórmula (y Σ0₀ y Π0₀ son ambos iguales a Δ0₀). Por construcción, todas estas fórmulas son aritméticas (nunca se vinculan variables de clase) y, de hecho, al poner la fórmula en forma de prenexo de Skolem se puede ver que cada fórmula aritmética es lógicamente equivalente a Σ0 _n o Π0 _{Fórmula n} para todos los n suficientemente grandes.}

Comprensión recursiva

El subsistema RCA₀ es un sistema más débil que ACA₀ y se utiliza 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. El primer término es claro: el esquema de inducción Σ⁰₁ es el axioma de inducción para todo Σ^{0₁ fórmula φ. El término "Δ0₁ comprensión" es más complejo, porque no existe una fórmula Δ0₁. En cambio, el esquema de comprensión Δ0₁ afirma el axioma de comprensión para cada estilo Σ0₁ fórmula que es lógicamente equivalente a Π0₁ fórmula. Este esquema incluye, para cada Σ0₁ la fórmula φ y cada Π0 ₁ 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))}$

The set of first-order consequences of RCA₀ es el mismo que los del subsistema Ieva₁ de Peano aritmética en la que la inducción se restringe a la⁰₁ fórmulas. A su vez, I Elisabeth₁ es conservador sobre aritmética recursiva primitiva (PRA) para ${\displaystyle \Pi _{2} {0}}$ oraciones. Además, el ordinal de prueba-teorético ${\displaystyle \mathrm {RCA} _{0}$ es ⋅^⋅Lo mismo que el del PRA.

Se puede ver que una colección S de subconjuntos de ω determina un modelo ω de RCA₀ si y sólo 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 un modelo ω de RCA₀. Esta es la motivación detrás del nombre de este sistema: si se puede demostrar que existe un conjunto usando RCA₀, entonces el conjunto es recursivo (es decir, computable).

Sistemas más débiles

A veces se desea un sistema aún más débil que RCA₀. 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 es ya no es posible) y los axiomas básicos por los axiomas obvios que definen la exponenciación inductivamente a partir de la multiplicación; entonces el sistema consta de los axiomas básicos (enriquecidos), más Δ⁰₁ comprensión, más Δ^{0< /sup>₀ inducción.}

Sistemas más fuertes

Sobre ACA₀, cada fórmula de aritmética de segundo orden es equivalente a un Σ¹_n o Π¹_n fórmula para todos los grandes suficiente n. El sistema Π¹₁-comprensión es el sistema que consta de los axiomas básicos, más los axioma de inducción ordinario de segundo orden y el axioma de comprensión para cada (negrita) Π¹₁ fórmula φ. Esto equivale a Σ¹₁-comprensión (por otro lado, Δ¹< sub style="margin-left:-0.6em">1-comprensión, definida de manera análoga a Δ⁰_{1-comprensión, es más débil).}

Determinación proyectiva

La determinación proyectiva es la afirmación de que cada juego de información perfecta de dos jugadores con movimientos que son números naturales, duración del juego ω y conjunto de pagos proyectivos está determinado, es decir, uno de los jugadores tiene una estrategia ganadora. (El primer jugador gana el juego si la jugada pertenece al conjunto de pagos; en caso contrario, gana el segundo jugador). Un conjunto es proyectivo si y sólo si (como predicado) es expresable mediante una fórmula en el lenguaje de segundo orden. aritmética, permitiendo números reales como parámetros, por lo que la determinación proyectiva se puede expresar como un esquema en el lenguaje de Z₂.

Muchas proposiciones naturales expresables en el lenguaje de la aritmética de segundo orden son independientes de Z₂ e incluso ZFC, pero son provables de la determinación proyectiva. Ejemplos incluyen propiedad de subconjunto perfecto coanalítica, mensurabilidad y propiedad de Baire para ${\displaystyle \Sigma ¿Qué?$ Sets, ${\displaystyle \Pi _{3} {1}}$ uniformización, etc. Sobre una teoría base débil (como RCA)₀), determinación proyectiva implica comprensión y proporciona una teoría esencialmente completa de las declaraciones aritméticas de segundo orden — naturales en el lenguaje de Z₂ que son independientes de Z₂ con determinación proyectiva son difíciles de encontrar.

ZFC + {hay n cardinales de Woodin: n es un número natural} es conservador sobre Z₂ con determinación proyectiva, es decir un enunciado en el lenguaje de la aritmética de segundo orden es demostrable en Z₂ con determinación proyectiva si y sólo si su traducción al lenguaje de la teoría de conjuntos es demostrable en ZFC + {hay n Cardenales Woodin: n∈N}.

Codificación matemática

La aritmética de segundo orden formaliza directamente los números naturales y los conjuntos de números naturales. Sin embargo, es capaz de formalizar otros objetos matemáticos indirectamente mediante técnicas de codificación, un hecho que fue observado por primera vez por Weyl. Los números enteros, racionales y reales se pueden formalizar en el subsistema RCA₀, junto con espacios métricos separables completos y funciones continuas entre ellos.

El programa de investigación de matemáticas inversas utiliza estas formalizaciones de las matemáticas en aritmética de segundo orden para estudiar los axiomas de existencia de conjuntos necesarios para demostrar teoremas matemáticos. Por ejemplo, el teorema del valor intermedio para funciones de reales a reales se puede demostrar en RCA₀, mientras que el teorema de Bolzano-Weierstrass es equivalente a ACA₀ sobre RCA₀.

La codificación antes mencionada funciona bien para funciones continuas y totales, asumiendo una teoría base de orden superior más un lema de Kőnig débil. Como quizás se esperaba, en el caso de la topología, la codificación no está exenta de problemas.