aritmética de skolem

En lógica matemática , la aritmética de Skolem es la teoría de primer orden de los números naturales con multiplicación , llamada así en honor a Thoralf Skolem . La firma de la aritmética de Skolem contiene sólo la operación de multiplicación y la igualdad, omitiendo por completo la operación de suma.

La aritmética de Skolem es más débil que la aritmética de Peano , que incluye operaciones tanto de suma como de multiplicación. ^[1] A diferencia de la aritmética de Peano, la aritmética de Skolem es una teoría decidible . Esto significa que es posible determinar efectivamente, para cualquier oración en el lenguaje de la aritmética de Skolem, si esa oración es demostrable a partir de los axiomas de la aritmética de Skolem. La complejidad computacional asintótica en tiempo de ejecución de este problema de decisión es triplemente exponencial. ^[2]

Axiomas

Definimos las siguientes abreviaturas.

• un | b  := ∃ n .( an = b )
• Uno( mi ) := ∀ n .( ne = n )
• Prime( p ) := ¬Uno( p ) ∧ ∀ a .( a | p → (Uno( a ) ∨ a = p ))
• PrimePower( p , P ) := Prime( p ) ∧ p | P ∧ ∀ q .(Primo( q ) ∧ ¬( q = p ) → ¬( q | P ))
• InvAdicAbs( p , n , P ) := PrimePower( p , P ) ∧ P | n ∧ ∀Q.((PrimePower( p , Q ) ∧ Q | n ) → Q | P ) [ P es la potencia más grande de p que divide n ]
• AdicAbsDiff _n ( p , a , b ) := Prime( p ) ∧ p | ab ∧ ∃ P .∃ Q .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , Q ) ∧ Q = p ⁿ P ) para cada entero n > 0. [La potencia más grande de p que divide a b es p ⁿ veces la potencia más grande de p que divide a ]

Los axiomas de la aritmética de Skolem son: ^[3]

1. ∀ a .∀ b .( ab = ba )
2. ∀ a .∀ b .∀ c .(( ab ) c = a ( antes de Cristo ))
3. ∃ e .Uno( e )
4. ∀ a .∀ b .(Uno( ab ) → Uno( a ) ∨ Uno( b ))
5. ∀ a .∀ b .∀ c .( ac = antes de Cristo → a = b )
6. ∀ a .∀ b .∀ n .( a ⁿ = b ⁿ → a = b ) para cada número entero n > 0
7. ∀ x .∃ a .∃ r .( x = ar ⁿ ∧ ∀ b .∀ s .( x = bs ⁿ → a | b )) para cada entero n > 0
8. ∀ a .∃ p .(Primo( p ) ∧ ¬( p | a )) [Infinitud de primos]
9. ∀ p .∀ P .∀ Q .((PrimePower( p , P ) ∧ PrimePower( p , Q )) → ( P | Q ∨ Q | P ))
10. ∀ p .∀ n .(Prime( p ) → ∃ P .InvAdicAbs( p , n , P ))
11. ∀ n .∀ m .( n = m ↔ ∀ p .(Prime( p ) → ∃ P .(InvAdicAbs( p , n , P ) ∧ InvAdicAbs( p , m , P )))) [Factorización única]
12. ∀ p .∀ n .∀ m .(Prime( p ) → ∃ P .∃ Q .(InvAdicAbs( p , n , P ) ∧ InvAdicAbs( p , m , Q ) ∧ InvAdicAbs( p , nm , PQ ))) [ p -el valor absoluto ádico es multiplicativo]
13. ∀ a .∀ b .(∀ p .(Prime( p ) → ∃ P .∃ Q .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , Q ) ∧ P | Q )) → a | b ) [Si la valoración p -ádica de a es menor que la de b para cada primo p , entonces a | b ]
14. ∀ a .∀ b .∃ c .∀ p (Prime( p ) → ((( p | a → ∃ P .(InvAdicAbs( p , b , P ) ∧ InvAdicAbs( p , c , P ))) ∧ (( p | b ) → ( p | a )))) [Eliminando de la factorización prima de b todos los primos que no dividen a ]
15. ∀ a .∃ b .∀ p .(Prime( p ) → (∃ P .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , pP ))) ∧ ( p | b → p | a )) ) [Aumentar cada exponente en la factorización prima de a en 1]
16. ∀ a .∀ b .∃ c .∀ p .(Prime( p ) → ((AdicAbsDiff _n ( p , a , b ) → InvAdicAbs( p , c , p )) ∧ ( p | c → AdicAbsDiff _n ( p , a , b ))) para cada número entero n > 0 [Producto de aquellos primos p tales que la mayor potencia de p que divide a b es p ⁿ veces la mayor potencia de p que divide a ]

poder expresivo

La lógica de primer orden con igualdad y multiplicación de números enteros positivos puede expresar la relación . Usando esta relación e igualdad, podemos definir las siguientes relaciones en números enteros positivos: ${\displaystyle c=a\cdot b}$

• Divisibilidad: ${\displaystyle b|c\ \Leftrightarrow \ \exists a.c=a\cdot b}$
• Máximo común divisor : ${\displaystyle d=\gcd(a,b)\ \Leftrightarrow \ d|a\land d|b\land \forall d'.(d'|a\land d'|b)\Rightarrow d'|d}$
• Minimo común multiplo : ${\displaystyle m=\mathrm {lcm} (a,b)\ \Leftrightarrow \ a|m\land b|m\land \forall m'.(a|m'\land b|m')\Rightarrow m|m'}$
• el constante : ${\displaystyle 1}$ ${\displaystyle \forall a.1|a}$
• Número primo : ${\displaystyle \mathrm {prime} (p)\ \Leftrightarrow \ p\neq 1\land \forall a.a|p\Rightarrow (a=1\lor a=p)}$
• El número es un producto de números primos (para un fijo ): ${\displaystyle b}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \exists a_{1},...a_{k}.\ \mathrm {prime} (a_{1})\land \ldots \land \mathrm {prime} (a_{k})\land b=a_{1}\cdot \ldots \cdot a_{k}}$
• El número es una potencia de algún primo: ${\displaystyle b}$ ${\displaystyle \mathrm {ppower} (b)\ \Leftrightarrow \ \exists p.\mathrm {prime} (p)\land \forall a.(a\neq 1\land a|b)\Rightarrow p|a}$
• El número es un producto de potencias exactamente primas: ${\displaystyle b}$ ${\displaystyle k}$ ${\displaystyle \exists a_{1},...a_{k}.\ \mathrm {ppower} (a_{1})\land \ldots \land \mathrm {ppower} (a_{k})\land b=a_{1}\cdot \ldots \cdot a_{k}}$

