Aritmética de segundo orden - Second-order arithmetic

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 axiomática de conjuntos como base para gran parte de las matemáticas, pero no para todas.

Un precursor de la aritmética de segundo orden que involucra parámetros de tercer orden fue introducido por David Hilbert y Paul Bernays 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 sólida que 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 propios números. 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 sobre tales conjuntos, es posible formalizar los números reales en aritmética de segundo orden. Por esta razón, la aritmética de segundo orden a veces se denomina " análisis " (Sieg 2013, p. 291).

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 probar esencialmente que todos los resultados de la matemática clásica se pueden expresar 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 completa (Z ₂ ). Dichos subsistemas son esenciales para la matemática inversa , un programa de investigación que investiga cuánta matemática clásica se puede derivar en ciertos subsistemas débiles de diversa fuerza. 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. La matemática inversa también aclara el alcance y la manera en que la matemática clásica es no constructiva .

Definición

Sintaxis

El lenguaje de la aritmética de segundo orden se clasifica en dos . El primer tipo de términos y, en particular , las variables , generalmente denotadas con letras minúsculas, consta de individuos , cuya interpretación prevista es como números naturales. El otro tipo de variables, denominadas de forma diversa "variables de conjunto", "variables de clase" o incluso "predicados", generalmente se indican con letras mayúsculas. Se refieren a clases / predicados / propiedades de los individuos, por lo que pueden considerarse como 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 limitadas (es decir, sin cuantificadores sobre variables de conjunto) 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 unaria S (la función sucesora ) y las operaciones binarias + y (suma y multiplicación). La función sucesora agrega 1 a su entrada. Las relaciones = (igualdad) y <(comparación de números naturales) relacionan a dos individuos, mientras que la relación ∈ (pertenencia) relaciona a un individuo y un conjunto (o clase). Así, en la notación, el lenguaje de la aritmética de segundo orden viene dado por la firma . ${\ Displaystyle \ cdot}$${\ Displaystyle {\ mathcal {L}} = \ {0, S, +, \ cdot, =, <, \ in \}}$

Por ejemplo, , es una fórmula bien formada de la aritmética de segundo orden que es aritmética, tiene una variable conjunto libre X y uno variable individual unido n (pero no hay variables de set consolidados, como se requiere de una fórmula aritmética) -Considerando que es una fórmula bien formada que no es aritmética, que tiene una variable de conjunto de límites X y una variable individual de límite n . ${\ Displaystyle \ forall n (n \ in X \ rightarrow Sn \ in X)}$${\ Displaystyle \ existe X \ forall n (n \ in X \ leftrightarrow n <SSSSSS0 \ cdot SSSSSSS0)}$

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 establecidos abarcan todos los subconjuntos del rango de las variables numéricas. 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 para que el conjunto de variables se extienda, y este dominio puede ser un subconjunto adecuado del conjunto de potencias completo del dominio de números. variables (Shapiro 1991, págs. 74-75).

Axiomas

Básico

Los siguientes axiomas se conocen como axiomas básicos o, a veces, axiomas de Robinson. La teoría de primer orden resultante , conocida como aritmética de Robinson , es esencialmente aritmética de Peano sin inducción. El dominio del discurso para las variables cuantificadas son los números naturales , denotados colectivamente por N , e incluyendo el miembro distinguido , llamado " cero ". ${\ Displaystyle \ 0}$

Las funciones primitivas son la función sucesora unaria , indicada por prefijo , y dos operaciones binarias , suma y multiplicación , indicadas por infijo "+" y " ", respectivamente. También hay una relación binaria primitiva llamada orden , denotada por el infijo "<". ${\ Displaystyle S}$${\ Displaystyle \ cdot}$

Axiomas que gobiernan la función sucesora y cero :

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

2. ("la función sucesora es inyectiva ")${\ Displaystyle \ forall m \ forall n [Sm = Sn \ rightarrow m = n].}$

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

Suma definida de forma recursiva :

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

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

