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 , nombrada en honor a Thoralf Skolem . La signatura de la aritmética de Skolem contiene únicamente 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 de suma y 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, para cualquier enunciado en el lenguaje de la aritmética de Skolem, si dicho enunciado es demostrable a partir de los axiomas de la aritmética de Skolem. La complejidad computacional asintótica de este problema de decisión es triplemente exponencial. ^{[ 2 ]}

A continuación definimos las siguientes abreviaturas.

$${\displaystyle {\begin{aligned}a\mid b&:=\exists n\;(a\cdot n=b)\\\operatorname {One} (e)&:=\forall n\;(n\cdot e=n)\\\operatorname {Prime} (p)&:=\lnot \operatorname {One} (p)\land \forall a\;(a\mid p\to (\operatorname {One} (a)\lor a=p))\\\operatorname {PrimePower} (p,P)&:=\operatorname {Prime} (p)\land p\mid P\land \forall q\;(\operatorname {Prime} (q)\land \lnot (q=p)\to \lnot (q\mid P))\\\operatorname {InvAdicAbs} (p,n,P)&:=\operatorname {PrimePower} (p,P)\land P\mid n\land \forall Q\;((\operatorname {PrimePower} (p,Q)\land Q\mid n)\to Q\mid P)\\\operatorname {AdicAbsDiff} _{n}(p,a,b)&:=\operatorname {Prime} (p)\land p\mid ab\land \exists P\,\exists Q\;(\operatorname {InvAdicAbs} (p,a,P)\land \operatorname {InvAdicAbs} (p,b,Q)\land Q=p^{n}P)\end{aligned}}}$$ En lenguaje sencillo:

• ${\displaystyle \operatorname {InvAdicAbs} (p,n,P)}$se cumple si y solo si${\displaystyle P}$es la mayor potencia entera de${\displaystyle p}$que divide${\displaystyle n}$exactamente.

• ${\displaystyle \operatorname {AdicAbsDiff} _{n}(p,a,b)}$se cumple si y solo si la valoración p-ádica de${\displaystyle b}$^{[ 3 ]} excede la valoración p-ádica de${\displaystyle a}$exactamente${\displaystyle n}$, es decir${\displaystyle v_{p}(b)=v_{p}(a)+n}$.

Los axiomas de la aritmética de Skolem son: ^{[ 4 ]}

1. ${\displaystyle \forall a\,\forall b\;(ab=ba)}$
2. ${\displaystyle \forall a\,\forall b\,\forall c\;((ab)c=a(bc))}$
3. ${\displaystyle \exists e\;\operatorname {One} (e)}$
4. ${\displaystyle \forall a\,\forall b\;(\operatorname {One} (ab)\to \operatorname {One} (a)\land \operatorname {One} (b))}$
5. ${\displaystyle \forall a\,\forall b\,\forall c\;(ac=bc\to a=b)}$
6. ${\displaystyle \forall a\,\forall b\;(a^{n}=b^{n}\to a=b){\text{ for each integer }}n>0}$
7. ${\displaystyle \forall x\,\exists a\,\exists r\;(x=ar^{n}\land \forall b\,\forall s\;(x=bs^{n}\to a\mid b)){\text{ for each integer }}n>0}$
8. ${\displaystyle \forall a\,\exists p\;(\operatorname {Prime} (p)\land \lnot (p\mid a))}$^{[ 5 ]}
9. ${\displaystyle \forall p\,\forall P\,\forall Q\;((\operatorname {PrimePower} (p,P)\land \operatorname {PrimePower} (p,Q))\to (P\mid Q\lor Q\mid P))}$
10. ${\displaystyle \forall p\,\forall n\;(\operatorname {Prime} (p)\to \exists P\;\operatorname {InvAdicAbs} (p,n,P))}$
11. ${\displaystyle \forall n\,\forall m\;\left(n=m\leftrightarrow \forall p\;(\operatorname {Prime} (p)\to \exists P\;(\operatorname {InvAdicAbs} (p,n,P)\land \operatorname {InvAdicAbs} (p,m,P)))\right)}$^{[ 6 ]}
12. ${\displaystyle \forall p\,\forall n\,\forall m\;\left(\operatorname {Prime} (p)\to \exists P\,\exists Q\;(\operatorname {InvAdicAbs} (p,n,P)\land \operatorname {InvAdicAbs} (p,m,Q)\land \operatorname {InvAdicAbs} (p,nm,PQ))\right)}$^{[ 7 ]}
13. ${\displaystyle \forall a\,\forall b\;\left(\forall p\;(\operatorname {Prime} (p)\to \exists P\,\exists Q\;(\operatorname {InvAdicAbs} (p,a,P)\land \operatorname {InvAdicAbs} (p,b,Q)\land P\mid Q))\to a\mid b\right)}$^{[ 8 ]}
14. ${\displaystyle \forall a\,\forall b\,\exists c\,\forall p\;\left(\operatorname {Prime} (p)\to \left((p\mid a\to \exists P\;(\operatorname {InvAdicAbs} (p,b,P)\land \operatorname {InvAdicAbs} (p,c,P)))\land (p\mid b\to p\mid a)\right)\right)}$^{[ 9 ]}
15. ${\displaystyle \forall a\,\exists b\,\forall p\;\left(\operatorname {Prime} (p)\to \left(\exists P\;(\operatorname {InvAdicAbs} (p,a,P)\land \operatorname {InvAdicAbs} (p,b,pP))\right)\land (p\mid b\to p\mid a)\right)}$^{[ 10 ]}
16. ${\displaystyle \forall a\,\forall b\,\exists c\,\forall p\;\left(\operatorname {Prime} (p)\to \left((\operatorname {AdicAbsDiff} _{n}(p,a,b)\to \operatorname {InvAdicAbs} (p,c,p))\land (p\mid c\to \operatorname {AdicAbsDiff} _{n}(p,a,b))\right)\right)}$^{[ 11 ]}

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

