¿Cuáles son algunos ejemplos de teorías más fuertes que la Aritmética de Presburgo pero más débiles que la Aritmética de Peano?

Question

¿Cuáles son algunos ejemplos de teorías más fuertes que la Aritmética de Presburgo pero más débiles que la Aritmética de Peano? ¿Son todas estas teorías decidibles? Si no lo son, ¿con qué métodos distintos de la Gödelización se puede establecer la indecidibilidad?

EDIT: En ambas respuestas se ha indicado que la Aritmética de Robinson es una teoría intermedia, pero no entiendo cómo puede ser "más fuerte" que la Aritmética de Presburgo de forma razonable, porque la Aritmética de Robinson no puede demostrar la conmutatividad de la suma. He intentado definir "más fuerte" en los comentarios. Agradecería cualquier sugerencia para aclarar la pregunta y esta definición.

Answer 1

La aritmética de Peano es relativamente fuerte, y las teorías decidibles de la aritmética como la de Presburger son bastante inusuales. Aquí hay una "torre" de tres teorías entre las dos, de fuerza creciente:

1. Q de Robinson que es una axiomatización sin inducción de la aritmética, que da la suma y la mutliplicación como sus únicas constantes de función. No puede demostrar la exponenciación total;
2. La aritmética de funciones exponenciales (EFA) tiene un operador de exponenciación y una forma de inducción muy limitada. No puede demostrar la exponenciación iterada (también conocida como tetration ) total;
3. Aritmética recursiva primitiva se axiomatiza a veces como la aritmética de Peano, pero con la inducción restringida a las fórmulas sin cuantificación universal (se da más habitualmente como una teoría puramente ecuacional). No puede demostrar la función total de Ackermann.

Obsérvese que los he distinguido por los operadores aritméticos que tienen y por los que no pueden probar el total. Esta es una medida muy natural de la fuerza de las teorías de la aritmética: una parte esencial de la demostración del teorema de incompletitud es proporcionar una operación de diagonalización, que sólo podemos hacer si tenemos la multiplicación. Estas teorías lo tienen, por lo que todas ellas admiten los teoremas de incompletitud.

Answer 2

Hay infinitas teorías diferentes más fuertes que la aritmética de Presburgo y más débiles que la aritmética de Peano. Los ejemplos clásicos de teorías más débiles que la aritmética de Peano se determinan añadiendo diferentes cantidades de inducción a la aritmética de Robinson.

• El $\Sigma^0_n$ Los axiomas de inducción dicen que cualquier conjunto de números definible por un $\Sigma^0_n$ fórmula que contiene 0 y es cerrada bajo sucesión contiene todo número natural.

• El $\Sigma^0_n$ Los axiomas de limitación dicen que cualquier no hay $\Sigma^0_n$ función definible sobre un segmento inicial acotado de los números naturales con un rango no acotado.

• La teoría Q de la "aritmética de Robinson" consiste en un pequeño número de axiomas sobre las operaciones aritméticas.

• La teoría que $\Sigma^0_n$ es Q más el $\Sigma^0_n$ axiomas de inducción.

• La teoría B $\Sigma^0_n$ es Q más el $\Sigma^0_n$ axiomas de delimitación.

Se sabe que, para cada $n$ , I $\Sigma^0_{n+1}$ implica B $\Sigma^0_{n+1}$ lo que a su vez implica que I $\Sigma^0_n$ y las implicaciones son todas estrictas.

Ninguna de estas teorías es decidible, como tampoco lo es ninguna otra extensión consistente de la aritmética de Robinson. El primer teorema de incompletitud se aplica a todas estas teorías.

La demostración estándar del segundo teorema de incompletitud se aplica a todas las teorías I $\Sigma^0_1$ y más fuerte. El segundo teorema de incompletitud puede demostrarse también para algunos sistemas más débiles, pero las cosas se vuelven muy técnicas para sistemas más débiles que I $\Sigma^0_1$ .

Answer 3

La teoría de primer orden de $(\mathbb{N},+,|_2)$ (aquí $x |_2 y$ significa que $x$ es una potencia de $2$ y que $x$ divide $y$ ) es decidible. Esto se puede demostrar utilizando autómatas. Nótese que el conjunto de potencias de 2 es obviamente definible como $x |_2 x$ .

Además, hay muchas expansiones decidibles concretas. Esto se puede ver de la siguiente manera: 1) esta teoría de primer orden es bi-interpretable con la teoría débil monádica de segundo orden de $(\mathbb{N},n \mapsto n+1)$ . Así, las expansiones decidibles de una inducen expansiones decidibles de la otra; 2) hay muchas expansiones decidibles concretas de la teoría monádica de segundo orden de $(\mathbb{N},n \mapsto n+1)$ mediante predicados unarios. Por ejemplo, todo predicado mórfico (como la palabra Thue-Morse).

Para una caracterización de las expansiones decidibles ver:

Alexander Rabinovich Sobre la decidibilidad de la lógica monádica de orden sobre los naturales extendida por predicados monádicos. Inf. Comput. 205(6): 870-889 (2007)