Skolem arithmetic

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.

For other uses, see Skolem arithmetic (disambiguation).

Skolem arithmetic is much 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, however.

Extension

Skolem arithmetic with the order predicate or the successor predicate is equivalent to Peano arithmetic.

See also

References

Bès, Alexis. "A survey of Arithmetical Definability". Archived from the original on 28 November 2012. Retrieved 27 June 2012.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.