Robinsonova aritmetika

Robinsonova aritmetika (také Robinsonova aritmetika Q nebo jen aritmetika Q) je jeden z axiomatických systémů formální teorie aritmetiky. Je podstatně slabší než Peanova aritmetika ale na rozdíl od ní je konečně axiomatizovaná. Pojmenována je po americkém matematikovi Raphaelu Mitchelovi Robinsonovi.

Jazyk aritmetiky[editovat]

Robinsonova aritmetika je teorie v jazyce L obsahujícím jeden konstantní (nulární) symbol 0, jeden unární funkční symbol S (následník), dva binární funkční symboly +, $\cdot$ a binární relační symbol $=$ . Tento jazyk se nazývá jazyk aritmetiky.

Term $S(S(\ldots S(0)\ldots))$ , kde se symbol S vyskytuje n-krát, se nazývá n-tý numerál a značí se $\underline{n}$ . Za nultý numerál se považuje term (konstantní symbol) 0.

Axiomy[editovat]

Robinsonova aritmetika má sedm axiomů, které jsou univerzálními uzávěry následujících formulí (tj. vzniknou z těchto formulí, předsadíme-li před ně několik univerzálních kvantifikátorů kvantifikujících všechny vyskytující se volné proměnné):

(Q1) $\,0\neq S(x)$
(Q2) $\,x\neq 0 \rightarrow (\exists y)(x=S(y))$
(Q3) $\,S(x)=S(y) \rightarrow x=y$
(Q4) $\,x+0=x$
(Q5) $\,x+S(y)=S(x+y)$
(Q6) $\,x\cdot 0 = 0$
(Q7) $\,x \cdot S(y)=x\cdot y + x$

Vlastnosti[editovat]

Robinsonova aritmetika je neúplná teorie. Následující formule v ní nejsou dokazatelné ani vyvratitelné:
- $\,x+y=y+x$
- $x\cdot y = y \cdot x$
- $\leq$ je slabě antisymetrická relace, tedy také $\leq$ je lineární uspořádání
Robinsonova aritmetika je nerozhodnutelná teorie, dokonce každé bezesporné rozšíření Robinsonovy aritmetiky v konečném jazyce je nerozhodnutelné. Pokud je tedy toto rozšíření rekurzivně axiomatizované, je také neúplné.
Robinsonova aritmetika (i každé její bezesporné rozšíření) je dokonce rekurzivně neoddělitelná, tj. neexistuje rekurzivní množina obsahující všechny v ní dokazatelné formule a žádné v ní vyvratitelné.
Robinsonova aritmetika je $\Sigma$ -úplná, tj. pro každou $\Sigma$ -formuli $\varphi$ (formuli vzniklou z otevřené formule opakovaným užitím konjunkce, disjunkce, omezené kvantifikace a (neomezené) existenční kvantifikace) a přirozená čísla $k,n_1,\ldots,n_k$ platí: $\varphi(\underline{n}_1, \ldots, \underline{n}_k)$ je dokazatelná v Robinsonově aritmetice $\Leftrightarrow \mathbb{N}\models\varphi[n_1,\ldots,n_k]$ (viz model).