Matemáticas inversas

Rama de la lógica matemática

Matemáticas inversas es un programa de lógica matemática que busca determinar qué axiomas se requieren para demostrar teoremas de las matemáticas. Su método de definición puede describirse brevemente como "regresar de los teoremas a los axiomas ", en contraste con la práctica matemática ordinaria de derivar teoremas a partir de axiomas. Puede conceptualizarse como esculpir las condiciones necesarias a partir de las suficientes .

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

La matemática inversa suele llevarse a cabo utilizando subsistemas de aritmética de segundo orden , ^[1] donde muchas de sus definiciones y métodos se inspiran 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 recursividad ; Muchos resultados en matemáticas inversas tienen resultados correspondientes en análisis computable . En matemáticas inversas de orden superior , la atención se centra en los subsistemas de la aritmética de orden superior y el lenguaje más rico asociado. ^{[ se necesita aclaración ]}

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 no especialistas es Stillwell (2018). Una introducción a las matemáticas inversas de orden superior, y también el artículo fundacional, es Kohlenbach (2005).

Principios generales

En matemáticas inversas, se comienza con un lenguaje marco y una teoría base (un sistema de axiomas centrales) que es demasiado débil para demostrar la mayoría de los teoremas que podrían interesarle, pero aún lo suficientemente poderoso como para desarrollar las definiciones necesarias para enunciar estos 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 puede enunciarse en el sistema base pero que no es demostrable en el sistema base, el objetivo es determinar el sistema de axiomas 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 demostraciones. La primera prueba muestra que T es demostrable a partir de S ; ésta es una prueba matemática ordinaria junto con una justificación de que puede llevarse a cabo en el sistema S. La segunda prueba, conocida como inversión , muestra que T en sí implica S ; Esta prueba se realiza en el sistema base. ^[1] La inversión establece que ningún sistema de axiomas 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ía de las investigaciones en matemáticas inversas se centran en subsistemas de la aritmética de segundo orden . El conjunto de investigaciones en matemáticas inversas ha establecido que los subsistemas débiles de aritmética de segundo orden son suficientes para formalizar casi todas las matemáticas de nivel universitario. En aritmética de segundo orden, todos los objetos se pueden representar como números naturales o conjuntos de números naturales. Por ejemplo, para demostrar teoremas sobre números reales, los números reales se pueden representar como secuencias de Cauchy de números racionales , cada una de las cuales se puede representar como un conjunto de números naturales.

Los sistemas de axiomas que se consideran con mayor frecuencia en matemáticas inversas se definen utilizando esquemas de axiomas llamados esquemas de comprensión . Tal esquema establece que existe cualquier conjunto de números naturales definibles mediante una fórmula de una complejidad determinada. 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 las matemáticas inversas no se llevan a cabo utilizando la teoría de conjuntos como sistema base es que el lenguaje de la teoría de conjuntos es demasiado expresivo. 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 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 puedan expresarse 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 de álgebra y combinatoria están restringidos a estructuras contables, mientras que los teoremas de análisis y topología están restringidos a 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 aritmética de segundo orden cuando están restringidos. Por ejemplo, "cada campo tiene un cierre algebraico" no es demostrable en la teoría de conjuntos ZF, pero la forma restringida "cada campo contable tiene un cierre algebraico" es demostrable en RCA ₀ , el sistema más débil típicamente empleado en matemáticas inversas.

Uso de aritmética de orden superior

Una corriente reciente de investigación en matemáticas inversas de orden superior , iniciada por Ulrich Kohlenbach en 2005, se centra en subsistemas de aritmética de orden superior . ^[3] 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 considerablemente. Por ejemplo, una función continua en el espacio de Cantor es simplemente una función que asigna secuencias binarias a secuencias binarias, y que también satisface la definición habitual de continuidad 'épsilon-delta'.

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 establece la existencia de un funcional que decide la verdad o falsedad de fórmulas de una complejidad determinada. 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 subsistemas principales de la aritmética de segundo orden generalmente demuestran las mismas oraciones de segundo orden (o un subconjunto grande) que los sistemas originales de segundo orden. ^[4] Por ejemplo, la teoría básica de las matemáticas inversas de orden superior, llamada RCA^ω0
_{_}, prueba las mismas oraciones que RCA ₀ , hasta el idioma.

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 espacios básicos se comportan de manera muy diferente en aritmética de segundo orden y superior: por un lado, cuando se restringen a cubiertas contables/el lenguaje de la aritmética de segundo orden, la compacidad del intervalo unitario se puede demostrar en WKL ₀ de la siguiente sección. Por otro lado, dadas las coberturas incontables/el lenguaje de la aritmética de orden superior, la compacidad del intervalo unitario sólo se puede demostrar a partir de la aritmética de segundo orden (completa). ^[5] 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 campos contables , así como puntos en espacios polacos efectivos , se pueden representar como conjuntos de números naturales y, en módulo, esta representación se puede estudiar en aritmética de segundo orden.