• 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)}$
• Mínimo común múltiplo :${\displaystyle m=\mathrm {lcm} (a,b)\ \Leftrightarrow \ a|m\land b|m\land \forall m'((a|m'\land b|m')\Rightarrow m|m')}$
• la 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))}$
• Número${\displaystyle b}$es un producto de${\displaystyle k}$primos (para un fijo)${\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})}$
• Número${\displaystyle b}$es un poder de algún primo:${\displaystyle \mathrm {ppower} (b)\ \Leftrightarrow \ \exists p(\mathrm {prime} (p)\land \forall a((a\neq 1\land a|b)\Rightarrow p|a))}$
• Número${\displaystyle b}$es un producto de exactamente${\displaystyle k}$poderes primordiales:${\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})}$

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

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

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

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

Ahora consideremos la descomposición de otro número positivo,

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

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

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

Defina la suma punto por punto 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 )}$

Así, tenemos un isomorfismo entre la estructura de los enteros positivos con la multiplicación,${\displaystyle (N,\cdot )}$y de la suma punto por punto de las secuencias de enteros no negativos en las que solo un número finito de elementos son distintos de cero,${\displaystyle (N^{*},{\bar {+}})}$.

A partir del teorema de Feferman-Vaught para la lógica de primer orden , el valor de verdad de una fórmula de 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 . Dado que la aritmética de Presburger es decidible, la aritmética de Skolem también lo es. ^{[ 12 ]}

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

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

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 reforzamos la teoría de multiconjuntos de factores primos. Por ejemplo, consideremos la relación${\displaystyle a\sim b}$Eso es cierto si y solo si${\displaystyle a}$y${\displaystyle b}$tienen el mismo número de factores primos distintos:

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

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

Si añadimos la relación${\displaystyle \sim }$En cuanto 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 demuestra el teorema de Feferman-Vaught .

Una extensión de la aritmética de Skolem con el predicado sucesor,${\displaystyle succ(n)=n+1}$Se puede definir la relación de adición utilizando la identidad de Tarski: ^{[ 13 ] [ 14 ]}

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

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

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

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

Si tenemos un predicado de ordenación sobre los números naturales (menores que,${\displaystyle <}$), podemos expresar${\displaystyle \mathrm {succ} }$por

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

así que la extensión con${\displaystyle <}$También es indecidible.

• aritmética de Presburger
• aritmética de Robinson
• eliminación de cuantificadores