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 firma de la aritmética de Skolem contiene solo la operación de multiplicación y la igualdad, omitiendo la operación de suma por completo.
La aritmética de Skolem es mucho más débil que la aritmética de Peano , que incluye operaciones de suma y multiplicación. 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. Sin embargo, la complejidad computacional asintótica del tiempo de ejecución de este problema de decisión es triplemente exponencial.
Poder expresivo
La lógica de primer orden con igualdad y multiplicación de enteros positivos puede expresar la relación . Usando esta relación e igualdad, podemos definir las siguientes relaciones en enteros positivos:
- Divisibilidad:
- Máximo común divisor :
- Mínimo común múltiplo :
- el constante :
- Número primo :
- Número es un producto de primos (para un fijo ):
- Número es un poder de alguna prima:
- Número es un producto de exactamente poderes primarios:
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 las secuencias de números enteros no negativos que constituyen su descomposición de factores primos, y la multiplicación se convierte en una suma puntual de secuencias. La decidibilidad se deriva 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 los enteros positivos es isomórfica a la teoría de primer orden de los conjuntos múltiples finitos de enteros no negativos con la operación de suma múltiple, cuya decidibilidad se reduce a la decidibilidad de la teoría de los elementos.
Más detalladamente, de acuerdo con el teorema fundamental de la aritmética , un entero positivo se puede representar como un producto de poderes primos:
Si un número primo no aparece como factor, definimos su exponente ser cero. Por lo tanto, solo un número finito de exponentes son distintos de cero en la secuencia infinita. Denote tales secuencias de enteros no negativos por.
Ahora considere la descomposición de otro número positivo,
La multiplicacion corresponde a la suma puntual de los exponentes:
Defina la suma puntual correspondiente en secuencias mediante:
Así tenemos un isomorfismo entre la estructura de enteros positivos con multiplicación, y de la suma puntual de las secuencias de números enteros no negativos en los que sólo un número finito de elementos son distintos de cero, .
Desde el 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 adición puntual de ellas se reduce, de manera algorítmica, al valor de verdad de fórmulas en la teoría de elementos de la secuencia con Además, que, en este caso, es aritmética de Presburger . Debido a que la aritmética de Presburger es decidible, la aritmética de Skolem también lo es.
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 mayor conjunto de relaciones si fortalecemos la teoría de multijuegos de factores primos. Por ejemplo, considere la relación eso es cierto si y solo si y tienen el mismo número de factores primos distintos:
Por ejemplo, porque ambos lados denotan un número que tiene dos factores primos distintos.
Si sumamos la relación para la aritmética de Skolem, sigue siendo decidible. Esto se debe a que la teoría de conjuntos de índices (la estructura del índice en el teorema de Feferman-Vaught) sigue siendo decidible en presencia del operador de equinumerosidad en conjuntos.
Extensiones indecidibles
Una extensión de la aritmética de Skolem con el predicado sucesor, puede definir la relación de adición usando la identidad de Tarski:
y definiendo la relación en enteros positivos por
Debido a que puede expresar tanto la multiplicación como la suma, la teoría resultante es indecidible.
Si tenemos un predicado de ordenamiento en números naturales (menor que, ), podemos expresar por
entonces la extensión con también es indecidible.
Ver también
Referencias
Bès, Alexis (2002). "Una encuesta de definibilidad aritmética" (PDF) . Soc.Math. Belgique, Un tributo a Maurice Boffa : 1-54.