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.

Obsah

[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é:
  • 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).

[editovat] Podívejte se také na

Související články obsahuje:
 Portál Matematika 
V jiných jazycích