verdadera aritmética

Conjunto de todos los enunciados verdaderos de primer orden sobre la aritmética de los números naturales.

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 verdadera aritmética ocasionalmente se llama aritmética de Skolem, aunque este término generalmente se refiere a la teoría diferente de los números naturales con la 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 se construyen 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. ${\displaystyle {\mathcal {N}}}$

• El dominio del discurso es el conjunto de los 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 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 si lo es 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}}\models \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {N}}.}$

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

Indefinibilidad aritmética

El resultado central de la aritmética verdadera es el teorema de indefinibilidad de Alfred Tarski (1936). Afirma que el conjunto Th( ) ${\displaystyle {\mathcal {N}}}$ no es definible aritméticamente. Esto significa que no existe una 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 canónico de Gödel de la oración θ . ${\displaystyle {\underline {\#(\theta )}}}$

El teorema de Post es una versión más nítida 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 consta únicamente de 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 aritméticamente definible, pero sólo mediante una fórmula de complejidad superior a . 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}}}$n arbitrariamente grande .

Propiedades de computabilidad

Como se analizó 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 relacionado 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}}}$ .

Propiedades teóricas de modelos

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

Verdadera teoría de la aritmética de segundo orden.

La verdadera teoría de la aritmética de segundo orden consta de todas las oraciones en el lenguaje de la aritmética de segundo orden que se satisfacen con 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}}}$ se puede definir 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 única fórmula en 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 .

Notas

1. Boolos, Burgess y Jeffrey 2002, pág. 295
2. ver teorías asociadas con una estructura
3. Orilla 2011, pag. 184

Referencias

• 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 tipos de orden de modelos de aritmética", en Zhang, Yi (ed.), Lógica y álgebra , Matemáticas contemporáneas, vol. 302, Sociedad Estadounidense de Matemáticas, págs. 275–285, ISBN 978-0-8218-2984-4.
• Shore, Richard (2011), "The recursively enumerable Degrees", en Griffor, ER (ed.), Handbook of Computability Theory , Studies in Logic and the Foundations of Mathematics, vol. 140, Holanda Septentrional (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 , segunda serie, 105 (1), Annals of Mathematics: 121–139, doi :10.2307/1971028, ISSN  0003 -486X, JSTOR  1971028, SEÑOR  0432435
• Tarski, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". Una traducción al inglés "El concepto de verdad en las lenguas formalizadas" aparece en Corcoran, J., ed. (1983), Lógica, semántica y metamatemática: artículos de 1923 a 1938 (2ª ed.), Hackett Publishing Company, Inc., ISBN 978-0-915144-75-4

enlaces externos

• Weisstein, Eric W. "Aritmética". MundoMatemático .
• Weisstein, Eric W. "Aritmética de Peano". MundoMatemático .
• Weisstein, Eric W. "Teorema de Tarski". MundoMatemático .