Multiplicación definida de forma recursiva:

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 de orden "<":

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

9. ${\ Displaystyle \ forall n \ forall m [m <Sn \ leftrightarrow (m <n \ lor m = n)].}$

10. ("todo número natural es cero o mayor que cero")${\ Displaystyle \ forall n [0 = n \ lor 0 <n].}$

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

Estos axiomas son todos enunciados de primer orden . Es decir, todas las variables oscilan sobre los números naturales y no los conjuntos de los mismos, un hecho incluso más fuerte que su aritmética. Además, sólo hay un cuantificador existencial , en el axioma 3. Los axiomas 1 y 2, junto con un esquema de axioma de inducción, conforman la definición habitual de N de Peano-Dedekind . Agregar a estos axiomas cualquier tipo de esquema de axiomas de inducción hace redundantes 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 de número libre n y posible otro número libre o variables de conjunto (escritas m _• y X _• ), el axioma de inducción para φ es el axioma:

${\ Displaystyle \ forall m \ forall X ((\ varphi (0) \ land \ forall n (\ varphi (n) \ rightarrow \ varphi (Sn))) \ rightarrow \ forall n \ varphi (n))}$

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

Un caso particularmente importante del esquema de inducción es cuando φ es la fórmula " " que expresa el hecho de que n es un miembro de X ( siendo X una variable de conjunto libre): en este caso, el axioma de inducción para φ es ${\ Displaystyle n \ in X}$

${\ 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 \ existe Z \ forall n (n \ in Z \ leftrightarrow \ varphi (n))}$

Este axioma permite formar el conjunto de números naturales que satisfacen φ ( n ). Existe una restricción técnica de que la fórmula φ no puede contener la variable Z , ya que de lo contrario la fórmula conduciría al axioma de comprensión ${\ Displaystyle Z = \ {n | \ varphi (n) \}}$${\ Displaystyle n \ not \ in Z}$

${\ Displaystyle \ existe Z \ forall n (n \ in Z \ leftrightarrow n \ not \ in Z)}$,

que 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) consiste en 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, 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 tomarse como parte del sistema deductivo cuando se emplean estas semánticas (Shapiro 1991, p. 66).

Modelos

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

Cuando D es el conjunto de potencias completo de M , el modelo se denomina modelo completo . El uso de semántica de segundo orden completa equivale 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 solo un modelo completo. Esto se sigue del hecho de que los axiomas de la aritmética de Peano con el axioma de inducción de segundo orden tienen solo un modelo bajo la semántica de segundo orden. ${\ Displaystyle {\ mathcal {M}}}$

Cuando M es el conjunto habitual de números naturales con sus operaciones habituales, se denomina modelo ω . En este caso, el modelo puede identificarse con D , su colección de conjuntos de naturales, porque este conjunto es suficiente para determinar completamente un modelo ω. ${\ Displaystyle {\ mathcal {M}}}$

El modelo completo único , que es el conjunto habitual de números naturales con su estructura habitual y todos sus subconjuntos, se denomina modelo estándar o previsto de aritmética de segundo orden. ${\ Displaystyle \ omega}$

Funciones definibles

Las funciones de primer orden que son probables totales en aritmética de segundo orden son precisamente las mismas que las representables en el sistema F (Girard y Taylor 1987, pp. 122-123). Casi de manera equivalente, el sistema F es la teoría de los funcionales correspondientes 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 .

Subsistemas

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

Un subíndice 0 en el nombre de un subsistema indica que incluye sólo una parte restringida del esquema de inducción de segundo orden completo (Friedman 1976). Tal restricción reduce significativamente la fuerza de la teoría de la prueba del sistema. Por ejemplo, el sistema ACA _{0 que se} describe a continuación es equivalente a 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 fuerte 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 de axiomas de comprensión aritmética (en otras palabras, 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 todo el esquema del axioma de inducción aritmético, 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 está cerrado bajo el salto de Turing, la reducibilidad de Turing y la unión de Turing (Simpson 2009, págs. 311–313).

El subíndice 0 en ACA ₀ indica que no todas las instancias del esquema de axioma de inducción están incluidas en este subsistema. Esto no hace 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 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), definidos 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 en absoluto, con límites o de lo contrario), 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 la teoría de la demostración ε ₀ que la aritmética de primer orden, debido al esquema de inducción limitado.

