Predicados recursivos primitivos para exponenciación y multiplicación

Aug 19 2020

Tengo las siguientes creencias declaradas informalmente y débilmente sostenidas, algunas de las cuales me parecen inconsistentes después de reflexionar más. Me pregunto dónde podría estar la fuente de los errores en mi pensamiento; los errores en las definiciones básicas son una posibilidad definitiva.

  1. Es imposible hacer eliminación de cuantificadores en la teoría de primer orden de los números enteros con suma y multiplicación. (Esta es, hasta donde puedo decir, una versión un poco más fuerte del primer teorema de incompletitud).

  2. En la teoría de primer orden de los enteros con suma y multiplicación, es posible definir un predicado recursivo primitivo para la exponenciación. (Por un predicado para la exponenciación, solo me refiero a algo que se comporta como "$Fabc\text{ just when }a^b = c.$")

  3. Es posible hacer eliminación de cuantificadores en la teoría de primer orden de los números enteros con dos operaciones$a \oplus b = \min(a, b)$y$a \otimes b = a + b$(es decir, suma ordinaria de números enteros). Soy consciente de que también necesitamos predicados de divisibilidad y operadores de multiplicación para que los números primos realmente eliminen el cuantificador.

  4. En la teoría de primer orden de los números enteros con las operaciones$\oplus$y$\otimes$, es posible definir un predicado recursivo primitivo para la multiplicación (casi exactamente de la misma manera que el predicado para la exponenciación anterior).


En términos generales, parece que hay una falla en la analogía entre la "torre de operaciones ordinaria"$(+, \times, \hat{\phantom{n}}, \cdots)$y la "torre tropical de operaciones"$(\min, +, \times, \cdots)$.

Más específicamente, si (4) y (3) son verdaderos, no entiendo por qué uno no puede simplemente usar libremente el predicado de multiplicación y luego tener una situación en la que ambos podemos hacer la eliminación del cuantificador (a través de (3)) y no hacer eliminación del cuantificador (a través de (1)). Me sorprendería mucho si (2) fuera cierto pero (4) no lo fuera, y me sorprendería aún más si (2) fuera falso.

Sospecho que no entiendo muy bien lo que significa un predicado de exponenciación (es decir, mi definición informal de$Fabc$es incorrecto, o hay más detalles sobre "usar libremente el predicado de multiplicación" que no conozco.

Respuestas

4 NoahSchweber Aug 19 2020 at 05:54

Tus reclamos$(1), (2)$, y$(3)$cada uno es correcto. Reclamar$(4)$, sin embargo, es incorrecto ; de hecho, si la multiplicación fuera definible sobre$(\mathbb{N};\max,+)$entonces la teoria$Th(\mathbb{N};\max,+)$sería tan complicado como$Th(\mathbb{N};+,\times)$. Pero el primero es recursivo mientras que el segundo ni siquiera es definible aritméticamente.

El problema es que la definición "obvia" de multiplicación en términos de suma no es en realidad de primer orden : las definiciones recursivas no son a priori algo que la lógica de primer orden pueda hacer. En estructuras suficientemente ricas podemos encontrar formas de realizar definiciones recursivas de primer orden, y de hecho es la riqueza de$Th(\mathbb{N};+,\times)$en este sentido, lo que hace posible el eorema de Godel, pero la suma por sí sola no es lo suficientemente poderosa para hacer que esto funcione. La clave es que si tenemos tanto la suma como la multiplicación, podemos "codificar" secuencias finitas de naturales por naturales individuales (por ejemplo, a través de la$\beta$función ) y así hablar de construcciones recursivas al hablar de las secuencias que codifican sus "comportamientos paso a paso", pero con la suma sola ni siquiera podemos codificar pares de números por números individuales .

Profundizando en esa última oración y volviendo a su reclamo$(2)$, aquí hay un esquema de cómo definir la exponenciación usando la suma y la multiplicación de primer orden:

Tenemos$a^b=c$si hay algún número que, cuando se interpreta como una secuencia, tiene una longitud es$b$, Primer periodo$a$, ultimo plazo$c$, y$i+1$º término igual a$a$veces el$i$th término.

Tenga en cuenta que esta es una definición de "todo a la vez" en lugar de una definición por un "proceso recursivo": módulo los detalles de codificar secuencias finitas por números, solo implica cuantificar sobre números individuales y verificar propiedades básicas, que es exactamente lo primero: orden lógica puede hacer. Sin la capacidad de codificar secuencias finitas como números individuales de primer orden, lo cual$(\mathbb{N};\max,+)$carece - estaríamos atascados con la definición habitual que no es de primer orden.

  • Aparte, es importante que esta sea una "definición verificable:" en la teoría$\mathsf{Q}$, que es un pequeño fragmento de la teoría completa$Th(\mathbb{N};+,\times)$, tenemos eso para cada$a,b,c$la frase abreviada por$$\underline{a}^{\underline{b}}=\underline{c}$$(dónde$\underline{k}$es el número que representa al número natural$k$) es demostrable en$\mathsf{Q}$si$a^b=c$y es refutable en$\mathsf{Q}$si$a^b\not=c$. Esto se llama representabilidad y es una de las ideas clave de la prueba de Gödel; de hecho, toda función recursiva es representable .