Paris-Haringtonin lause

Paris-Harrington -lause (tai Paris-Harrington -lause ) on matemaattisen logiikan lause , josta tuli ensimmäinen luonnollinen ja suhteellisen yksinkertainen esimerkki luonnollisia lukuja koskevasta väittämästä matematiikan historiassa , mikä on totta, mutta ei todennettavissa Peanon aksiomatiikassa . Todistamattomien lauseiden olemassaolo aritmetiikassa seuraa suoraan Gödelin ensimmäisestä epätäydellisyyslauseesta (1930). Lisäksi Gödelin toinen lause , (julkaistu yhdessä ensimmäisen kanssa), tarjoaa konkreettisen esimerkin tällaisesta väittämästä: nimittäin aritmeettisen johdonmukaisuuslauseen . Pitkään aikaan ei kuitenkaan ollut olemassa "luonnollisia" esimerkkejä sellaisista väitteistä, toisin sanoen lauseista, jotka eivät syntyisi jostain logiikkaa koskevista väitteistä, vaan olisivat luonnollisia matemaattisia väitteitä numeroista.

Tämän lauseen ja sen todisteen julkaisivat vuonna 1977 Geoffrey Paris (Iso-Britannia) ja Leo Harrington (USA).

Vahva Ramseyn lause

Paris-Harringtonin tulos perustuu hieman modifioituun kombinatoriseen Ramseyn lauseeseen [1] :

Kaikille luonnollisille luvuille voidaan määrittää luonnollinen luku , jolla on seuraava ominaisuus: jos värjätään jokainen -elementin osajoukko jollakin väreistä, on olemassa osajoukko , joka sisältää vähintään elementtejä siten, että kaikilla -elementin osajoukoilla on sama väri. , ja elementtien lukumäärä ei ole pienempi kuin pienin elementti ${\näyttötyyli n,k,m}$ $N$ $n$ $S=\{1,2,3,\dots N\}$ $k$ $S$ $Y,$ $m$ $n$ $Y$ $Y$ $Y.$

Ilman ehtoa " alkioiden lukumäärä ei ole pienempi kuin pienin alkio $Y$ $Y$ ", tämä väite seuraa Ramseyn äärellisestä lauseesta . Huomaa, että vahvistettu versio Ramseyn lauseesta voidaan kirjoittaa ensimmäisen asteen logiikan kielellä [2] .

Sanamuoto

Paris-Harrington-lause sanoo:

Edellä esitetty vahvistettu Ramseyn lause ei ole todistettavissa Peanon aksiomatiikassa .

Paris ja Harrington osoittivat kirjoituksessaan, että Peanon aksiomaattisen johdonmukaisuus seuraa tästä lauseesta ; Kuitenkin, kuten Gödel on osoittanut , Peanon aritmetiikka ei pysty todistamaan omaa johdonmukaisuuttaan, joten Paris-Harrington-lause on siinä todistamaton. Toisaalta toisen asteen logiikkaa tai ZF-joukkoteorian aksiomatiikkaa käyttämällä on helppo todistaa vahva Ramseyn lause pitää paikkansa [2] .

Muita esimerkkejä todistamattomista lauseista aritmetiikassa

Goodsteinin lause
Kanamori–Macaloon-lause
Kruskal-puulause

Kirjallisuus

Paris J., Harrington L. Matemaattinen epätäydellisyys Peano Aritmetiikassa // Matemaattisen logiikan käsikirja. - Amsterdam: Pohjois-Hollanti, 1977. - ISBN 072042285X . (lauseen ensimmäinen kirjoittajan julkaisu)
Marker, David. Malliteoria : Johdanto . - New York: Springer , 2002. - ISBN 0-387-98760-6 .

Linkit

Kochetkov Yu. Yu. Laskettavat funktiot. Luku 19. Todistamattomia lauseita aksiomaattisessa aritmetiikassa . Haettu: 17.8.2018. (määrätön)
Bovykin, Andrey, Weisstein, Eric W. Paris - Harringtonin lause . Haettu 17. elokuuta 2018. SaatavillaMathWorldistä .
Bovykin, Andrei . Lyhyt johdatus todistamattomuuteen (sisältää lauseen todistuksen).