Concept
In mathematical logic, Skolem arithmetic is the first-order theory of the natural numbers with multiplication, named in honor of Thoralf Skolem. The signature of Skolem arithmetic contains only the multiplication operation and equality, omitting the addition operation entirely. Skolem arithmetic is weaker than Peano arithmetic, which includes both addition and multiplication operations. Unlike Peano arithmetic, Skolem arithmetic is a decidable theory. This means it is possible to effectively determine, for any sentence in the language of Skolem arithmetic, whether that sentence is provable from the axioms of Skolem arithmetic. The asymptotic running-time computational complexity of this decision problem is triply exponential. First-order logic with equality and multiplication of positive integers can express the relation Using this relation and equality, we can define the following relations on positive integers: Divisibility: Greatest common divisor: Least common multiple: the constant : Prime number: Number is a product of primes (for a fixed ): Number is a power of some prime: Number is a product of exactly prime powers: The truth value of formulas of Skolem arithmetic can be reduced to the truth value of sequences of non-negative integers constituting their prime factor decomposition, with multiplication becoming point-wise addition of sequences. The decidability then follows from the Feferman–Vaught theorem that can be shown using Quantifier elimination. Another way of stating this is that first-order theory of positive integers is isomorphic to the first-order theory of finite multisets of non-negative integers with the multiset sum operation, whose decidability reduces to the decidability of the theory of elements. In more detail, according to the fundamental theorem of arithmetic, a positive integer can be represented as a product of prime powers: If a prime number does not appear as a factor, we define its exponent to be zero. Thus, only finitely many exponents are non-zero in the infinite sequence .