Matemáticas inversas

Rama de la lógica matemática

La matemática inversa es un programa de lógica matemática que busca determinar qué axiomas son necesarios para demostrar teoremas matemáticos. Su método de definición puede describirse brevemente como "ir hacia atrás desde los teoremas a los axiomas ", en contraste con la práctica matemática ordinaria de derivar teoremas a partir de axiomas. Puede conceptualizarse como la creación de condiciones necesarias a partir de condiciones suficientes .

El programa de matemáticas inversas fue prefigurado por los resultados de la teoría de conjuntos, como el teorema clásico de que el axioma de elección y el lema de Zorn son equivalentes en la teoría de conjuntos ZF . Sin embargo, el objetivo de las matemáticas inversas es estudiar los axiomas posibles de los teoremas matemáticos ordinarios en lugar de los axiomas posibles para la teoría de conjuntos.

Las matemáticas inversas se llevan a cabo generalmente utilizando subsistemas de aritmética de segundo orden , ^[1] donde muchas de sus definiciones y métodos están inspirados en trabajos previos en análisis constructivo y teoría de la prueba . El uso de la aritmética de segundo orden también permite emplear muchas técnicas de la teoría de la recursión ; muchos resultados en matemáticas inversas tienen resultados correspondientes en análisis computable . En matemáticas inversas de orden superior , el enfoque se centra en los subsistemas de aritmética de orden superior y el lenguaje asociado más rico. ^{[ aclaración necesaria ]}

El programa fue fundado por Harvey Friedman  (1975, 1976) ^[2] y presentado por Steve Simpson . Una referencia estándar para el tema es Simpson (2009), mientras que una introducción para los no especialistas es Stillwell (2018). Una introducción a las matemáticas inversas de orden superior, y también el artículo fundador, es Kohlenbach (2005). Una introducción completa, que cubre los principales resultados y métodos, es Dzhafarov y Mummert (2022) ^[3]. harvtxt error: no target: CITEREFDzhafarov_and_Mummert2022 (help)

Principios generales

En las matemáticas inversas, se parte de un lenguaje marco y una teoría base (un sistema de axiomas central) que es demasiado débil para demostrar la mayoría de los teoremas que pueden interesarnos, pero lo suficientemente potente como para desarrollar las definiciones necesarias para enunciar esos teoremas. Por ejemplo, para estudiar el teorema “Toda sucesión acotada de números reales tiene un supremo ”, es necesario utilizar un sistema base que pueda hablar de números reales y sucesiones de números reales.

Para cada teorema que se puede enunciar en el sistema base pero no es demostrable en el sistema base, el objetivo es determinar el sistema axiomático particular (más fuerte que el sistema base) que es necesario para demostrar ese teorema. Para demostrar que se requiere un sistema S para demostrar un teorema T , se requieren dos pruebas. La primera prueba muestra que T es demostrable a partir de S ; esta es una prueba matemática ordinaria junto con una justificación de que se puede llevar a cabo en el sistema S . La segunda prueba, conocida como inversión , muestra que T en sí implica S ; esta prueba se lleva a cabo en el sistema base. ^[1] La inversión establece que ningún sistema axiomático S′ que extienda el sistema base puede ser más débil que S y al mismo tiempo demostrar  T .

Uso de la aritmética de segundo orden

La mayor parte de la investigación en matemáticas inversas se centra en los subsistemas de la aritmética de segundo orden . El conjunto de investigaciones en matemáticas inversas ha establecido que los subsistemas débiles de la aritmética de segundo orden son suficientes para formalizar casi todas las matemáticas de nivel universitario. En la aritmética de segundo orden, todos los objetos pueden representarse como números naturales o conjuntos de números naturales. Por ejemplo, para demostrar teoremas sobre números reales, los números reales pueden representarse como sucesiones de Cauchy de números racionales , cada una de las cuales puede representarse como un conjunto de números naturales.

Los sistemas axiomáticos que se consideran con más frecuencia en matemáticas inversas se definen mediante esquemas axiomáticos denominados esquemas de comprensión . Dichos esquemas establecen que existe cualquier conjunto de números naturales definibles mediante una fórmula de una complejidad dada. En este contexto, la complejidad de las fórmulas se mide utilizando la jerarquía aritmética y la jerarquía analítica .