Idea de decidibilidad

El valor de verdad de las fórmulas de la aritmética de Skolem se puede reducir al valor de verdad de secuencias de números enteros no negativos que constituyen su descomposición en factores primos, y la multiplicación se convierte en una suma puntual de secuencias. La decidibilidad se deriva entonces del teorema de Feferman-Vaught que se puede demostrar mediante la eliminación del cuantificador . Otra forma de afirmar esto es que la teoría de primer orden de enteros positivos es isomorfa a la teoría de primer orden de multiconjuntos finitos de enteros no negativos con la operación de suma de conjuntos múltiples, cuya decidibilidad se reduce a la decidibilidad de la teoría de los elementos.

Con más detalle, según el teorema fundamental de la aritmética , un número entero positivo se puede representar como producto de potencias primas: ${\displaystyle a>1}$

${\displaystyle a=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots }$

Si un número primo no aparece como factor, definimos su exponente como cero. Por lo tanto, sólo un número finito de exponentes son distintos de cero en la secuencia infinita . Denotemos tales secuencias de números enteros no negativos por . ${\displaystyle p_{k}}$ ${\displaystyle a_{k}}$ ${\displaystyle a_{1},a_{2},\ldots }$ ${\displaystyle N^{*}}$

Consideremos ahora la descomposición de otro número positivo,

${\displaystyle b=p_{1}^{b_{1}}p_{2}^{b_{2}}\cdots }$

La multiplicación corresponde a la suma puntual de los exponentes: ${\displaystyle ab}$

${\displaystyle ab=p_{1}^{a_{1}+b_{1}}p_{2}^{a_{2}+b_{2}}\cdots }$

Defina la suma puntual correspondiente en secuencias mediante:

${\displaystyle (a_{1},a_{2},\ldots ){\bar {+}}(b_{1},b_{2},\ldots )=(a_{1}+b_{1},a_{2}+b_{2},\ldots )}$

Por tanto, tenemos un isomorfismo entre la estructura de números enteros positivos con multiplicación y la suma puntual de secuencias de números enteros no negativos en las que sólo un número finito de elementos son distintos de cero . ${\displaystyle (N,\cdot )}$ ${\displaystyle (N^{*},{\bar {+}})}$

Del teorema de Feferman-Vaught para la lógica de primer orden , el valor de verdad de una fórmula lógica de primer orden sobre secuencias y la suma puntual sobre ellas se reduce, de forma algorítmica, al valor de verdad de las fórmulas en la teoría de los elementos de la secuencia con suma, que, en este caso, es la aritmética de Presburger . Como la aritmética de Presburger es decidible, la aritmética de Skolem también lo es.

Complejidad

Ferrante y Rackoff (1979, capítulo 5) establecen, utilizando juegos de Ehrenfeucht-Fraïssé , un método para demostrar los límites superiores de la complejidad de los problemas de decisión de las potencias directas débiles de las teorías. Aplican este método para obtener una complejidad espacial triple exponencial para y, por tanto, de la aritmética de Skolem. ${\displaystyle (N^{*},{\bar {+}})}$

