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(\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

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) (nula není následníkem žádného čísla) * (Q2) \,x\neq 0 \rightarrow (\exists y)(x=S(y)) (každé číslo, vyjma nuly, je následníkem nějakého čísla) * (Q3) \,S(x)=S(y) \rightarrow 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 ** \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é. +more 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).

Související články

Peanova aritmetika * Presburgerova aritmetika

Kategorie:Matematická logika Kategorie:Aritmetika