La razón por la que no se realizan matemáticas inversas utilizando la teoría de conjuntos como sistema base es que el lenguaje de la teoría de conjuntos es demasiado expresivo. Los conjuntos extremadamente complejos de números naturales se pueden definir mediante fórmulas simples en el lenguaje de la teoría de conjuntos (que pueden cuantificar sobre conjuntos arbitrarios). En el contexto de la aritmética de segundo orden, resultados como el teorema de Post establecen un vínculo estrecho entre la complejidad de una fórmula y la (no)computabilidad del conjunto que define.

Otro efecto del uso de la aritmética de segundo orden es la necesidad de restringir los teoremas matemáticos generales a formas que se puedan expresar dentro de la aritmética. Por ejemplo, la aritmética de segundo orden puede expresar el principio "Todo espacio vectorial contable tiene una base", pero no puede expresar el principio "Todo espacio vectorial tiene una base". En términos prácticos, esto significa que los teoremas del álgebra y la combinatoria están restringidos a las estructuras contables, mientras que los teoremas de análisis y topología están restringidos a los espacios separables . Muchos principios que implican el axioma de elección en su forma general (como "Todo espacio vectorial tiene una base") se vuelven demostrables en subsistemas débiles de la aritmética de segundo orden cuando se restringen. Por ejemplo, "todo cuerpo tiene una clausura algebraica" no es demostrable en la teoría de conjuntos ZF, pero la forma restringida "todo cuerpo contable tiene una clausura algebraica" es demostrable en RCA ₀ , el sistema más débil empleado típicamente en matemáticas inversas.

Uso de aritmética de orden superior

Una línea reciente de investigación en matemáticas inversas de orden superior , iniciada por Ulrich Kohlenbach en 2005, se centra en los subsistemas de la aritmética de orden superior . ^[4] Debido al lenguaje más rico de la aritmética de orden superior, el uso de representaciones (también conocidas como "códigos") comunes en la aritmética de segundo orden se reduce en gran medida. Por ejemplo, una función continua en el espacio de Cantor es simplemente una función que mapea secuencias binarias a secuencias binarias, y que también satisface la definición habitual de "épsilon-delta" de continuidad.

Las matemáticas inversas de orden superior incluyen versiones de orden superior de esquemas de comprensión (de segundo orden). Un axioma de orden superior de este tipo establece la existencia de un funcional que decide la verdad o falsedad de fórmulas de una complejidad dada. En este contexto, la complejidad de las fórmulas también se mide utilizando la jerarquía aritmética y la jerarquía analítica . Las contrapartes de orden superior de los principales subsistemas de la aritmética de segundo orden generalmente prueban las mismas oraciones de segundo orden (o un subconjunto grande) que los sistemas originales de segundo orden. ^[5] Por ejemplo, la teoría base de las matemáticas inversas de orden superior, llamada RCA^ω
₀, prueba las mismas oraciones que RCA ₀ , hasta el lenguaje.

Como se señaló en el párrafo anterior, los axiomas de comprensión de segundo orden se generalizan fácilmente al marco de orden superior. Sin embargo, los teoremas que expresan la compacidad de los espacios básicos se comportan de manera bastante diferente en la aritmética de segundo y superior orden: por un lado, cuando se restringen a las cubiertas contables/el lenguaje de la aritmética de segundo orden, la compacidad del intervalo unitario es demostrable en WKL ₀ a partir de la siguiente sección. Por otro lado, dadas las cubiertas incontables/el lenguaje de la aritmética de orden superior, la compacidad del intervalo unitario solo es demostrable a partir de la aritmética de segundo orden (completa). ^[6] Otros lemas de cobertura (por ejemplo, debido a Lindelöf , Vitali , Besicovitch , etc.) exhiben el mismo comportamiento, y muchas propiedades básicas de la integral de calibre son equivalentes a la compacidad del espacio subyacente.

Los cinco grandes subsistemas de la aritmética de segundo orden

La aritmética de segundo orden es una teoría formal de los números naturales y de los conjuntos de números naturales. Muchos objetos matemáticos, como anillos , grupos y cuerpos contables , así como puntos en espacios polacos efectivos , pueden representarse como conjuntos de números naturales y, en módulo de esta representación, pueden estudiarse en la aritmética de segundo orden.

Las matemáticas inversas hacen uso de varios subsistemas de aritmética de segundo orden. Un teorema típico de matemáticas inversas muestra que un teorema matemático particular T es equivalente a un subsistema particular S de aritmética de segundo orden sobre un subsistema más débil B . Este sistema más débil B se conoce como el sistema base para el resultado; para que el resultado de las matemáticas inversas tenga significado, este sistema no debe ser capaz de demostrar por sí mismo el teorema matemático T . ^{[ cita requerida ]}

