En lógica matemática , la verdadera aritmética es el conjunto de todas las declaraciones verdaderas de primer orden sobre la aritmética de los números naturales . [1] Esta es la teoría asociada con el modelo estándar de los axiomas de Peano en el lenguaje de los axiomas de Peano de primer orden. La verdadera aritmética se llama ocasionalmente aritmética de Skolem, aunque este término generalmente se refiere a la diferente teoría de los números naturales con multiplicación.
Definición
La firma de la aritmética de Peano incluye los símbolos de suma, multiplicación y función sucesora, los símbolos de igualdad y relación menor que, y un símbolo constante para 0. Las fórmulas (bien formadas) del lenguaje de la aritmética de primer orden están construidas de estos símbolos junto con los símbolos lógicos en la forma habitual de la lógica de primer orden .
La estructura se define como un modelo de aritmética de Peano de la siguiente manera.
- El dominio del discurso es el conjunto de números naturales,
- El símbolo 0 se interpreta como el número 0,
- Los símbolos de función se interpretan como las operaciones aritméticas habituales en ,
- Los símbolos de igualdad y relación menor que se interpretan como la relación habitual de igualdad y orden en .
Esta estructura se conoce como modelo estándar o interpretación prevista de la aritmética de primer orden.
Se dice que una oración en el lenguaje de la aritmética de primer orden es verdadera ensi es cierto en la estructura que se acaba de definir. La notación se usa para indicar que la oración es cierto en
La verdadera aritmética se define como el conjunto de todas las oraciones en el lenguaje de la aritmética de primer orden que son verdaderas en, escrito Th () . Este conjunto es, de manera equivalente, la teoría (completa) de la estructura. [2]
Indefinibilidad aritmética
El resultado central de la verdadera aritmética es el teorema de indefinibilidad de Alfred Tarski (1936). Afirma que el conjunto Th () no se puede definir aritméticamente. Esto significa que no hay fórmulaen el lenguaje de la aritmética de primer orden de modo que, para cada oración θ en este idioma,
- si y solo si
Aquí es el numeral del número canónico de Gödel de la oración θ .
El teorema de Post es una versión más precisa del teorema de indefinibilidad que muestra una relación entre la definibilidad de Th () y los grados de Turing , utilizando la jerarquía aritmética . Para cada número natural n , sea Th n () ser el subconjunto de Th () que consta solo de oraciones que sono más bajo en la jerarquía aritmética. El teorema de Post muestra que, para cada n , Th n () es definible aritméticamente, pero solo mediante una fórmula de complejidad superior a. Por tanto, ninguna fórmula puede definir Th () , porque
pero ninguna fórmula única puede definir Th n () para n arbitrariamente grande .
Propiedades de computabilidad
Como se discutió anteriormente, Th () no es definible aritméticamente, por el teorema de Tarski. Un corolario del teorema de Post establece que el grado de Turing de Th () es 0 (ω) , por lo que Th () no es decidible ni enumerable de forma recursiva .
Th () está estrechamente relacionado con la teoría Th () de los grados de Turing recursivamente enumerables , en la firma de órdenes parciales . [3] En particular, existen funciones computables S y T tales que:
- Para cada oración φ en la firma de la aritmética de primer orden, φ está en Th () si y solo si S ( φ ) está en Th () .
- Para cada oración ψ en la firma de órdenes parciales, ψ está en Th () si y solo si T ( ψ ) está en Th () .
Propiedades de la teoría de modelos
La verdadera aritmética es una teoría inestable , y también lo ha hecho. modelos para cada cardenal incontable . Como hay muchos tipos continuos sobre el conjunto vacío, la verdadera aritmética también tienemodelos contables. Dado que la teoría está completa , todos sus modelos son elementalmente equivalentes .
Verdadera teoría de la aritmética de segundo orden
La verdadera teoría de la aritmética de segundo orden consiste en todas las oraciones en el lenguaje de la aritmética de segundo orden que son satisfechas por el modelo estándar de la aritmética de segundo orden, cuya parte de primer orden es la estructura. y cuya parte de segundo orden consiste en cada subconjunto de .
La verdadera teoría de la aritmética de primer orden, Th () , es un subconjunto de la verdadera teoría de la aritmética de segundo orden, y Th () es definible en aritmética de segundo orden. Sin embargo, la generalización del teorema de Post a la jerarquía analítica muestra que la verdadera teoría de la aritmética de segundo orden no se puede definir mediante una fórmula única en la aritmética de segundo orden.
Simpson (1977) ha demostrado que la verdadera teoría de la aritmética de segundo orden es computablemente interpretable con la teoría del orden parcial de todos los grados de Turing , en la firma de órdenes parciales, y viceversa .
Notas
- ^ Boolos, Burgess y Jeffrey 2002 , p. 295
- ^ ver teorías asociadas con una estructura
- ^ Shore 2011 , p. 184
Referencias
- Boolos, George ; Burgess, John P .; Jeffrey, Richard C. (2002), Computabilidad y lógica (4a ed.), Cambridge University Press, ISBN 978-0-521-00758-0.
- Bovykin, Andrey; Kaye, Richard (2001), "Sobre tipos de órdenes de modelos de aritmética", en Zhang, Yi (ed.), Logic and algebra , Contemporary Mathematics, 302 , American Mathematical Society, pp. 275-285, ISBN 978-0-8218-2984-4.
- Shore, Richard (2011), "Los grados recursivamente enumerables", en Griffor, ER (ed.), Handbook of Computability Theory , Studies in Logic and the Foundations of Mathematics, 140 , North-Holland (publicado en 1999), págs. 169 –197, ISBN 978-0-444-54701-9.
- Simpson, Stephen G. (1977), "Teoría de primer orden de los grados de insolubilidad recursiva", Annals of Mathematics , Second Series, Annals of Mathematics, 105 (1): 121-139, doi : 10.2307 / 1971028 , ISSN 0003 -486X , JSTOR 1.971.028 , MR 0432435
- Tarski, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". Una traducción al inglés "El concepto de verdad en lenguajes formalizados" aparece en Corcoran, J., ed. (1983), Lógica, semántica y metamatemática: artículos de 1923 a 1938 (2a ed.), Hackett Publishing Company, Inc., ISBN 978-0-915144-75-4
enlaces externos
- Weisstein, Eric W. "Aritmética" . MathWorld .
- Weisstein, Eric W. "Aritmética de Peano" . MathWorld .
- Weisstein, Eric W. "Teorema de Tarski" . MathWorld .