Paris-Harringtonova věta

Paris-Harringtonův teorém (nebo Paris-Harringtonův teorém) je teorém v matematické logice , který se stal prvním přirozeným a relativně jednoduchým příkladem tvrzení o přirozených číslech v dějinách matematiky , což je sice pravdivé, ale v Peanově axiomatice nedokazatelné . Existence neprokazatelných teorémů v aritmetice vyplývá přímo z první Gödelovy věty o neúplnosti (1930). Kromě toho Gödelův druhý teorém (publikovaný společně s prvním) poskytuje konkrétní příklad takového tvrzení: konkrétně prohlášení o konzistenci aritmetický. Dlouho však neexistovaly „přirozené“ příklady takových tvrzení, tedy tvrzení, která by nevznikala z tvrzení o nějaké logice, ale byla by přirozenými matematickými tvrzeními o číslech.

Tuto větu a její důkaz publikovali v roce 1977 Geoffrey Paris (Velká Británie) a Leo Harrington (USA).

Silná Ramseyova věta

Výsledek Paris-Harrington je založen na poněkud modifikovaném kombinatorickém Ramseyho teorému [1] :

Pro jakákoli přirozená čísla lze zadat přirozené číslo s následující vlastností: pokud obarvíme každou z podmnožin -prvků jednou z barev, pak existuje podmnožina obsahující alespoň prvky tak, že všechny podmnožiny -prvků mají stejnou barvu a počet prvků není menší než nejmenší prvek $n,k,m$ $N$ $n$ $S=\{1,2,3,\tečky N\}$ $k$ $S$ $Y,$ $m$ $n$ $Y$ $Y$ $Y.$

Bez podmínky " počet prvků není menší než nejmenší prvek $Y$ $Y$ ", toto tvrzení vyplývá z Ramseyho konečné věty . Všimněte si, že zesílenou verzi Ramseyho věty lze napsat v jazyce logiky prvního řádu [2] .

Formulace

Paris-Harringtonova věta říká:

Posílený Ramseyův teorém uvedený výše není v Peanově axiomatice prokazatelný .

Paris a Harrington ve svém článku ukázali, že konzistence Peanovy axiomatiky vyplývá z této věty ; nicméně, jak Gödel ukázal , Peanova aritmetika nedokáže dokázat svou vlastní konzistenci, takže Paris-Harringtonova věta je v ní neprokazatelná. Na druhou stranu pomocí logiky druhého řádu nebo axiomatiky ZF teorie množin je snadné dokázat, že silná Ramseyova věta je pravdivá [2] .

Další příklady nedokazatelných teorémů v aritmetice

Goodsteinova věta
Kanamori-Macaloonova věta
Kruskalova věta o stromech

Literatura

Paris J., Harrington L. A Mathematical Incompleteness in Peano Arithmetic // Handbook of Mathematical Logic. - Amsterdam: North-Holland, 1977. - ISBN 072042285X . (první autorova publikace věty)
Marker, David. Teorie modelu : Úvod . - New York: Springer , 2002. - ISBN 0-387-98760-6 .

Odkazy

Kochetkov Yu Yu. Vyčíslitelné funkce. Kapitola 19. Věty nedokazatelné v axiomatické aritmetice . Staženo: 17. srpna 2018. (neurčitý)
Bovykin, Andrey, Weisstein, Eric W. Paris -Harringtonova věta . Staženo 17. srpna 2018. Dostupné zMathWorld .
Bovykin, Andrej . Stručný úvod do neprokazatelnosti (obsahuje důkaz věty).