Simpson (2009) describe cinco subsistemas particulares de aritmética de segundo orden, a los que llama los Cinco Grandes , que aparecen con frecuencia en las matemáticas inversas. En orden de fuerza creciente, estos sistemas se nombran con las siglas RCA ₀ , WKL ₀ , ACA ₀ , ATR ₀ y Π¹
₁-CA ₀ .

La siguiente tabla resume los "cinco grandes" sistemas ^[7] y enumera los sistemas equivalentes en aritmética de orden superior. ^[5] Estos últimos generalmente prueban las mismas oraciones de segundo orden (o un subconjunto grande) que los sistemas de segundo orden originales. ^[5]

El subíndice ₀ en estos nombres significa que el esquema de inducción ha sido restringido del esquema completo de inducción de segundo orden. ^[8] Por ejemplo, ACA ₀ incluye el axioma de inducción (0 ∈ X ∀ n ( n ∈ X → n + 1 ∈ X )) → ∀ n n ∈ X ${\displaystyle \wedge }$ . Esto junto con el axioma de comprensión completa de la aritmética de segundo orden implica el esquema completo de inducción de segundo orden dado por el cierre universal de ( φ (0) ∀ n ( φ ( n ) → φ ( n +1))) → ∀ n φ ( n ) ${\displaystyle \wedge }$ para cualquier fórmula de segundo orden φ . Sin embargo, ACA ₀ no tiene el axioma de comprensión completo, y el subíndice ₀ es un recordatorio de que tampoco tiene el esquema de inducción de segundo orden completo. Esta restricción es importante: los sistemas con inducción restringida tienen ordinales de demostración teórica significativamente más bajos que los sistemas con el esquema de inducción de segundo orden completo.

El sistema base RCA0

RCA ₀ es el fragmento de aritmética de segundo orden cuyos axiomas son los axiomas de la aritmética de Robinson , inducción para Σ⁰
₁Fórmulas y comprensión de Δ⁰
₁fórmulas.

El subsistema RCA ₀ es el más comúnmente utilizado como sistema base para las matemáticas inversas. Las iniciales "RCA" significan "axioma de comprensión recursiva", donde "recursivo" significa "computable", como en función recursiva . Este nombre se utiliza porque RCA ₀ corresponde informalmente a "matemática computable". En particular, cualquier conjunto de números naturales que se pueda demostrar que existen en RCA ₀ es computable, y por lo tanto cualquier teorema que implique que existen conjuntos no computables no es demostrable en RCA _0. En esta medida, RCA ₀ es un sistema constructivo, aunque no cumple con los requisitos del programa del constructivismo porque es una teoría de la lógica clásica que incluye la ley del medio excluido .

A pesar de su aparente debilidad (de no demostrar que existen conjuntos no computables), RCA ₀ es suficiente para demostrar una serie de teoremas clásicos que, por lo tanto, requieren solo una fuerza lógica mínima. Estos teoremas están, en cierto sentido, por debajo del alcance de la empresa de las matemáticas inversas porque ya son demostrables en el sistema base. Los teoremas clásicos demostrables en RCA ₀ incluyen:

• Propiedades básicas de los números naturales, enteros y racionales (por ejemplo, que estos últimos forman un cuerpo ordenado ).
• Propiedades básicas de los números reales (los números reales son un cuerpo ordenado arquimediano ; cualquier secuencia anidada de intervalos cerrados cuyas longitudes tienden a cero tiene un único punto en su intersección; los números reales no son contables). ^{[1] Sección II.4}
• Teorema de la categoría de Baire para un espacio métrico completamente separable (la condición de separabilidad es necesaria incluso para enunciar el teorema en el lenguaje de la aritmética de segundo orden). ^{[1] Teorema II.5.8}
• Teorema del valor intermedio en funciones reales continuas. ^{[1] Teorema II.6.6}
• Teorema de Banach-Steinhaus para una secuencia de operadores lineales continuos en espacios de Banach separables. ^{[1] Teorema II.10.8}
• Una versión débil del teorema de completitud de Gödel (para un conjunto de oraciones, en un lenguaje contable, que ya está cerrado bajo consecuencia).
• La existencia de un cierre algebraico para un cuerpo contable (pero no su unicidad). ^{[1] II.9.4--II.9.8}
• La existencia y unicidad de la clausura real de un cuerpo ordenado contable. ^{[1] II.9.5, II.9.7}