La matemática inversa utiliza varios subsistemas de la aritmética de segundo orden. Un teorema matemático inverso típico muestra que un teorema matemático particular T es equivalente a un subsistema particular S de aritmética de segundo orden sobre un subsistema B más débil . Este sistema B más débil se conoce como sistema base del resultado; Para que el resultado matemático inverso tenga significado, este sistema no debe poder demostrar por sí mismo el teorema matemático T. ^{[ cita necesaria ]}

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

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

El subíndice ₀ en estos nombres significa que el esquema de inducción ha sido restringido del esquema de inducción completo de segundo orden. ^[7] Por ejemplo, ACA ₀ incluye el axioma de inducción (0 ∈  X  ∧ ∀ n ( n  ∈  X  →  n  + 1 ∈  X )) → ∀ n  n  ∈ X . Esto, junto con el axioma de comprensión total de la aritmética de segundo orden, implica el esquema de inducción completo de segundo orden dado por la clausura universal de ( φ (0) ∧ ∀ n ( φ ( n ) → φ ( n +1))) → ∀ n φ ( n ) para cualquier fórmula de segundo orden φ . Sin embargo, el 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 teóricos de prueba significativamente más bajos que los sistemas con el esquema de inducción completo de segundo orden.

El sistema base RCA 0

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 utilizado como sistema base para matemáticas inversas. Las iniciales "RCA" significan "axioma de comprensión recursiva", donde "recursivo" significa "comutable", como en función recursiva . Este nombre se utiliza porque RCA ₀ corresponde informalmente a "matemáticas computables". En particular, cualquier conjunto de números naturales cuya existencia pueda demostrarse en RCA ₀ es computable y, por tanto, cualquier teorema que implique que existen conjuntos no computables no es demostrable en RCA ₀ . En este sentido, 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 tercero excluido .

A pesar de su aparente debilidad (de no demostrar la existencia de conjuntos no computables), RCA ₀ es suficiente para demostrar una serie de teoremas clásicos que, por lo tanto, requieren sólo una fuerza lógica mínima. Estos teoremas están, en cierto sentido, por debajo del alcance de la matemática inversa 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 formen un cuerpo ordenado ).
• Propiedades básicas de los números reales (los números reales son un campo ordenado de Arquímedes ; cualquier secuencia anidada de intervalos cerrados cuyas longitudes tienden a cero tiene un solo punto en su intersección; los números reales no son contables). ^{[1] Sección II.4}
• El teorema de la categoría de Baire para un espacio métrico separable completo (la condición de separabilidad es necesaria incluso para expresar el teorema en el lenguaje de la aritmética de segundo orden). ^{[1] teorema II.5.8}
• El teorema del valor intermedio en funciones reales continuas. ^{[1] teorema II.6.6}
• El 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 una clausura algebraica para un campo contable (pero no su unicidad). ^{[1] II.9.4--II.9.8}
• La existencia y unicidad del cierre real de un campo ordenado contable. ^{[1] II.9.5, II.9.7}

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

Lema de Kőnig débil WKL 0

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 de Kőnig débil , 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 exclusivas, hay un conjunto que contiene todos los n que satisfacen una y ningún n que satisface la otra). Cuando este axioma se suma 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 el otro, para los subsistemas más fuertes que se describen a continuación.

En cierto sentido, el lema de Kőnig débil es una forma del axioma de elección (aunque, como se indicó, puede demostrarse en la teoría de conjuntos clásica 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 implique 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. WKL ₀ puede demostrar un buen número de resultados matemáticos clásicos que, sin embargo, no se derivan de RCA ₀ . Estos resultados no se pueden expresar como enunciados de primer orden, pero pueden expresarse 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: toda cobertura por una secuencia de intervalos abiertos tiene una subcobertura finita.
• El teorema de Heine-Borel para espacios métricos separables totalmente acotados (donde la cobertura se realiza mediante una secuencia de bolas abiertas).
• Una función real continua en el intervalo unitario cerrado (o en cualquier espacio métrico separable compacto, como arriba) está acotada (o: acotada y alcanza sus límites).
• Una función real continua en el intervalo unitario cerrado se puede aproximar 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 de Riemann .
• El teorema del punto fijo de Brouwer (para funciones continuas sobre un producto finito de copias del intervalo unitario cerrado).
• El teorema separable de Hahn-Banach 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 cerrados) en {0,1} de longitud ω.
• Todo anillo conmutativo contable tiene un ideal primo .
• Todo campo contable formalmente real es ordenable.
• Unicidad del cierre algebraico (para un campo contable).

