Skolemská aritmetika - Skolem arithmetic

Tento článek týkající se matematiky je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

Skolemská aritmetika je teorie prvního řádu z přirozená čísla s násobení, pojmenovaný na počest Thoralf Skolem. The podpis aritmetiky Skolem obsahuje pouze operaci násobení a rovnost, přičemž operaci sčítání zcela vynechává.

Skolemská aritmetika je mnohem slabší než Peano aritmetika, který zahrnuje operace sčítání i násobení. Na rozdíl od Peano aritmetiky, Skolemova aritmetika je a rozhodnutelná teorie. To znamená, že u jakékoli věty v jazyce Skolemovy aritmetiky je možné účinně určit, zda je tato věta prokazatelná z axiomů Skolemovy aritmetiky. Asymptotická doba běhu výpočetní složitost z toho rozhodovací problém je trojnásobně exponenciální.

Rozšíření

Skolemská aritmetika s predikátem řádu nebo predikátem nástupce je ekvivalentní Peano aritmetika.

Viz také

• Presburgerova aritmetika
• Robinsonova aritmetika

Reference

Bès, Alexis. „Průzkum aritmetické definovatelnosti“. Archivovány od originál dne 28. listopadu 2012. Citováno 27. června 2012.