Aritmética verdadera

En lógica matemática , la aritmética verdadera es el conjunto de todos los enunciados verdaderos 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 aritmética verdadera se denomina ocasionalmente aritmética de Skolem, aunque este término generalmente se refiere a la teoría diferente de los números naturales con multiplicación .

La firma de la aritmética de Peano incluye los símbolos de adición, 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 se construyen a partir de estos símbolos junto con los símbolos lógicos de la manera habitual de la lógica de primer orden .

La estructura se define como un modelo de aritmética de Peano de la siguiente manera. ${\displaystyle {\mathcal {N}}}$

• El dominio del discurso es el conjunto de números naturales,${\displaystyle \mathbb {N}}$
• 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 ,${\displaystyle \mathbb {N}}$
• Los símbolos de igualdad y relación menor que se interpretan como la relación habitual de igualdad y orden en .${\displaystyle \mathbb {N}}$

Esta estructura se conoce como modelo estándar o interpretación intencionada 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 si es verdadera en la estructura que se acaba de definir. La notación se utiliza para indicar que la oración es verdadera en${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}\modelos \varphi }$${\estilo de visualización \varphi}$${\displaystyle {\mathcal {N}}.}$

La aritmética verdadera se define como el conjunto de todas las oraciones en el lenguaje de la aritmética de primer orden que son verdaderas en , escritas como Th( ) . Este conjunto es, equivalentemente, la teoría (completa) de la estructura . ^[2]${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$

El resultado central de la aritmética verdadera es el teorema de indefinibilidad de Alfred Tarski (1936). Éste afirma que el conjunto Th( )${\displaystyle {\mathcal {N}}}$ no es definible aritméticamente. Esto significa que no existe ninguna fórmula en el lenguaje de la aritmética de primer orden tal que, para cada oración θ en este lenguaje, ${\displaystyle \varphi (x)}$

${\displaystyle {\mathcal {N}}\models \theta \quad {\text{if and only if}}\quad {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}}).}$

Aquí está el numeral del número de Gödel canónico de la oración θ . ${\displaystyle {\underline {\#(\theta )}}}$

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( )${\displaystyle {\mathcal {N}}}$ y los grados de Turing , utilizando la jerarquía aritmética . Para cada número natural n , sea Th _n ( )${\displaystyle {\mathcal {N}}}$ el subconjunto de Th( )${\displaystyle {\mathcal {N}}}$ que consiste únicamente en oraciones que están o más abajo 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 mayor que . Por lo tanto, ninguna fórmula única puede definir Th( ) , porque ${\displaystyle \Sigma _{n}^{0}}$${\displaystyle {\mathcal {N}}}$${\displaystyle \Sigma _{n}^{0}}$${\displaystyle {\mathcal {N}}}$

${\displaystyle {\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N}})}$

pero ninguna fórmula única puede definir Th _n ( ) para ${\displaystyle {\mathcal {N}}}$un n arbitrariamente grande .

Como se ha comentado anteriormente, Th( )${\displaystyle {\mathcal {N}}}$ no es definible aritméticamente, según el teorema de Tarski. Un corolario del teorema de Post establece que el grado de Turing de Th( )${\displaystyle {\mathcal {N}}}$ es 0 ^(ω) , por lo que Th( )${\displaystyle {\mathcal {N}}}$ no es decidible ni recursivamente enumerable .

Th( )${\displaystyle {\mathcal {N}}}$ está estrechamente relacionada con la teoría Th( )${\displaystyle {\mathcal {R}}}$ 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( )${\displaystyle {\mathcal {N}}}$ si y sólo si S ( φ ) está en Th( )${\displaystyle {\mathcal {R}}}$ .
• Para cada oración ψ en la firma de órdenes parciales, ψ está en Th( )${\displaystyle {\mathcal {R}}}$ si y sólo si T ( ψ ) está en Th( )${\displaystyle {\mathcal {N}}}$ .

La aritmética verdadera es una teoría inestable , por lo que tiene modelos para cada cardinal incontable . Como hay muchos tipos continuos en el conjunto vacío, la aritmética verdadera también tiene modelos contables. Como la teoría es completa , todos sus modelos son elementalmente equivalentes . ${\displaystyle 2^{\kappa }}$${\displaystyle \kappa }$${\displaystyle 2^{\aleph _{0}}}$

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 . ${\displaystyle {\mathcal {N}}}$${\displaystyle \mathbb {N} }$

La verdadera teoría de la aritmética de primer orden, Th( )${\displaystyle {\mathcal {N}}}$ , es un subconjunto de la verdadera teoría de la aritmética de segundo orden, y Th( )${\displaystyle {\mathcal {N}}}$ es definible en la 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 es definible mediante ninguna 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 los órdenes parciales, y viceversa .

• Boolos, George ; Burgess, John P.; Jeffrey , Richard C. (2002), Computabilidad y lógica (4.ª ed.), Cambridge University Press, ISBN 978-0-521-00758-0.
• Bovykin, Andrey; Kaye, Richard (2001), "Sobre los tipos de orden de los modelos aritméticos", en Zhang, Yi (ed.), Lógica y álgebra , Contemporary Mathematics, vol. 302, American Mathematical Society, págs. 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, vol. 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 irresolubilidad recursiva", Anales de Matemáticas , Segunda serie, 105 (1), Anales de Matemáticas: 121–139, doi :10.2307/1971028, ISSN  0003-486X, JSTOR  1971028, MR  0432435
• Tarski, Alfred (1936), "El principio de verdad en los idiomas formalizados". Una traducción al inglés de "El concepto de verdad en los idiomas formalizados" aparece en Corcoran, J., ed. (1983), Logic, Semantics and Metamathematics: Papers from 1923 to 1938 (2.ª ed.), Hackett Publishing Company, Inc., ISBN 978-0-85-0-332-0 978-0-915144-75-4

• Weisstein, Eric W. "Aritmética". MathWorld .
• Weisstein, Eric W. "Aritmética de Peano". MathWorld .
• Weisstein, Eric W. "Teorema de Tarski". MathWorld .