La parte de primer orden de RCA ₀ (los teoremas del sistema que no involucran ninguna variable de conjunto) es el conjunto de teoremas de la aritmética de Peano de primer orden con inducción limitada a Σ⁰
₁fórmulas. Es demostrablemente consistente, como lo es RCA ₀ , en la aritmética de Peano de primer orden completa.

Lema de König débil WKL0

El subsistema WKL ₀ consta de RCA ₀ más una forma débil del lema de König , es decir, la afirmación de que cada subárbol infinito del árbol binario completo (el árbol de todas las secuencias finitas de 0 y 1) tiene un camino infinito. Esta proposición, que se conoce como lema débil de König , es fácil de enunciar en el lenguaje de la aritmética de segundo orden. WKL ₀ también se puede definir como el principio de Σ⁰
₁separación (dados dos Σ⁰
₁fórmulas de una variable libre n que son excluyentes, existe un conjunto que contiene todos los n que satisfacen uno y ningún n que satisface el otro). Cuando este axioma se agrega a RCA ₀ , el subsistema resultante se llama WKL ₀ . Se hace una distinción similar entre axiomas particulares por un lado, y subsistemas que incluyen los axiomas básicos y la inducción por otro lado, para los subsistemas más fuertes descritos a continuación.

En cierto sentido, el lema débil de König es una forma del axioma de elección (aunque, como se ha dicho, se puede demostrar en la teoría clásica de conjuntos de Zermelo-Fraenkel sin el axioma de elección). No es constructivamente válido en algunos sentidos de la palabra "constructivo".

Para demostrar que WKL ₀ es en realidad más fuerte que (no demostrable en) RCA ₀ , es suficiente exhibir un teorema de WKL ₀ que implica que existen conjuntos no computables. Esto no es difícil; WKL ₀ implica la existencia de conjuntos separadores para conjuntos recursivamente enumerables efectivamente inseparables.

Resulta que RCA ₀ y WKL ₀ tienen la misma parte de primer orden, lo que significa que prueban las mismas oraciones de primer orden. Sin embargo, WKL ₀ puede probar una buena cantidad de resultados matemáticos clásicos que no se deducen de RCA _0. Estos resultados no se pueden expresar como enunciados de primer orden, pero sí como enunciados de segundo orden.

Los siguientes resultados son equivalentes al lema de König débil y, por tanto, a WKL ₀ sobre RCA ₀ :

• El teorema de Heine-Borel para el intervalo real unitario cerrado, en el siguiente sentido: todo recubrimiento por una secuencia de intervalos abiertos tiene un subrecubrimiento finito.
• El teorema de Heine-Borel para espacios métricos separables, totalmente acotados y completos (donde el cubrimiento es mediante una secuencia de bolas abiertas).
• Una función real continua en el intervalo unitario cerrado (o en cualquier espacio métrico compacto separable, como el anterior) está acotada (o: está acotada y alcanza sus límites).
• Una función real continua en el intervalo unitario cerrado puede aproximarse uniformemente mediante polinomios (con coeficientes racionales).
• Una función real continua en el intervalo unitario cerrado es uniformemente continua.
• Una función real continua en el intervalo unitario cerrado es integrable según Riemann .
• Teorema del punto fijo de Brouwer (para funciones continuas en un -símplex). ^{[1] Teorema IV.7.7} ${\displaystyle n}$
• El teorema de Hahn-Banach separable en la forma: una forma lineal acotada en un subespacio de un espacio de Banach separable se extiende a una forma lineal acotada en todo el espacio.
• El teorema de la curva de Jordan
• Teorema de completitud de Gödel (para un lenguaje contable).
• Determinación para juegos abiertos (o incluso clopen) en {0,1} de longitud ω.
• Todo anillo conmutativo contable tiene un ideal primo .
• Todo cuerpo formalmente real y contable es ordenable.
• Unicidad del cierre algebraico (para un cuerpo contable).

Comprensión aritmética ACA0

ACA ₀ es RCA ₀ más el esquema de comprensión de fórmulas aritméticas (que a veces se denomina "axioma de comprensión aritmética"). Es decir, ACA ₀ nos permite formar el conjunto de números naturales que satisfacen una fórmula aritmética arbitraria (una sin variables de conjunto acotadas, aunque posiblemente contenga parámetros de conjunto). ^{[1] pp. 6--7} En realidad, basta con añadir a RCA ₀ el esquema de comprensión de fórmulas Σ ₁ (que también incluye variables libres de segundo orden) para obtener una comprensión aritmética completa. ^{[1] Lema III.1.3}