Grädel (1989, Sección 5) demuestra que el problema de satisfacibilidad para el fragmento libre de cuantificadores de la aritmética de Skolem pertenece a la clase de complejidad NP .

Extensiones decidibles

Gracias a la reducción anterior utilizando el teorema de Feferman-Vaught, podemos obtener teorías de primer orden cuyas fórmulas abiertas definen un conjunto mayor de relaciones si fortalecemos la teoría de multiconjuntos de factores primos. Por ejemplo, considere la relación que es verdadera si y sólo si y tienen el mismo número de factores primos distintos: ${\displaystyle a\sim b}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle |\{p\mid \mathrm {prime} (p)\land (p|a)\}|\ =\ |\{p\mid \mathrm {prime} (p)\land (p|b)\}|}$

Por ejemplo, porque ambos lados denotan un número que tiene dos factores primos distintos. ${\displaystyle 2^{10}\cdot 3^{100}\sim 5^{8}\cdot 19^{9}}$

Si sumamos la relación a la aritmética de Skolem, sigue siendo decidible. Esto se debe a que la teoría de conjuntos de índices sigue siendo decidible en presencia del operador de equinumerosidad en conjuntos, como lo muestra el teorema de Feferman-Vaught . ${\displaystyle \sim }$

Extensiones indecidibles

Una extensión de la aritmética de Skolem con el predicado sucesor puede definir la relación de suma usando la identidad de Tarski: ^{[4] [5]} ${\displaystyle succ(n)=n+1}$

${\displaystyle (c=0\lor c=a+b)\Leftrightarrow (ac+1)(bc+1)=c^{2}(ab+1)+1}$

y definir la relación en números enteros positivos por ${\displaystyle c=a+b}$

${\displaystyle \mathrm {succ} (ac)\,\mathrm {succ} (bc)=\mathrm {succ} (c^{2}\mathrm {succ} (ab))}$

Como puede expresar tanto la multiplicación como la suma, la teoría resultante es indecidible.

Si tenemos un predicado ordenante en los números naturales (menor que, ), podemos expresar mediante ${\displaystyle <}$ ${\displaystyle \mathrm {succ} }$

${\displaystyle \mathrm {succ} (a)=b\ \ \Leftrightarrow \ \ a<b\land \forall c.{\big (}a<c\Rightarrow (b=c\lor b<c){\big )}}$

entonces la extensión con también es indecidible. ${\displaystyle <}$

Ver también

• aritmética de presburger
• aritmética de robinson
• Eliminación de cuantificadores

Referencias

1. Nadel 1981.
2. Ferrante y Rackoff 1979, pag. 135.
3. Cegielski 1981.
4. Robinson 1949, pag. 100.
5. Bès y Richard 1998.

Bibliografía

• Bès, Alexis (2001). "Un estudio de definibilidad aritmética" (PDF) . En Crabbé, Marcel; Punto, Françoise; Michaux, Christian (eds.). Un homenaje a Maurice Boffa . Bruselas: Societé mathématique de Belgique. págs. 1–54.

• Bès, Alexis; Richard, Denis (1998). "Extensiones indecidibles de la aritmética de Skolem". Revista de Lógica Simbólica . 63 (2): 379–401. CiteSeerX  10.1.1.2.1139 . doi :10.2307/2586837. JSTOR  2586837. S2CID  14566619.

• Cegielski, Patrick (1981), "Théorie élémentaire de la multiplication des entiers naturalls", en Berlín, Chantal; McAloon, Kenneth; Ressayre, Jean-Pierre (eds.), Teoría de modelos y aritmética , Berlín: Springer, págs.

• Ferrante, Juana; Rackoff, Charles W. (1979). La complejidad computacional de las teorías lógicas. Berlín Heidelberg Nueva York: Springer-Verlag. doi :10.1007/BFb0062837. ISBN 3-540-09501-2.

• Grädel, Erich (junio de 1989). "El dominó y la complejidad de las subclases de teorías lógicas". Anales de lógica pura y aplicada . 43 (1): 1–30. doi : 10.1016/0168-0072(89)90023-7 .

• Nadel, Mark E. (1981). "La integridad de la multiplicación de Peano". Revista Israelí de Matemáticas . 39 (3): 225–233. doi : 10.1007/bf02760851 . Consultado el 8 de septiembre de 2022 .

• Robinson, Julia Hall Bowman (1949). "Problemas de definibilidad y decisión en aritmética" (PDF) . Revista de Lógica Simbólica . 14 (2): 98-114. doi :10.2307/2266510. JSTOR  2266510. S2CID  40861592 . Consultado el 5 de septiembre de 2022 .