Robinsonova aritmetika

Z Wikipedie, otevřené encyklopedie

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.

[editovat] Jazyk aritmetiky

Robinsonova aritmetika je teorie v jazyce L obsahujícím jeden konstantní symbol 0, jeden unární funkční symbol S (následník), dva binární funkční symboly +, $\cdot$ a jeden binární relační symbol $\leq$ . 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.

Robinsonovu aritmetiku lze zavést také v jazyce vzniklém z jazyka aritmetiky odebráním relačního symbolu $\leq$ . V tom případě je osmý axiom (viz dále) považován za axiom definice tohoto symbolu.

[editovat] Axiomy

Robinsonova aritmetika má osm 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$
(Q8) $\,x\leq y \leftrightarrow (\exists z)(z+x=y)$

[editovat] Vlastnosti

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 $Σ$ -úplná, tj. pro každou $Σ$ -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).