Přeskočit na obsah

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.

Jazyk aritmetiky

[editovat | editovat zdroj]

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 +, a binární relační symbol . Tento jazyk se nazývá jazyk aritmetiky.

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

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) (nula není následníkem žádného čísla)
  • (Q2) (každé číslo, vyjma nuly, je následníkem nějakého čísla)
  • (Q3) (následník je prosté zobrazení)
  • (Q4) (definice sčítání čísla s nulou)
  • (Q5) (definice sčítání čísla s nenulovým číslem)
  • (Q6) (definice násobení čísla nulou)
  • (Q7) (definice násobení čísla nenulovým číslem)

Vlastnosti

[editovat | editovat zdroj]
  • 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 (formuli vzniklou z otevřené formule opakovaným užitím konjunkce, disjunkce, omezené kvantifikace a (neomezené) existenční kvantifikace) a přirozená čísla platí: je dokazatelná v Robinsonově aritmetice (viz model).

Související články

[editovat | editovat zdroj]