La jerarquía aritmética de fórmulas

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

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

representa

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

y

${\ Displaystyle \ existe n <t (\ cdots)}$

representa

${\ Displaystyle \ existe n (n <t \ land \ cdots)}$.

Una fórmula se llama Σ ⁰ ₁ (oa veces Σ ₁ ), respectivamente Π ⁰ ₁ (oa 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 agregando cuantificadores individuales existenciales, respectivamente universales, a una fórmula Π ⁰ _{n −1} , respectivamente Σ ⁰ _{n −1} (y Σ ⁰ ₀ y Π ⁰ ₀ son todos equivalentes a Δ ⁰ ₀ ). Por construcción, todas estas fórmulas son aritméticas (ninguna variable de clase está ligada nunca) y, de hecho, al poner la fórmula en forma Skolem prenex, se puede ver que cada fórmula aritmética es equivalente a una fórmula Σ ⁰ _n o Π ⁰ _n para todas lo suficientemente grande n .

Comprensión recursiva

El subsistema RCA ₀ es un sistema más débil que el ACA ₀ y se utiliza a menudo como sistema base en matemáticas inversas . Consiste en: 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 de Σ ⁰ ₁ es el axioma de inducción para cada fórmula de Σ ⁰ ₁ φ. El término “ comprensión Δ ⁰ ₁ ” es más complejo, porque no existe una fórmula Δ ⁰ ₁ . El esquema de comprensión Δ ⁰ _{1 en} cambio afirma el axioma de comprensión para cada fórmula Σ ⁰ ₁ que es equivalente a una fórmula Π ⁰ ₁ . 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 \ existe 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 el que la inducción se restringe a Σ ⁰ ₁ fórmulas. A su vez, IΣ ₁ es conservador sobre aritmética recursiva primitiva (PRA) para oraciones. Además, el ordinal de la teoría de la demostración es ω ^ω , el mismo que el de PRA. ${\ Displaystyle \ Pi _ {2} ^ {0}}$${\ Displaystyle \ mathrm {RCA} _ {0}}$

Puede verse que una colección S de subconjuntos de ω determina un modelo ω de RCA ₀ si y solo si S está 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 ₀ . Ésta es la motivación detrás del nombre de este sistema: si se puede probar 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 el RCA ₀ . Uno de estos sistemas se define de la siguiente manera: primero se debe aumentar el lenguaje de la aritmética con una función exponencial (en sistemas más fuertes, el 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 no es posible). ya sea 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 inducción Δ ⁰ ₀ .

Sistemas más fuertes

Sobre ACA ₀ , cada fórmula de aritmética de segundo orden es equivalente a una fórmula Σ ¹ _n o Π ¹ _n para todos los n suficientemente grandes . El sistema Π ¹ ₁ -comprensión es el sistema que consta de los axiomas básicos, más el axioma ordinario de inducción de segundo orden y el axioma de comprensión para cada Π ¹ ₁ fórmula φ. Esto es equivalente a Σ ¹ ₁ -comprensión (por otro lado, Δ ¹ ₁ -comprensión, definida análogamente a Δ ⁰ ₁ -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 enteros, la duración del juego ω y el conjunto de pagos proyectivos están determinados, es decir, uno de los jugadores tiene una estrategia ganadora. (El primer jugador gana el juego si el juego pertenece al conjunto de pagos; de lo contrario, el segundo jugador gana.) Un conjunto es proyectivo sif (como predicado) se puede expresar mediante una fórmula en el lenguaje de la aritmética de segundo orden, lo que permite 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 que se pueden expresar en el lenguaje de la aritmética de segundo orden son independientes de Z ₂ e incluso de ZFC, pero se pueden demostrar a partir de la determinación proyectiva. Los ejemplos incluyen la propiedad coanalítica de subconjuntos perfectos , la mensurabilidad y la propiedad de Baire para conjuntos, uniformización , etc. Sobre una teoría de base débil (como RCA ₀ ), la determinación proyectiva implica comprensión y proporciona una teoría esencialmente completa de aritmética de segundo orden: enunciados naturales en el lenguaje de Z ₂ que son independientes de Z ₂ con determinación proyectiva son difíciles de encontrar (Woodin 2001). ${\ Displaystyle \ Sigma _ {2} ^ {1}}$${\ Displaystyle \ Pi _ {3} ^ {1}}$

ZFC + {hay n cardenales 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 sif su traducción al lenguaje de la teoría de conjuntos se puede demostrar en ZFC + {hay n cardenales Woodin: n ∈N}.

Codificar las matemáticas

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

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 (Simpson 2009, p. 32). Por ejemplo, el teorema del valor intermedio para funciones de reales a reales se puede demostrar en RCA ₀ (Simpson 2009, p. 87), mientras que el teorema de Bolzano - Weierstrass es equivalente a ACA ₀ sobre RCA ₀ (Simpson 2009, p. 34 ).

La codificación antes mencionada funciona bien para funciones continuas y totales, como se muestra en (Kohlenbach 2002, Sección 4), asumiendo una teoría de base de orden superior más el lema de Koenig débil . Como quizás se esperaba, en el caso de la topología o la teoría de medidas, la codificación no está exenta de problemas, como se explora en, por ejemplo, (Hunter, 2008) o (Normann-Sanders, 2019). Sin embargo, incluso la codificación de funciones integrables de Riemann conduce a problemas: como se muestra en (Normann-Sanders, 2020), los axiomas mínimos (de comprensión) necesarios para probar el teorema de convergencia de Arzelà para la integral de Riemann son * muy * diferentes dependiendo de si se usa segundo- códigos de pedido o funciones de tercer orden.

Ver también

• Teorema de París-Harrington
• Aritmética de Presburger
• Verdadera aritmética

Referencias

• Burgess, JP (2005), Fixing Frege , Princeton University Press.
• Buss, SR (1998), Manual de teoría de la prueba , Elsevier. ISBN  0-444-89840-9
• Friedman, H. (1976), "Sistemas de aritmética de segundo orden con inducción restringida", I, II (Resúmenes). Journal of Symbolic Logic , v. 41, págs. 557–559. JStor
• Girard, L. y Taylor (1987), Pruebas y tipos , Cambridge University Press.
• Hilbert, D. y Bernays, P. (1934), Grundlagen der Mathematik , Springer-Verlag. Señor 0237246
• Hunter, James, Topología inversa de orden superior , Disertación, Universidad de Madison-Wisconsin [1] .
• Kohlenbach, U. , Usos matemáticos y fundacionales de tipos superiores , Reflexiones sobre los fundamentos de las matemáticas, Lect. Notes Log., Vol. 15, ASL, 2002, págs. 92-116.
• Dag Normann y Sam Sanders, Representaciones en la teoría de la medida , arXiv: 1902.02756 , (2019).
• Dag Normann y Sam Sanders, Sobre la incontables $ \ mathbb {R} $ , arxiv: [2] , (2020), págs. 37.
• Sieg, W. (2013), Programas y más allá de Hilbert , Oxford University Press.
• Shapiro, S. (1991), Fundaciones sin fundacionalismo , Oxford University Press. ISBN  0-19-825029-0
• Simpson, SG (2009), Subsystems of second order arithmetic , 2nd edition, Perspectives in Logic, Cambridge University Press. ISBN  978-0-521-88439-6 MR 2517689
• Takeuti, G. (1975) Teoría de la prueba ISBN  0-444-10492-5
• Woodin, WH (2001), "The Continuum Hypothesis, Part I", Notices of the American Mathematical Society , v. 48 n. 6.