La matemática inversa es un método de lógica matemática que busca determinar qué axiomas son necesarios para demostrar teoremas. Su método se puede describir brevemente como "ir hacia atrás, desde los teoremas hasta los axiomas ", a diferencia de la práctica matemática habitual de derivar teoremas a partir de axiomas. Se puede conceptualizar como la obtención de condiciones necesarias a partir de condiciones suficientes .
El programa de matemáticas inversas fue prefigurado por resultados en teoría de conjuntos, como el teorema clásico que establece que el axioma de elección y el lema de Zorn son equivalentes sobre la teoría de conjuntos ZF . Sin embargo, el objetivo de las matemáticas inversas es estudiar posibles axiomas de teoremas matemáticos ordinarios, en lugar de posibles axiomas para la teoría de conjuntos. Las matemáticas inversas se suelen llevar a cabo utilizando subsistemas de aritmética de segundo orden , [ 1 ] donde muchas de sus definiciones y métodos se inspiran en trabajos previos de análisis constructivo y teoría de la demostración . 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 está en subsistemas de aritmética de orden superior y el lenguaje más rico asociado.
El programa fue fundado por Harvey Friedman [ 2 ] [ 3 ] y promovido por Steve Simpson . [ 1 ]
La matemática inversa constructiva es un programa relacionado que se aplica a la matemática constructiva .
Principios generales
En matemáticas inversas, se parte de un lenguaje marco y una teoría base —un sistema axiomático central— que es demasiado débil para demostrar la mayoría de los teoremas de interés, pero lo suficientemente potente como para desarrollar las definiciones necesarias para enunciar dichos 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. [ 4 ]
Para cada teorema que puede enunciarse en el sistema base pero no es demostrable en el sistema base, el objetivo es determinar el sistema axiomático particular [ 5 ] (más fuerte que el sistema base) que es necesario para demostrar ese teorema. [ 5 ] Para demostrar que se requiere un sistema S para demostrar un teorema T , se requieren dos demostraciones. La primera demostración muestra que T es demostrable a partir de S ; esta es una demostración matemática ordinaria junto con una justificación de que puede llevarse a cabo en el sistema S. La segunda demostración, conocida como inversión , muestra que T mismo implica S ; esta demostración 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 sin dejar de demostrar T.
Uso de aritmética de segundo orden
La mayor parte de la investigación en matemáticas inversas se centra 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 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, estos pueden representarse como sucesiones de Cauchy de números racionales , cada una de las cuales puede representarse como un conjunto de números naturales. [ 6 ]
Los sistemas axiomáticos más comúnmente considerados en matemáticas inversas se definen mediante esquemas axiomáticos denominados esquemas de comprensión . Dicho esquema establece que existe cualquier conjunto de números naturales definible por 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 . [ 7 ]
La razón por la que las matemáticas inversas no se realizan utilizando la teoría de conjuntos como sistema base es que el lenguaje de la teoría de conjuntos es demasiado expresivo. [ 8 ] Conjuntos extremadamente complejos de números naturales pueden definirse mediante fórmulas simples en el lenguaje de la teoría de conjuntos (que puede 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 puedan expresarse dentro de la aritmética. Por ejemplo, la aritmética de segundo orden puede expresar el principio "Todo espacio vectorial numerable 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 se restringen a estructuras numerables, mientras que los teoremas de análisis y topología se restringen a espacios separables . [ 9 ] 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 numerable tiene una clausura algebraica" es demostrable en RCA 0 , el sistema más débil que se emplea típicamente en matemáticas inversas. [ 10 ]
Uso de aritmética de orden superior
Una línea de investigación reciente en matemáticas inversas de orden superior , iniciada por Ulrich Kohlenbach en 2005, se centra en subsistemas de aritmética de orden superior . [ 11 ] 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 mapea secuencias binarias a secuencias binarias y que también satisface la definición usual 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 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 demuestran las mismas oraciones de segundo orden (o un gran subconjunto) que los sistemas originales de segundo orden. [ 12 ] Por ejemplo, la teoría base de las matemáticas inversas de orden superior, llamada RCA ω 0 , demuestra las mismas oraciones que RCA 0 , salvo 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 orden superior: por un lado, cuando se restringe a recubrimientos numerables/el lenguaje de la aritmética de segundo orden, la compacidad del intervalo unitario es demostrable en WKL 0 de la siguiente sección. Por otro lado, dados recubrimientos no numerables/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). [ 13 ] Otros lemas de recubrimiento (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 los conjuntos de números naturales. Muchos objetos matemáticos, como anillos , grupos y cuerpos numerables , así como puntos en espacios polacos efectivos , pueden representarse como conjuntos de números naturales, y módulo esta representación puede estudiarse en la aritmética de segundo orden. [ 14 ]
Las matemáticas inversas utilizan varios subsistemas de aritmética de segundo orden. Un teorema típico de matemáticas inversas demuestra 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 del resultado; para que el resultado de matemáticas inversas tenga sentido, este sistema no debe ser capaz de demostrar el teorema matemático T. [ 15 ]
Steve Simpson describe cinco subsistemas particulares de aritmética de segundo orden, que él llama los Cinco Grandes , que aparecen con frecuencia en matemáticas inversas. [ 1 ] [ 16 ] En orden de fuerza creciente, estos sistemas se nombran con las siglas RCA 0 , WKL 0 , ACA 0 , ATR 0 , y Π 1 1 -CA 0 .
La siguiente tabla resume los cinco sistemas principales [ 17 ] y enumera los sistemas contraparte en aritmética de orden superior. [ 12 ] Estos últimos generalmente demuestran las mismas sentencias de segundo orden (o un subconjunto grande) que los sistemas originales de segundo orden. [ 12 ]
El subíndice 0 en estos nombres significa que el esquema de inducción se ha restringido del esquema de inducción de segundo orden completo. [ 15 ] Por ejemplo, ACA 0 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 completa de la aritmética de segundo orden implica el esquema de inducción de segundo orden completo dado por el cierre universal de ( φ (0)∀ n ( φ ( n ) → φ ( n +1))) → ∀ n φ ( n ) para cualquier fórmula de segundo orden φ . Sin embargo, ACA 0 no tiene el axioma de comprensión completo, y el subíndice 0 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 teoría de la demostración significativamente más bajos que los sistemas con el esquema de inducción de segundo orden completo.
Sistema base RCA 0
RCA 0 es el fragmento de aritmética de segundo orden cuyos axiomas son los axiomas de la aritmética de Robinson , el esquema de axiomas de inducción para fórmulas Σ 0 1 y el esquema de axiomas de comprensión para fórmulas Δ 0 1 (también llamado comprensión recursiva). [ 18 ]
El-estados del esquema del axioma de induccióna pesar de-fórmulasque no cuantifican sobre variables de conjunto. Más explícitamente, estas son fórmulas de la formadóndees un-fórmula que puede incluir variables de conjunto. En otras palabras,se obtiene comenzando con una fórmula sin cuantificadores que puede involucrar variables de primer y segundo orden, luego agregando cuantificadores acotados sobre las variables de primer orden y, finalmente, agregando cuantificadores existenciales sobre las variables de primer orden. [ 19 ]
El-El esquema del axioma de comprensión establece quea pesar de-fórmulasy todo-fórmulas. [ 18 ]
El subsistema RCA 0 es el más comúnmente utilizado como sistema base para matemáticas inversas. [ 18 ] Las iniciales "RCA" significan "axioma de comprensión recursiva", donde "recursivo" significa "computable", como en función computable . Este nombre se usa porque RCA 0 corresponde informalmente a "matemáticas computables". En particular, cualquier conjunto de números naturales que se pueda demostrar que existe en RCA 0 es computable, [ 18 ] y por lo tanto cualquier teorema que implique que existen conjuntos no computables no es demostrable en RCA 0. En este sentido, RCA 0 es un sistema constructivo, aunque no cumple con los requisitos del programa del constructivismo porque es una teoría en lógica clásica que incluye la ley del tercero excluido .
A pesar de su aparente debilidad (al no demostrar la existencia de conjuntos no computables), RCA 0 es suficiente para demostrar varios teoremas clásicos que, por lo tanto, requieren una mínima fuerza lógica. Estos teoremas están, en cierto sentido, fuera del alcance de la matemática inversa, ya que son demostrables en el sistema base. Los teoremas clásicos demostrables en RCA 0 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 numerables). [ 20 ]
- El teorema de la categoría de Baire para un espacio métrico separable completo (la condición de separabilidad es necesaria incluso para enunciar el teorema en el lenguaje de la aritmética de segundo orden). [ 21 ]
- El teorema del valor intermedio en funciones reales continuas. [ 22 ]
- El teorema de Banach-Steinhaus para una sucesión de operadores lineales continuos en espacios de Banach separables. [ 23 ]
- Una versión débil del teorema de completitud de Gödel (para un conjunto de oraciones, en un lenguaje numerable, que ya es cerrado bajo consecuencia).
- La existencia de una clausura algebraica para un cuerpo numerable (pero no su unicidad). [ 24 ]
- La existencia y unicidad del cierre real de un cuerpo ordenado numerable. [ 25 ]
La parte de primer orden de RCA 0 (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 Σ 0 1. [ 26 ] Es demostrablemente consistente, al igual que RCA 0 , en la aritmética de Peano completa de primer orden.
Lema débil de Kőnig WKL 0
El subsistema WKL 0 consta de RCA 0 más una forma débil del lema de Kőnig , a saber, la afirmación de que todo 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, conocida como lema débil de Kőnig , es fácil de enunciar en el lenguaje de la aritmética de segundo orden. [ 27 ]
En aritmética de primer orden, WKL 0 se define más fácilmente añadiendo el esquema axiomático de separación Σ 0 1 : dadas dos fórmulas Σ 0 1 de una variable libre n que son excluyentes, existe un conjunto que contiene todos los n que satisfacen una y ningún n que satisface la otra. En símbolos:a pesar de-fórmulas. [ 27 ]
La terminología es algo confusa, ya que el lema débil de Kőnig en sí, como esquema axiomático, también se escribe como WKL, mientras que WKL 0 representa un sistema, no una variante del esquema axiomático WKL. [ 27 ]
(La parte de primer orden de RCA 0 ) + (-comprensión) + (-separación) juntos implica (-comprensión). [ 1 ] : Lema IV.4.4
En cierto sentido, el lema débil de Kőnig es una forma del axioma de elección (aunque, como se indicó, puede demostrarse 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". [ 28 ]
Para demostrar que WKL 0 es en realidad más fuerte que (no demostrable en) RCA 0 , observe que WKL 0 implica la existencia de conjuntos separadores para conjuntos recursivamente enumerables computacionalmente inseparables . En particular, uno puede simplemente escribir dos-fórmulasque definen tales dos conjuntos, entonces WKL 0 prueba que existe algúnque los separa, mientras que el modelo estándar de RCA 0 contiene solo conjuntos computables y, por lo tanto, no existe tal conjunto separador. [ 29 ]
Resulta que RCA 0 y WKL 0 tienen la misma parte de primer orden, lo que significa que demuestran las mismas proposiciones de primer orden. Sin embargo, WKL 0 puede demostrar un buen número de resultados matemáticos clásicos que no se derivan de RCA 0. Estos resultados no se pueden expresar como proposiciones de primer orden, pero sí como proposiciones de segundo orden. [ 28 ]
Los siguientes resultados son equivalentes al lema débil de Kőnig y, por lo tanto, a WKL 0 sobre RCA 0 :
- El teorema de Heine-Borel para el intervalo real unitario cerrado, en el siguiente sentido: toda cobertura mediante una sucesión de intervalos abiertos tiene una subcobertura finita.
- El teorema de Heine-Borel para espacios métricos separables, completos y 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 compacto separable, como se indicó anteriormente) 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 de Riemann .
- El teorema del punto fijo de Brouwer (para funciones continuas en un n -símplex). [ 30 ]
- El teorema separable de Hahn-Banach se formula de la siguiente manera: 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 numerable).
- Determinación para juegos abiertos (o incluso clopen) en {0, 1} de longitud ω.
- Todo anillo conmutativo numerable tiene un ideal primo .
- Todo cuerpo contable formalmente real es ordenable.
- Unicidad del cierre algebraico (para un cuerpo numerable).
- El teorema de De Bruijn–Erdős para grafos numerables: todo grafo numerable cuyos subgrafos finitos son k -coloreables es k -coloreable. [ 31 ]
Comprensión aritmética ACA 0
El sistema ACA 0 añade a RCA 0 el esquema de comprensión para fórmulas aritméticas, también llamado axioma de comprensión aritmética (aunque es un esquema axiomático). Es decir, ACA 0 nos permite formar el conjunto de números naturales que satisfacen una fórmula aritmética arbitraria (una sin variables de conjunto ligadas, aunque posiblemente contenga parámetros de conjunto). [ 32 ] Una fórmula aritmética es una fórmula donde las variables de conjunto pueden aparecer como parámetros, pero no cuantificadas. En otras palabras, es la unión.
En símbolos:para todas las fórmulas aritméticas. También posee el axioma de inducción restringida (no un esquema axiomático):Esto es menos restringido en comparación con el-Esquema del axioma de inducción utilizado en WKL 0 y RCA 0 , pero aún restringido en comparación con el esquema completo del axioma de inducción:para todas las fórmulasen aritmética de segundo orden. Específicamente, el esquema completo del axioma de inducción no es necesariamente derivable, porque ACA 0 puede ser incapaz de demostrar quese puede comprender. Es decir, hay algunas fórmulas, de tal manera queno es demostrable en ACA 0 .
De hecho, basta con añadir a RCA 0 el esquema de comprensión para-fórmulas, ya que entonces se puede tomar la negación lógica para obtener comprensión para-fórmulas, e iterar esto para obtener la comprensión de todos los niveles en la jerarquía aritmética. [ 33 ]
La parte de primer orden de ACA 0 es exactamente la aritmética de Peano de primer orden. En otras palabras, ACA 0 es una extensión conservadora de la aritmética de Peano de primer orden. [ 34 ] Los dos sistemas son demostrablemente equiconsistentes (en un sistema débil). ACA 0 puede considerarse un marco de matemáticas predicativas , aunque existen teoremas demostrables predicativamente que no son demostrables en ACA 0. 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 0 es más fuerte que WKL 0 es exhibir un modelo de WKL 0 que no contenga todos los conjuntos aritméticos. De hecho, es posible construir un modelo de WKL 0 que consista enteramente en conjuntos bajos usando el teorema de la base baja , ya que los conjuntos bajos en relación con otros conjuntos bajos son bajos.
Las siguientes afirmaciones son equivalentes a ACA 0 sobre RCA 0 :
- La completitud secuencial de los números reales (toda secuencia creciente acotada de números reales tiene un límite). [ 35 ]
- El teorema de Bolzano-Weierstrass . [ 35 ]
- Teorema de Ascoli : toda sucesión equicontinua y acotada de funciones reales en el intervalo unitario tiene una subsucesión uniformemente convergente.
- Todo cuerpo numerable se incrusta isomórficamente en su clausura algebraica. [ 36 ]
- Todo anillo conmutativo numerable tiene un ideal maximal . [ 37 ]
- Todo espacio vectorial numerable sobre los racionales (o sobre cualquier cuerpo numerable) tiene una base. [ 38 ]
- Para cualesquiera cuerpos numerables K ⊆ L , existe una base de trascendencia para L sobre K . [ 39 ]
- Lema de Kőnig (para árboles arbitrarios con ramificación finita, a diferencia de la versión débil descrita anteriormente). [ 40 ]
- Para cualquier grupo numerable G y cualesquiera subgrupos H , I de G , existe el subgrupo generado por H ∪ I. [ 41 ] pág. 40
- Cualquier función parcial puede extenderse a una función total. [ 42 ]
- Lema de Higman . [ 43 ]
- Varios teoremas en combinatoria, como ciertas formas del teorema de Ramsey . [ 44 ] [ 40 ]
Recursión transfinita aritmética ATR 0
El sistema ATR 0 añade a ACA 0 un esquema axiomático denominado recursión transfinita aritmética. De manera informal, establece que cualquier funcional aritmético puede iterarse de forma transfinita a lo largo de cualquier ordenación de pozo numerable , partiendo de cualquier conjunto.
El esquema axiomático de la recursión transfinita aritmética tiene un axioma por fórmula aritmética.El axioma establece que: Sies un conjunto bien ordenado, entonces existe algún, que es un conjunto indexado porobtenido mediante una inducción bien ordenada en:
- El conjunto completo esCada entrada indexada tiene el siguiente formato: :(n,a)\in Y\}} . Cada segmento inicial tiene la forma.
- En particular, el segmento inicial más bajo está vacío:.
- La inducción bien ordenada comienza eny procede por inducción: :\theta (n,Y^{a},{\vec {x}},{\vec {X}})\}}
ATR 0 es equivalente sobre ACA 0 al principio de separación Σ 1 1. ATR 0 es impredicativo y tiene el ordinal de la teoría de la demostración Γ 0 , el supremo del de los sistemas predicativos.
ATR 0 prueba la consistencia de ACA 0 y, por lo tanto, según el teorema de Gödel, es estrictamente más fuerte.
Las siguientes afirmaciones son equivalentes a ATR 0 sobre RCA 0 :
- Dos ordenamientos de pozos numerables cualesquiera son comparables. Es decir, son isomorfos o uno es isomorfo a un segmento inicial propio del otro. [ 45 ]
- Teorema de Ulm para grupos abelianos reducidos numerables.
- El teorema del conjunto perfecto , que establece que todo subconjunto cerrado no numerable de un espacio métrico separable completo contiene un conjunto cerrado perfecto.
- Teorema de separación de Lusin (esencialmente separación Σ 1 1 ). [ 46 ]
- Determinación para conjuntos abiertos en el espacio de Baire .
Π 1 1 comprensión Π 1 1 -CA 0
Π 1 1 -CA 0 es más fuerte que la recursión transfinita aritmética y es totalmente impredicativa. Consiste en RCA 0 , más el axioma de inducción.más el esquema de comprensión para las fórmulas Π 1 1 .
A-la fórmula es de la forma, dóndees una fórmula aritmética.La comprensión es el esquema axiomático que establecea pesar de-fórmulas.
En cierto sentido, la comprensión Π 1 1 -CA 0 es a la recursión transfinita aritmética ( separación Σ 1 1 ) como ACA 0 es al lema débil de Kőnig ( separación Σ 0 1 ). Es equivalente a varias afirmaciones de la teoría descriptiva de conjuntos cuyas demostraciones utilizan argumentos fuertemente impredicativos; esta equivalencia muestra que estos argumentos impredicativos no pueden eliminarse.
Los siguientes teoremas son equivalentes a Π 1 1 -CA 0 sobre RCA 0 :
- El teorema de Cantor-Bendixson (todo conjunto cerrado de números reales es la unión de un conjunto perfecto y un conjunto numerable). [ 47 ]
- La dicotomía de Silver (toda relación de equivalencia coanalítica tiene o bien un número numerable de clases de equivalencia o bien un conjunto perfecto de incomparables) [ 48 ]
- Todo grupo abeliano numerable es la suma directa de un grupo divisible y un grupo reducido. [ 49 ]
- Determinación para Σ 0 1Π 0 1 juegos. [ 50 ]
Sistemas adicionales
- Se pueden definir sistemas más débiles que la comprensión recursiva. El sistema débil RCA * 0 consiste en aritmética de funciones elementales EFA (los axiomas básicos más inducción Δ 0 0 en el lenguaje enriquecido, con una operación exponencial) más comprensión Δ 0 1. Sobre RCA * 0 , la comprensión recursiva tal como se definió anteriormente (es decir, con inducción Σ 0 1 ) es equivalente a la afirmación de que un polinomio (sobre un cuerpo numerable) tiene solo un número finito de raíces y al teorema de clasificación para grupos abelianos finitamente generados. El sistema RCA * 0 tiene el mismo ordinal de teoría de la demostración ω 3 que EFA y es conservador sobre EFA para oraciones Π 0 2 .
- El lema débil de Kőnig es la afirmación de que un subárbol del árbol binario infinito sin 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 es no vacío (esto no es demostrable en RCA 0 ). WWKL 0 se obtiene adjuntando este axioma a RCA 0 . 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 0 está estrechamente relacionada con la teoría de secuencias aleatorias algorítmicas . En particular, un ω-modelo de RCA 0 satisface el lema débil de Kőnig si y solo si para cada conjunto X hay un conjunto Y que es 1-aleatorio con respecto a X .
- DNR (abreviatura de "diagonalmente no recursivo") añade a RCA 0 un axioma que afirma la existencia de una función diagonalmente no recursiva con respecto a cada conjunto. Es decir, DNR establece 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 Δ 1 1 es, en ciertos aspectos, análoga a la recursión transfinita aritmética, así 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 la comprensión Δ 1 1 , pero no a la inversa.
- La elección Σ 1 1 establece que si η ( n , X ) es una fórmula Σ 1 1 tal que para cada n existe un X que satisface η, entonces existe una sucesión de conjuntos X n tal que η ( n , X n ) se cumple para cada n . La elección Σ 1 1 también tiene los conjuntos hiperaritméticos como modelo ω mínimo. La recursión transfinita aritmética demuestra la elección Σ 1 1 , pero no a la inversa.
- HBU (abreviatura de "Heine-Borel no numerable") expresa la compacidad (de cubierta abierta) del intervalo unitario, que involucra cubiertas no numerables . Este último aspecto de HBU hace que solo pueda expresarse 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 cubierta debida a Cousin y Lindelöf . HBU es difícil de demostrar: en términos de la jerarquía usual de axiomas de comprensión, una demostración de HBU requiere aritmética completa de segundo orden. [ 13 ]
- El teorema de Ramsey para grafos infinitos no se incluye en ninguno de los cinco subsistemas principales, y existen muchas otras variantes más débiles con diferentes niveles de solidez en su demostración. [ 44 ]
Sistemas más robustos
Al añadir el esquema completo del axioma de inducción de segundo orden a RCA 0 se obtiene RCA, el sistema de aritmética de comprensión recursiva con inducción no restringida. De manera similar, al añadir el esquema completo del axioma de inducción de segundo orden a WKL 0 se obtiene WKL, etc.
Sobre RCA 0 , la recursión transfinita Π 1 1 , la determinabilidad ∆ 0 2 y el teorema de Ramsey ∆ 1 1 son todos equivalentes entre sí.
Sobre RCA 0 , la inducción monótona Σ 1 1 , la determinación Σ 0 2 y el teorema de Ramsey Σ 1 1 son todos equivalentes entre sí.
Los siguientes son equivalentes: [ 51 ] [ 52 ]
- (esquema) Π 1 3 consecuencias de Π 1 2 -CA 0
- Determinación RCA 0 + (esquema sobre n finito ) en el n -ésimo nivel de la jerarquía de diferencias de Σ 0 2 conjuntos
- RCA 0 + { τ : τ es una oración S2S verdadera }
El conjunto de consecuencias Π 1 3 de la aritmética de segundo orden Z 2 tiene la misma teoría que la determinabilidad RCA 0 + (esquema sobre n finito ) en el n -ésimo nivel de la jerarquía de diferencias de los conjuntos Σ 0 3. [ 53 ]
Para un conjunto parcialmente ordenado P , sea MF( P ) el espacio topológico formado por los filtros en P cuyos conjuntos abiertos son conjuntos de la forma { F ∈ MF( P ) | p ∈ F } para algún p ∈ P . La siguiente afirmación es equivalente aencima: para cualquier poset numerable P , el espacio topológico MF( P ) es completamente metrizable si y solo si es regular . [ 54 ]
Modelos ω y modelos β
La ω en el modelo ω representa el conjunto de 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ónde 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 S. Existe un modelo ω estándar donde simplemente se toma S como compuesto por todos los subconjuntos de los enteros. Sin embargo, algunas teorías tienen otros modelos ω . Por ejemplo, RCA 0 tiene un modelo ω mínimo donde S consiste en los subconjuntos computables de ω . En particular, este modelo tiene solo una cantidad numerable de subconjuntos, que es estrictamente menor que la cantidad no numerable..
Un modelo β es un modelo ω que coincide con el modelo ω estándar en cuanto a la veracidad de las oraciones Π 1 1 y Σ 1 1 (con parámetros).
Los modelos que no dependen de ω también son útiles, especialmente en las demostraciones de teoremas de conservación.
Matemáticas inversas constructivas
La matemática inversa constructiva es un programa que se aplica a la matemática constructiva [ 55 ] y se utiliza para clasificar teoremas mediante principios lógicos , axiomas de existencia de funciones y sus combinaciones [ 56 ] . Implica clasificar teoremas en cuatro sistemas principales: BISH (matemática constructiva al estilo Bishop), CLASS, INT y RUSS [ 57 ] .
Véase también
Referencias
- 1 2 3 4 5 6 Simpson 2009 .
- ↑ Harvey Friedman ( 1975 , 1976 )
- ↑ H. Friedman, Algunos sistemas de aritmética de segundo orden y su uso (1974), Actas del Congreso Internacional de Matemáticos
- ↑ Simpson 2009 , págs. 25, 33.
- 1 2 Simpson 2009 , pág. 1.
- ↑ Simpson 2009 , pág. 4.
- ↑ Simpson 2009 , pág. 8.
- ↑ Simpson 2009 , pág. 9.
- ↑ Simpson 2009 , págs. 36–37.
- ↑ Simpson 2009 , pág. 27.
- ↑ Kohlenbach (2005) .
- 1 2 3 Véase Kohlenbach (2005) y Hunter (2008) .
- ^ Normann y Sanders (2018) .
- ↑ Simpson 2009 , págs. 1–2.
- 1 2 Simpson 2009 , pág. 6.
- ↑ Simpson afirma no haberinventado el término. [ Simpson, S.; Eastaugh, B.; Dean, W. (17 de junio de 2022). "Panel Discussion" . YouTube . París, Francia: Universidad de Chicago, Matemáticas inversas y su filosofía.]
- ↑ Simpson 2009 , pág. 42.
- 1 2 3 4 Simpson 2009 , pág. 23.
- ↑ Simpson 2009 , pág. 22.
- ↑ Simpson 2009 , Sección II.4.
- ↑ Simpson 2009 , Teorema II.5.8.
- ↑ Simpson 2009 , Teorema II.6.6.
- ↑ Simpson 2009 , Teorema II.10.8.
- ^ Simpson 2009 , II.9.4–II.9.8.
- ↑ Simpson 2009 , II.9.5, II.9.7.
- ↑ Simpson 2009 , Corolario IX.1.11.
- 1 2 3 Simpson 2009 , pág. 35.
- 1 2 Simpson 2009 , pág. 36.
- ↑ Simpson 2009 , pág. 34.
- ↑ Simpson 2009 , Teorema IV.7.7.
- ↑ Schmerl, James H. (2000). "Coloración de grafos y matemáticas inversas". Mathematical Logic Quarterly . 46 (4): 543– 548. doi : 10.1002/1521-3870(200010)46:4 < 543::AID-MALQ543 > 3.0.CO ; 2-E . MR 1791549 .
- ↑ Simpson 2009 , págs. 6–7.
- ↑ Simpson 2009 , Lema III.1.3.
- ↑ Simpson 2009 , Corolario IX.1.6.
- 1 2 Simpson 2009 , Teorema III.2.2.
- ↑ Simpson 2009 , Teorema III.3.2.
- ↑ Simpson 2009 , Teorema III.5.5.
- ↑ Simpson 2009 , Teorema III.4.3.
- ↑ Simpson 2009 , Teorema III.4.6.
- 1 2 Simpson 2009 , Teorema III.7.2.
- ↑ S. Takashi, " Matemáticas inversas y sistemas algebraicos contables ". Tesis doctoral, Universidad de Tohoku, 2016.
- ↑ 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.
- ↑ Simpson 2009 , Teorema X.3.22.
- 1 2 Hirschfeldt (2014) .
- ↑ Simpson 2009 , Teorema V.6.8.
- ↑ Simpson 2009 , Teorema V.5.1.
- ↑ Simpson 2009 , Ejercicio VI.1.7.
- ↑ Simpson 2009 , Teorema VI.3.6.
- ↑ Simpson 2009 , Teorema VI.4.1.
- ↑ Simpson 2009 , Teorema VI.5.4.
- ↑ Kołodziejczyk, Leszek; Michalewski, Henryk (2016). ¿Hasta qué punto es imposible de demostrar 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 .
- ↑ Kołodziejczyk, Leszek (19 de octubre de 2015). "Pregunta sobre la capacidad de decisión de S2S" . FOM.
- ↑ Montalban, Antonio; Shore, Richard (2014). "Los límites de la determinatividad en la aritmética de segundo orden: consistencia y fuerza de complejidad". Israel Journal of Mathematics . 204 : 477–508 . doi : 10.1007/s11856-014-1117-9 . S2CID 287519 .
- ↑ C. Mummert, SG Simpson. "Matemáticas inversas ycomprensión". En Boletín de Lógica Simbólica vol. 11 (2005), págs. 526–533.
- ↑ Bridges, Douglas; Ishihara, Hajime; Schwichtenberg, Helmut; Rathjen, Michael, eds. (2023), «Una introducción a las matemáticas inversas constructivas» , Manual de matemáticas constructivas , Enciclopedia de matemáticas y sus aplicaciones, Cambridge: Cambridge University Press, pp. 636–660 , ISBN 978-1-316-51086-5, recuperado el 15 de abril de 2026
- ↑ Diener, Hannes (abril de 2020). "Matemáticas inversas constructivas". arXiv : 1804.05495 [ math.LO ].
- ↑ Diener, Hannes (2020-04-04). "Matemáticas inversas constructivas". arXiv : 1804.05495 [ math.LO ].
Referencias/Lecturas adicionales
- 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 , Montreal: Congreso Canadiense de Matemáticas, 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 , Lecture Notes Series of the Institute for Mathematical Sciences, National University of Singapore, 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) , Notas 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 la importancia matemática 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 , Perspectivas en lógica (2.ª ed.), Cambridge University Press , doi : 10.1017/CBO9780511581007 , ISBN 978-0-521-88439-6, MR 2517689
- Stillwell, John (2018), Matemáticas inversas: demostraciones desde 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
- Dzhafarov, Damir D.; Mummert, Carl (2022), Matemáticas inversas: problemas, reducciones y demostraciones , Teoría y aplicaciones de la computabilidad (1.ª ed.), Springer Cham, pp. XIX, 488, doi : 10.1007/978-3-031-11367-3 , ISBN 978-3-031-11367-3
Enlaces externos
- Página principal de Stephen G. Simpson
- Zoológico de Matemáticas Inversas
- teoría de la computabilidad
- Lógica matemática
- Teoría de la demostración