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

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(\dots S(0)\dots ))$, kde se symbol S vyskytuje n-krát, se nazývá n-tý numerál a značí se $\underset{\_}{n}$. Za nultý numerál se považuje term (konstantní symbol) 0.

Axiomy

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 obecných kvantifikátorů kvantifikujících všechny vyskytující se volné proměnné):

• (Q1) $0\ne S(x)$ (nula není následníkem žádného čísla)
• (Q2) $x\ne 0\to (\mathrm{\exists }y)(x=S(y))$ (každé číslo, vyjma nuly, je následníkem nějakého čísla)
• (Q3) $S(x)=S(y)\to x=y$ (následník je prosté zobrazení)
• (Q4) $x+0=x$ (definice sčítání čísla s nulou)
• (Q5) $x+S(y)=S(x+y)$ (definice sčítání čísla s nenulovým číslem)
• (Q6) $x\cdot 0=0$ (definice násobení čísla nulou)
• (Q7) $x\cdot S(y)=x\cdot y+x$ (definice násobení čísla nenulovým číslem)

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$
  • $\le$ je slabě antisymetrická relace, tedy také $\le$ 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 $\mathrm{\Sigma }$-úplná, tj. pro každou $\mathrm{\Sigma }$-formuli $\phi$ (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,\dots ,n_k$ platí: $\phi ({\underset{\_}{n}}_1,\dots ,{\underset{\_}{n}}_k)$ je dokazatelná v Robinsonově aritmetice $\iff \mathbb{N}\models \phi [n_1,\dots ,n_k]$ (viz model).

Související články

• Peanova aritmetika
• Presburgerova aritmetika