Paris-Harringtons sats

Paris-Harringtons sats är en sats inom matematisk logik som anger att den starka ändliga varianten av Ramseys sats (som tillhör Ramseyteorin) är sann, men inte bevisbar i Peanoaritmetik. Detta var det första "naturliga" exemplet av ett sant påstående om heltal som kan formuleras i aritmetiskt språk, men inte bevisas med Peanoaritmetik. Det var redan känt att sådana utsagor fanns från Gödels ofullständighetssatser.

Den starka ändliga versionen av Ramseys sats

Den starka ändliga Ramseysatsen är ett påstående om färgning och naturliga tal och säger att:

• För alla positiva heltal n, k, m kan man hitta N med följande egenskap: om vi färgar varje n-delmängd av S = {1,2,3,...,N} med en av k givna färger, så kan vi hitta en m-delmängd Y av S sådan att alla n-delmängder av Y har samma färg, och att antalet element i Y är större än det minsta elementet i Y.

Utan det sista villkoret, att |Y| > min(Y), är detta en följd av den vanliga ändliga varianten av Ramseys sats, tillämpad för den kompletta grafen $K_{{\mathcal {P}}_{n(S)}}$, där N ges av villkoret

${\binom {N}{n}}=|{\mathcal {P}}_{n}(S)|\geq R(\,\underbrace {m,m,\ldots ,m} _{k}\,),$

och R(m,...,m) (k stycken m) är det vanliga ramseytalet.

Denna starka variant av Ramseys sats kan också härledas från den oändliga Ramseysatsen på nästan exakt samma sätt som den ändliga Ramseysatsen kan härledas från den, med ett kompakthetsargument. Detta bevis kan utföras i andra ordningens aritmetik. Paris-Harringtons sats säger dock att denna variant av Ramseys sats inte är bevisbar i Peano-aritmetik (första ordningens aritmetik).

Paris-Harringtons sats

Kort sagt visade Jeff Paris och Leo Harrington att den starka ändliga varianten av Ramseys sats är obevisbar i Peano-aritmetik, genom att visa att i varje modell av Peano-aritmetiken kan denna aritmetik i sin tur modelleras med hjälp av ramseysatsvarianten. Från existensen av det motsvarande ramseytalet kan man dra slutsatsen att Peano-aritmetiken är konsistent, alltså motsägelsefri. Emellertid kan man enligt Gödels andra ofullständighetssats inte bevisa peanoaritmetikens motsägelsefrihet med hjälp av enbart peanoaritmetiken själv. Eftersom man skulle kunna bevisa motsägelsefriheten med hjälp av enbart peanoaritmetiken, om den starka ändliga ramseysatsen vore bevisbar i denna aritmetik, kan det inte finnas något sådant bevis för denna sats.

Det minsta talet N som uppfyller den starka ändliga varianten av Ramseys sats är en beräkningsbar funktion av n, m, k, men denna funktion växer extremt snabbt. Speciellt är den inte primitivt rekursiv, men den växer också mycket snabbare än vanliga exempel på icke-primitiva rekursiva funktioner som Ackermannfunktionen. Dess tillväxt är så snabb att man i Peanoaritmetiken inte kan bevisa att den är definierad överallt, trots att man enkelt visar att Ackermann-funktionen är väldefinierad med hjälp av enbart peanoaritmetik. rekursiv

Se även

• Goodsteins sats
• Kanamori–McAloon sats

Referenser

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.

Noter

• Marker, David (2002). Model Theory: An Introduction. New York: Springer. ISBN 0-387-98760-6 
• http://mathworld.wolfram.com/Paris-HarringtonTheorem.html
• Paris, J.; Harrington, L. (1977). ”A Mathematical Incompleteness in Peano Arithmetic”. i Barwise, J.. Handbook of Mathematical Logic. Amsterdam, Netherlands: North-Holland 

Externa länkar

• A brief introduction to unprovability (innehåller ett bevis för Paris–Harringtons sats) av Andrey Bovykin