La parte de primer orden de ACA ₀ es exactamente aritmética de Peano de primer orden; ACA ₀ es una extensión conservadora de la aritmética de Peano de primer orden. Los dos sistemas son demostrablemente (en un sistema débil) equiconsistentes. ACA ₀ puede considerarse como un marco de matemática predicativa , aunque existen teoremas demostrables de manera predicativa que no son demostrables en ACA ₀ . La mayoría de los resultados fundamentales sobre los números naturales, y muchos otros teoremas matemáticos, pueden demostrarse en este sistema.

Una forma de ver que ACA ₀ es más fuerte que WKL ₀ es exhibir un modelo de WKL ₀ que no contenga todos los conjuntos aritméticos. De hecho, es posible construir un modelo de WKL ₀ que consista enteramente en conjuntos bajos utilizando el teorema de base baja , ya que los conjuntos bajos en relación con los conjuntos bajos son bajos.

Las siguientes afirmaciones son equivalentes a ACA ₀ sobre RCA ₀ :

• La completitud secuencial de los números reales (toda secuencia creciente acotada de números reales tiene un límite). ^{[1] Teorema III.2.2}
• Teorema de Bolzano-Weierstrass . ^{[1] Teorema III.2.2}
• Teorema de Ascoli : toda secuencia equicontinua acotada de funciones reales en el intervalo unitario tiene una subsucesión uniformemente convergente.
• Todo cuerpo contable se incrusta isomórficamente en su clausura algebraica. ^{[1] Teorema III.3.2}
• Todo anillo conmutativo contable tiene un ideal máximo . ^{[1] teorema III.5.5}
• Todo espacio vectorial contable sobre los racionales (o sobre cualquier cuerpo contable) tiene una base. ^{[1] Teorema III.4.3}
• Para cualquier campo contable , existe una base de trascendencia para sobre . ^{[1] teorema III.4.6} ${\displaystyle K\subseteq L}$ ${\displaystyle L}$ ${\displaystyle K}$
• Lema de König (para árboles arbitrarios de ramificación finita, a diferencia de la versión débil descrita anteriormente). ^{[1] Teorema III.7.2}
• Para cualquier grupo contable y cualquier subgrupo de , existe el subgrupo generado por . ^{[9] p.40} ${\displaystyle G}$ ${\displaystyle H,I}$ ${\displaystyle G}$ ${\displaystyle H\cup I}$
• Cualquier función parcial puede extenderse a una función total. ^[10]
• Varios teoremas en combinatoria, como ciertas formas del teorema de Ramsey . ^{[11] [1] Teorema III.7.2}

Recursión transfinita aritmética ATR0

El sistema ATR ₀ añade a ACA ₀ un axioma que establece, informalmente, que cualquier funcional aritmético (es decir, cualquier fórmula aritmética con una variable numérica libre n y una variable de conjunto libre X , vista como el operador que lleva X al conjunto de n que satisface la fórmula) puede iterarse transfinitamente a lo largo de cualquier orden contable comenzando con cualquier conjunto. ATR ₀ es equivalente sobre ACA ₀ al principio de Σ¹
₁separación. ATR ₀ es impredicativo y tiene el ordinal de prueba teórica , el supremo de los sistemas predicativos. ${\displaystyle \Gamma _{0}}$

ATR ₀ demuestra la consistencia de ACA ₀ y, por lo tanto, por el teorema de Gödel, es estrictamente más fuerte.

Las siguientes afirmaciones son equivalentes a ATR ₀ sobre RCA ₀ :

• Dos ordenamientos de pozos contables cualesquiera son comparables, es decir, son isomorfos o uno es isomorfo a un segmento inicial propio del otro. ^{[1] Teorema V.6.8}
• Teorema de Ulm para grupos abelianos reducidos contables.
• El teorema del conjunto perfecto , que establece que todo subconjunto cerrado incontable de un espacio métrico separable completo contiene un conjunto cerrado perfecto.
• Teorema de separación de Lusin (esencialmente Σ¹
  ₁separación). ^{[1] Teorema V.5.1}
• Determinación para conjuntos abiertos en el espacio de Baire .

P1 1comprensión Π1 1-CALIFORNIA0

P¹
₁-CA ₀ es más fuerte que la recursión transfinita aritmética y es completamente impredicativa. Consiste en RCA ₀ más el esquema de comprensión para Π¹
₁fórmulas.

