Robinsonova aritmetika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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.

Axiomy[editovat | editovat zdroj]

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)
  • (Q2)
  • (Q3)
  • (Q4)
  • (Q5)
  • (Q6)
  • (Q7)

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]