Presburgerova aritmetika

Presburgerova aritmetika je jeden z axiomatických systémů formální teorie aritmetiky. Je podstatně slabší než Peanova aritmetika, zejména proto, že v jazyce neobsahuje symbol pro násobení. Pojmenována je po polském matematikovi Mojżeszi Presburgerovi, který tuto axiomatiku publikoval v roce 1929.

Axiomy

Presburgerova aritmetika je teorie v jazyce L obsahujícím konstantní symbol 0, unární funkční symbol S a binární funkční symbol +. Axiomy jsou následující:

• (PR1) $0\ne S(x)$
• (PR2) $S(x)=S(y)\to x=y$
• (PR3) $x+0=x$
• (PR4) $x+S(y)=S(x+y)$
• (schéma indukce) $\phi (0)\wedge (\mathrm{\forall }x)(\phi (x)\to \phi (S(x)))\to (\mathrm{\forall }x)(\phi (x))$ pro všechny formule $\phi$ jazyka L

Vlastnosti

• Presburgerova aritmetika je bezesporná, úplná a rozhodnutelná teorie
• Každá formule jazyka L je v Presburgerově aritmetice ekvivalentní nějaké formuli, která je jednoho ze tří tvarů $t=s,(\mathrm{\exists }z)(t+z=s),(\mathrm{\exists }z)(t=s+mz)$, kde t,s jsou termy a m numerál (tj. term vzniklý m-násobnou aplikací funkčního symbolu S na konstantní symbol 0).

Související články

• Robinsonova aritmetika
• Peanova aritmetika