En cierto sentido, Π¹
₁-CA ₀ comprensión es recursión transfinita aritmética (Σ¹
₁separación) ya que ACA ₀ es demasiado débil para el lema de König (Σ⁰
₁separación). Es equivalente a varias afirmaciones de la teoría de conjuntos descriptivos cuyas pruebas hacen uso de argumentos fuertemente impredicativos; esta equivalencia muestra que estos argumentos impredicativos no pueden eliminarse.

Los siguientes teoremas son equivalentes a Π¹
₁-CA ₀ sobre RCA ₀ :

• Teorema de Cantor-Bendixson (todo conjunto cerrado de números reales es la unión de un conjunto perfecto y un conjunto numerable). ^{[1] Ejercicio VI.1.7}
• Dicotomía de Silver (toda relación de equivalencia coanalítica tiene un número contable de clases de equivalencia o un conjunto perfecto de incomparables) ^{[1] Teorema VI.3.6}
• Todo grupo abeliano contable es la suma directa de un grupo divisible y un grupo reducido. ^{[1] Teorema VI.4.1}
• Determinación para juegos. ^{[1] Teorema VI.5.4} ${\displaystyle \Sigma _{1}^{0}\land \Pi _{1}^{0}}$

Sistemas adicionales

• Se pueden definir sistemas más débiles que la comprensión recursiva. El sistema débil RCA^*
  ₀consiste en funciones aritméticas elementales EFA (los axiomas básicos más Δ⁰
  ₀inducción en el lenguaje enriquecido con una operación exponencial) más Δ⁰
  ₁Comprensión. Sobre RCA^*
  ₀, comprensión recursiva como se definió anteriormente (es decir, con Σ⁰
  ₁La inducción es equivalente a la afirmación de que un polinomio (sobre un cuerpo contable) tiene sólo un número finito de raíces y al teorema de clasificación para grupos abelianos finitamente generados. El sistema RCA^*
  ₀tiene el mismo ordinal teórico de prueba ω ³ que EFA y es conservador sobre EFA para Π⁰
  ₂oraciones.
• Débil Débil El lema de König es la afirmación de que un subárbol del árbol binario infinito que no tiene caminos infinitos tiene una proporción asintóticamente nula de hojas de longitud n (con una estimación uniforme de cuántas hojas de longitud n existen). Una formulación equivalente es que cualquier subconjunto del espacio de Cantor que tenga medida positiva no está vacío (esto no es demostrable en RCA ₀ ). WWKL ₀ se obtiene adjuntando este axioma a RCA ₀ . Es equivalente a la afirmación de que si el intervalo real unitario está cubierto por una secuencia de intervalos, entonces la suma de sus longitudes es al menos uno. La teoría de modelos de WWKL ₀ está estrechamente relacionada con la teoría de secuencias algorítmicamente aleatorias . En particular, un ω-modelo de RCA ₀ satisface el lema de König débil débil si y solo si para cada conjunto X hay un conjunto Y que es 1-aleatorio en relación con X .
• DNR (abreviatura de "diagonally non-recursive") añade a RCA ₀ un axioma que afirma la existencia de una función diagonalmente no recursiva relativa a cada conjunto. Es decir, DNR afirma que, para cualquier conjunto A , existe una función total f tal que para todo e la e ésima función recursiva parcial con oráculo A no es igual a f . DNR es estrictamente más débil que WWKL (Lempp et al. , 2004).
• Δ¹
  ₁-La comprensión es en ciertos aspectos análoga a la recursión transfinita aritmética, como la comprensión recursiva lo es al lema débil de König. Tiene los conjuntos hiperaritméticos como modelo ω mínimo. La recursión transfinita aritmética demuestra que Δ¹
  ₁-comprensión, pero no al revés.
• Σ¹
  ₁-choice es la afirmación de que si η ( n , X ) es un Σ¹
  ₁fórmula tal que para cada n existe una X que satisface η entonces existe una secuencia de conjuntos X _n tales que η ( n , X _n ) se cumple para cada n . Σ¹
  ₁-choice también tiene los conjuntos hiperaritméticos como modelo ω mínimo. La recursión transfinita aritmética demuestra Σ¹
  ₁-elección, pero no al revés.
• HBU (abreviatura de "Heine-Borel incontable") expresa la compacidad (de cobertura abierta) del intervalo unitario, que implica coberturas incontables . El último aspecto de HBU hace que solo sea expresable en el lenguaje de la aritmética de tercer orden . El teorema de Cousin (1895) implica HBU, y estos teoremas utilizan la misma noción de cobertura debido a Cousin y Lindelöf . HBU es difícil de demostrar: en términos de la jerarquía habitual de axiomas de comprensión, una prueba de HBU requiere aritmética completa de segundo orden. ^[6]
• El teorema de Ramsey para grafos infinitos no cae dentro de ninguno de los cinco grandes subsistemas, y hay muchas otras variantes más débiles con diferentes niveles de prueba. ^[11]

Sistemas más fuertes

Sobre RCA ₀ , Π¹
₁recursión transfinita, ∆⁰
₂determinación, y el ∆¹
₁El teorema de Ramsey es todos equivalentes entre sí.

Sobre RCA ₀ , Σ¹
₁inducción monótona, Σ⁰
₂determinación, y la Σ¹
₁El teorema de Ramsey es todos equivalentes entre sí.

Los siguientes son equivalentes: ^{[12] [13]}

• (esquema) Π¹
  ₃consecuencias de Π¹
  ₂-CA ₀
• RCA _{0 + (esquema sobre} n finitos ) determinación en el nivel n de la jerarquía de diferencias de Σ⁰
  ₂conjuntos
• RCA ₀ + {τ: τ es una oración S2S verdadera}

El conjunto de Π¹
₃consecuencias de la aritmética de segundo orden Z ₂ tiene la misma teoría que RCA _{0 + (esquema sobre} n finito ) determinación en el nivel n de la jerarquía de diferencias de Σ⁰
₃conjuntos. ^[14]

Para un conjunto parcial , sea el espacio topológico que consiste en los filtros en cuyos conjuntos abiertos están los conjuntos de la forma para algún . La siguiente afirmación es equivalente a sobre : para cualquier conjunto parcial numerable , el espacio topológico es completamente metrizable si y solo si es regular . ^[15] ${\displaystyle P}$ ${\displaystyle {\textrm {MF}}(P)}$ ${\displaystyle P}$ ${\displaystyle \{F\in {\textrm {MF}}(P)\mid p\in F\}}$ ${\displaystyle p\in P}$ ${\displaystyle \Pi _{2}^{1}{\mathsf {-CA}}_{0}}$ ${\displaystyle \Pi _{1}^{1}{\mathsf {-CA}}_{0}}$ ${\displaystyle P}$ ${\displaystyle {\textrm {MF}}(P)}$

Modelos ω y modelos β

El ω en ω-modelo representa el conjunto de números enteros no negativos (u ordinales finitos). Un ω-modelo es un modelo para un fragmento de aritmética de segundo orden cuya parte de primer orden es el modelo estándar de la aritmética de Peano, ^[1] pero cuya parte de segundo orden puede no ser estándar. Más precisamente, un ω-modelo está dado por una elección de subconjuntos de . Las variables de primer orden se interpretan de la manera habitual como elementos de , y , tienen sus significados habituales, mientras que las variables de segundo orden se interpretan como elementos de . Hay un ω-modelo estándar donde uno simplemente toma que consiste en todos los subconjuntos de los números enteros. Sin embargo, también hay otros ω-modelos; por ejemplo, RCA ₀ tiene un ω-modelo mínimo donde consiste en los subconjuntos recursivos de . ${\displaystyle S\subseteq {\mathcal {P}}(\omega )}$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle +}$ ${\displaystyle \times }$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \omega }$