Comprensión aritmética ACA 0

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 establecidas vinculadas, aunque posiblemente contenga parámetros establecidos). En realidad, basta con añadir a RCA ₀ el esquema de comprensión de las fórmulas Σ ₁ para obtener una comprensión aritmética completa.

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áticas predicativas , aunque existen teoremas predicativamente demostrables que no son demostrables en ACA ₀ . La mayoría de los resultados fundamentales sobre los números naturales y muchos otros teoremas matemáticos se pueden demostrar 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 equivalen 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}
• El 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 subsecuencia uniformemente convergente.
• Cada campo contable se integra isomórficamente en su cierre algebraico. ^{[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 campo contable) tiene una base. ^{[1] teorema III.4.3}
• Para cualquier campo contable , existe una base de trascendencia para over . ^{[1] teorema III.4.6} ${\displaystyle K\subseteq L}$ ${\displaystyle L}$ ${\displaystyle K}$
• Lema de Kőnig (para árboles arbitrarios con ramificaciones finitas, a diferencia de la versión débil descrita anteriormente). ^{[1] teorema III.7.2}
• Para cualquier grupo contable y cualquier subgrupo de , el subgrupo generado por existe. ^{[8] pág.40} ${\displaystyle G}$ ${\displaystyle H,I}$ ${\displaystyle G}$ ${\displaystyle H\cup I}$
• Cualquier función parcial se puede extender a una función total. ^[9]
• Varios teoremas en combinatoria, como ciertas formas del teorema de Ramsey . ^[10]

Recursión aritmética transfinita ATR 0

El sistema ATR ₀ añade al 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) se puede iterar transfinitamente a lo largo de cualquier orden de pozo contable comenzando con cualquier conjunto. ATR ₀ es equivalente sobre ACA ₀ al principio de Σ¹
₁separación. ATR ₀ es impredicativo y tiene el ordinal de teoría de la prueba , el supremo del de los sistemas predicativos. ${\displaystyle \Gamma _{0}}$

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

Las siguientes afirmaciones equivalen a ATR ₀ sobre RCA ₀ :

• Cualquier orden de dos pozos contables es comparable. 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).
• Determinación para conjuntos abiertos en el espacio de Baire .

Π1 1comprensión Π1 1-CA 0

Π¹
₁-CA ₀ es más fuerte que la recursividad transfinita aritmética y es totalmente impredicativa. Consta de RCA ₀ más el esquema de comprensión de Π¹
₁fórmulas.

En cierto sentido, Π¹
₁-La comprensión de CA ₀ es la recursividad transfinita aritmética (Σ¹
₁separación) como ACA ₀ es el lema de Kőnig débil (Σ⁰
₁separación). Equivale a varios enunciados de la teoría descriptiva de conjuntos 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 ₀ :

• El teorema de Cantor-Bendixson (todo conjunto cerrado de reales es la unión de un conjunto perfecto y un conjunto contable).
• La dicotomía de Silver (cada relación de equivalencia coanalítica tiene muchas clases de equivalencia o un conjunto perfecto de incomparables) ^[11]
• Todo grupo abeliano contable es la suma directa de un grupo divisible y un grupo reducido.

Sistemas adicionales

• Se pueden definir sistemas más débiles que la comprensión recursiva. El débil sistema RCA.^*
  ₀consta de 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 Σ⁰
  ₁inducción) es equivalente a la afirmación de que un polinomio (sobre un campo contable) tiene sólo un número finito de raíces y al teorema de clasificación para grupos abelianos generados finitamente. El sistema RCA^*
  ₀tiene el mismo ordinal teórico de prueba ω ³ que EFA y es conservador sobre EFA para Π⁰
  ₂oraciones.
• Débil El lema de Kőnig débil es la afirmación de que un subárbol del árbol binario infinito que no tiene caminos infinitos tiene una proporción asintóticamente desvaneciente de las 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 se puede demostrar en RCA ₀ ). WWKL ₀ se obtiene uniendo este axioma a RCA ₀ . Equivale a afirmar 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 del modelo 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 si y solo si para cada conjunto X hay un conjunto Y que es 1 aleatorio en relación con X.
• DNR (abreviatura de "diagonalmente no recursiva") agrega a RCA ₀ un axioma que afirma la existencia de una función diagonalmente no recursiva relativa a cada conjunto. Es decir, DNR establece que, para cualquier conjunto A , existe una función total f tal que para todo e la función recursiva parcial con Oracle A no es igual a f . DNR es estrictamente más débil que WWKL (Lempp et al. , 2004).
• Δ¹
  ₁-la comprensión es en cierto modo análoga a la recursividad 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 aritmética transfinita demuestra Δ¹
  ₁-comprensión pero no al revés.
