¿Por qué es imposible definir la multiplicación en la aritmética de Presburger?

Question

La aritmética de Peano define la multiplicación de forma recursiva como:

$$\begin{gather}a\cdot0=a\\a\cdot S(b)=a+(a\cdot b)\end{gather}$$

¿Por qué esto no es posible en la aritmética de Presburger?

Answer 1

Existe diferencia entre la definición por recursión y la definición aritmética (o definición explícita). Una operación n-aria $F$ está definida aritméticamente si y solo si hay una fórmula $\varphi(x_1, \ldots, x_n, y)$ con $x_1, \ldots, x_n, y$ libres, que no contenga ningún otro símbolo que primitivo y previamente definido y tal que la equivalencia: \[ F(x_1, \ldots, x_n) = y \longleftrightarrow \varphi(x_1, \ldots, x_n, y) \] se cumpla (en este caso, la equivalencia en cuestión debe cumplirse en el modelo estándar de la aritmética). Como MJD escribió en el comentario anterior, puedes agregar la caracterización recursiva de la multiplicación a la Aritmética de Presburger, pero el sistema resultante ya no es Aritmética de Presburger. Y no puedes definir aritméticamente la multiplicación a partir de otros primitivos en la aritmética de Presburger.

EDITAR: Corregidos algunos errores menores y de estilo.

Answer 2

La aritmética de Peano en realidad no define la multiplicación. La existencia de la multiplicación es un axioma en el sistema de Peano. La definición recursiva de la multiplicación que proporcionas en la pregunta no puede probar la existencia de la función de multiplicación para todos los números (aunque puede hacerlo para cualquier valor finito de $n$ y $m$). Hay dos formas de solucionarlo:

1. Usar la definición recursiva que proporcionas, y asumir que una función con estas propiedades existe (es decir, la existencia de la multiplicación es un axioma).
2. Agregar el Teorema de Recursión como un axioma y usarlo para probar la existencia de la multiplicación.

Ninguno de estos axiomas existe en la aritmética de Presburger, por lo que no es posible definir la multiplicación en la aritmética de Presburger sin extenderla.

Nota: La razón por la que el Teorema de Recursión se llama teorema y no axioma es porque puede demostrarse en la teoría de conjuntos ZF. Pero si tus únicos axiomas son los axiomas de Peano, no se puede demostrar y debe ser su propio axioma.

Una buena explicación de las complejidades de definir la multiplicación en la aritmética de Peano se puede encontrar en este blog: Cómo se define realmente la multiplicación en la aritmética de Peano

Answer 3

Cuando la gente hoy en día dice 'aritmética', más que al contenido en sí se están refiriendo generalmente a un Sistema Formal interpretado (https://en.wikipedia.org/wiki/Formal_system) que incluye un conjunto de axiomas (por ejemplo, los axiomas de la aritmética), un aparato deductivo (generalmente solo modus ponens) y un lenguaje particular (generalmente lógica de primer orden).

Existen dos aspectos al definir funciones, semántico y sintáctico, el mapeo abstracto y sus representaciones; la función factorial es un buen ejemplo. En un entorno de Sistema Formal, 'definir' significa definición formal, una sustitución normalmente de un símbolo, el definiendum, por un conjunto de otros, el definiens, que sin el alfabeto necesario (un símbolo para el definiendum) no se puede hacer.

Por otro lado, cualquier persona que haya leído el papel de Incompletitud de Gödel tendrá la misma pregunta que FUZxxl. La firma de Gödel contiene alfabetos de funciones solo para el sucesor y el cero, s y 0, menos que los de la Aritmética de Presburger, aunque presume el uso de igualdad, adición, multiplicación y otras funciones. Esto se debe a que también se incluyen en la firma de Gödel variables de orden superior, 1, 2, 3, … que permiten una definición formal de igualdad:

(a = b) 1[1(a) 1(b)]

(13.01, Principia Mathematica, página 176), así como adición y multiplicación:

(a+b = c) 1[x y (1(x,0) = x 1(x,sy) = s1(x,y)) 1(a,b) = c]

(a×b = c) 1[x y (1(x,0) = 0 1(x,y) + x = 1(x,sy)) 1(a,b) = c]

(Foundations without Foundationalism, página 120). Gödel bien podría haber evitado esta complicación (como las exposiciones comunes de la Incompletitud de Gödel hacen, ¡sin explicación!) simplemente incluyendo los símbolos necesarios en su firma, pero podría haber querido ser más fiel a la austeridad Logicista que, siempre que sea posible, elimina los símbolos no lógicos {+, , =, etc.} a favor de los lógicos {,, , etc.}.

La Aritmética de Presburger está definida como el Sistema Formal de primer orden de números naturales, con alfabetos no lógicos { 0, +, =}; sin variables de orden superior. La línea de los Axiomas de Peano de Wikipedia (https://en.wikipedia.org/wiki/Peano_axioms)

Un sistema de primer orden más débil llamado aritmética de Peano se obtiene añadiendo explícitamente
los símbolos de operación de adición y multiplicación y reemplazando el segundo orden
axioma de inducción con un esquema de axioma de primer orden.

pierde el punto más amplio de que "Aritmética" en "Aritmética de Peano" no significa aritmética, comúnmente entendida, sino que se refiere al orden del lenguaje en el que se formulan los axiomas de Peano y sus deducciones, un nombre equivocado poco útil.