Un modelo β es un modelo ω que concuerda con el modelo ω estándar en cuanto a la verdad de las oraciones y (con parámetros). ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Sigma _{1}^{1}}$

Los modelos no ω también son útiles, especialmente en las pruebas de teoremas de conservación.

Véase también

• Expresión en forma cerrada § Conversión de formas numéricas
• Principios de inducción, acotación y de mínimos números
• Análisis ordinal

Notas

1. Simpson, Stephen G. (2009), Subsistemas de aritmética de segundo orden, Perspectivas en lógica (2.ª ed.), Cambridge University Press, doi:10.1017/CBO9780511581007, ISBN 978-0-521-88439-6, MR 2517689
2. H. Friedman, Algunos sistemas de aritmética de segundo orden y su uso (1974), Actas del Congreso Internacional de Matemáticos
3. Dzhafarov, Damir D.; Mummert, Carl (2022). Matemáticas inversas: problemas, reducciones y demostraciones . Teoría y aplicaciones de la computabilidad (1.ª ed.). Springer Cham. págs. XIX, 488. doi :10.1007/978-3-031-11367-3. ISBN  978-3-031-11367-3.
4. Kohlenbach (2005).
5. Véase Kohlenbach (2005) y Hunter (2008).
6. Normann y Sanders (2018).
7. Simpson (2009), pág.42.
8. Simpson (2009), pág. 6.
9. S. Takashi, "Matemática inversa y sistemas algebraicos contables". Tesis doctoral, Universidad de Tohoku, 2016.
10. M. Fujiwara, T. Sato, "Nota sobre funciones totales y parciales en aritmética de segundo orden". En 1950 Proof Theory, Computation Theory and Related Topics , junio de 2015.
11. Hirschfeldt (2014).
12. Kołodziejczyk, Leszek; Michalewski, Henryk (2016). ¿Hasta qué punto es indemostrable el teorema de decidibilidad de Rabin? . LICS '16: 31.º Simposio anual ACM/IEEE sobre lógica en ciencias de la computación. arXiv : 1508.06780 .
13. Kołodziejczyk, Leszek (19 de octubre de 2015). "Pregunta sobre la capacidad de decisión de S2S". FOM.
14. Montalban, Antonio; Shore, Richard (2014). "Los límites de la determinación en aritmética de segundo orden: consistencia y fuerza de la complejidad". Revista israelí de matemáticas . 204 : 477–508. doi :10.1007/s11856-014-1117-9. S2CID  287519.
15. C. Mummert, SG Simpson. "Matemáticas inversas y comprensión". En Bulletin of Symbolic Logic vol. 11 (2005), pp.526–533. ${\displaystyle \Pi _{2}^{1}}$