• Σ¹
  ₁-elección es la afirmación de que si η ( n , X ) es un Σ¹
  ₁fórmula tal que para cada n existe una X que satisface η entonces hay una secuencia de conjuntos X _n tal que η ( n , X _n ) se cumple para cada n . Σ¹
  ₁-choice también tiene los conjuntos hiperaritméticos como modelo ω mínimo. La recursión aritmética transfinita demuestra Σ¹
  ₁-elección pero no al revés.
• HBU (abreviatura de "Heine-Borel incontable") expresa la compacidad (de cubierta abierta) del intervalo unitario, que implica cubiertas incontables . Este último aspecto de HBU lo hace sólo 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 demostración de HBU requiere aritmética completa de segundo orden. ^[5]
• El teorema de Ramsey para gráficos infinitos no cae en uno de los cinco grandes subsistemas, y hay muchas otras variantes más débiles con diferentes grados de prueba. ^[10]

Sistemas más fuertes

Sobre RCA ₀ , Π¹
₁recursividad transfinita, ∆⁰
₂determinabilidad, y el ∆¹
₁El teorema de Ramsey son todos equivalentes entre sí.

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

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

• (esquema) Π¹
  ₃consecuencias de Π¹
  ₂-CA ₀
• RCA ₀ + (esquema sobre n finito ) determinación en el n ésimo nivel 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 ₀ + (esquema sobre n finito ) determinación en el n- ésimo nivel de la jerarquía de diferencias de Σ⁰
₃conjuntos. ^[14]

Para un poset , denotemos el espacio topológico que consta de los filtros en cuyos conjuntos abiertos se encuentran los conjuntos de la forma for some . La siguiente afirmación equivale a over : para cualquier poset contable , el espacio topológico es completamente metrizable 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 el 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 ω viene dado por una elección de subconjuntos de . Las variables de primer orden se interpretan de la forma habitual como elementos de , y , tienen sus significados habituales, mientras que las variables de segundo orden se interpretan como elementos de . Existe un modelo ω estándar en el que simplemente se considera que está formado por todos los subconjuntos de números enteros. Sin embargo, también existen otros modelos ω; por ejemplo, RCA ₀ tiene un modelo ω mínimo que consta de 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 distintos de ω también son útiles, especialmente en las pruebas de teoremas de conservación.

Ver también

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

Notas

1. 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, SEÑOR 2517689
2. H. Friedman, Algunos sistemas de aritmética de segundo orden y su uso (1974), Actas del Congreso Internacional de Matemáticos
3. Kohlenbach (2005).
4. Véase Kohlenbach (2005) y Hunter (2008).
5. Normann y Sanders (2018).
6. Simpson (2009), p.42.
7. Simpson (2009), pág. 6.
8. S. Takashi, "Matemáticas inversas y sistemas algebraicos contables". Doctor. tesis, Universidad de Tohoku, 2016.
9. M. Fujiwara, T. Sato, "Nota sobre funciones totales y parciales en aritmética de segundo orden". En 1950 Teoría de la prueba, teoría de la computación y temas relacionados , junio de 2015.
10. Hirschfeldt (2014).
11. Simpson (2009), p.229.
12. Kołodziejczyk, Leszek; Michalewski, Henryk (2016). ¿Qué tan improbable es el teorema de decidibilidad de Rabin? . LICS '16: 31º Simposio anual ACM/IEEE sobre lógica en informática. arXiv : 1508.06780 .
13. Kołodziejczyk, Leszek (19 de octubre de 2015). "Pregunta sobre la capacidad de decisión de S2S". FOM.
14. Montalbán, Antonio; Orilla, Richard (2014). "Los límites de la determinación en la 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 Boletín de Lógica Simbólica vol. 11 (2005), págs.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 , Canadá. Matemáticas. Congreso, Montreal, Que., págs. 235–242, MR  0429508
• Friedman, Harvey (1976), Baldwin, John; Martín, DA ; Soare, Rhode Island ; 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 de la Universidad Nacional de Singapur, vol. 28, científico mundial
• 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 conferencias sobre lógica, Cambridge University Press , págs. , 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, señor  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, SEÑOR  1681895, S2CID  508431

enlaces externos

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