Referencias

• Ambos-Spies, K.; Kjos-Hanssen, B.; Lempp, S.; Slaman, TA (2004), "Comparación de DNR y WWKL", Journal of Symbolic Logic , 69 (4): 1089, arXiv : 1408.2281 , doi :10.2178/jsl/1102022212, S2CID  17582399.
• Friedman, Harvey (1975), "Algunos sistemas de aritmética de segundo orden y su uso", Actas del Congreso Internacional de Matemáticos (Vancouver, BC, 1974), vol. 1 , Congreso de Matemáticas de Canadá, Montreal, Quebec, págs. 235–242, MR  0429508
• Friedman, Harvey (1976), Baldwin, John; Martin, DA ; Soare, RI ; Tait, WW (eds.), "Sistemas de aritmética de segundo orden con inducción restringida, I, II", Reunión de la Asociación de Lógica Simbólica, The Journal of Symbolic Logic , 41 (2): 557–559, doi :10.2307/2272259, JSTOR  2272259
• Hirschfeldt, Denis R. (2014), Slicing the Truth , Serie de notas de conferencias del Instituto de Ciencias Matemáticas, Universidad Nacional de Singapur, vol. 28, World Scientific
• Hunter, James (2008), Topología inversa (PDF) (tesis doctoral), Universidad de Wisconsin-Madison
• Kohlenbach, Ulrich (2005), "Matemáticas inversas de orden superior", en Simpson, Stephen G (ed.), Matemáticas inversas de orden superior, Matemáticas inversas 2001 (PDF) , Apuntes de clase en lógica, Cambridge University Press , pp. 281–295, CiteSeerX  10.1.1.643.551 , doi :10.1017/9781316755846.018, ISBN 9781316755846
• Normann, Dag; Sanders, Sam (2018), "Sobre el significado matemático y fundamental de lo incontable", Journal of Mathematical Logic , 19 : 1950001, arXiv : 1711.08939 , doi : 10.1142/S0219061319500016, S2CID  119120366
• Simpson, Stephen G. (2009), Subsistemas de aritmética de segundo orden, Perspectives in Logic (2.ª ed.), Cambridge University Press , doi :10.1017/CBO9780511581007, ISBN 978-0-521-88439-6, Sr.  2517689
• Stillwell, John (2018), Matemáticas inversas, pruebas de adentro hacia afuera , Princeton University Press , ISBN 978-0-691-17717-5

• Solomon, Reed (1999), "Grupos ordenados: un estudio de caso en matemáticas inversas", The Bulletin of Symbolic Logic , 5 (1): 45–58, CiteSeerX  10.1.1.364.9553 , doi :10.2307/421140, ISSN  1079-8986, JSTOR  421140, MR  1681895, S2CID  508431

Enlaces externos

• Página de inicio de Stephen G. Simpson
• Zoológico de Matemáticas Inversas