Gödels kompakthetsteorem

Gödels kompaktitetssats säger att en uppsättning meningar i första ordningens logik har en modell om och bara om varje finit delmängd av meningar har en modell.

Denna sats är ett viktigt verktyg i modellteorin , eftersom det ger en bekväm metod för att konstruera modeller för en oändlig uppsättning meningar.

Satsen är en följd av Tikhonovs sats att produkten av kompakta rum är kompakt. Dessutom är det analogt med karakteriseringen av kompakta utrymmen i termer av den finita skärningsegenskapen.

Historik

Kurt Gödel bevisade kompaktitetsteoremet för ett räknebart antal meningar 1930; det oräkneliga fallet bevisades av Anatolij Ivanovitj Maltsev 1936.

Konsekvenser

• Om meningen är uppfylld i varje fält med egenskap noll, så är det sant i alla fält med en tillräckligt stor egenskap.
  • Låt faktiskt φ hålla i varje fält med karakteristik noll. Då dess negation ¬φ, tillsammans med fältets axiom och den oändliga sekvensen av propositioner 1+1 ≠ 0, 1+1+1 ≠ 0, ..., leder till en motsägelse (eftersom det inte finns något fält med karakteristik 0 där sekvensen av meningar garanterar att vilken modell som helst kommer att vara ett fält med egenskap 0). Därför finns det en ändlig delmängd A av dessa meningar, vilket leder till en motsägelse. Låt B innehålla alla meningar i A utom ¬φ. Då är vilket fält som helst med dastatono stor egenskap en modell B , och ¬φ tillsammans med B är inte genomförbart. Detta betyder att φ är uppfylld i varje modell B , i synnerhet är φ uppfylld i varje område med tillräckligt stor karakteristik.

• Om en teori har godtyckligt stora ändliga modeller, eller en oändlig modell, så har den modeller med godtyckligt stor kraft . (Detta är ett specialfall av Löwenheim-Skolem-satsen ).
  • Så, till exempel, det finns icke-standardiserade modeller av Peano-aritmetik med ett oräkneligt antal naturliga tal .
  • Bevis. Låt M vara en modell av den ursprungliga teorin. Låt oss lägga till en symbol till språket för varje element i uppsättningen T av stor kardinalitet . Sedan lägger vi till en uppsättning meningar som säger att alla dessa karaktärer är olika. Eftersom det finns en modell för varje ändlig delmängd av denna nya teori, finns det en modell för själva teorin.

• Konstruktion av en icke-standardmodell av reella tal , det vill säga en förlängning av teorin om reella tal, innehållande " infinitesimals ".
  • Låt Σ vara en axiomatisering av teorin om reella tal av första ordningen. Betrakta teorin som erhålls genom att lägga till en ny konstant ε till språket och propositionerna ε > 0 och ε < 1/ n för alla naturliga tal n . Uppenbarligen är de vanliga reella talen en modell för vilken ändlig delmängd som helst av dessa axiom . Genom kompaktitetsteoremet finns det en modell som uppfyller alla påståenden. Det vill säga en modell med ett infinitesimalt tal ε.

Om bevis

Satsen följer av Gödels fullständighetssats . Gödel bevisade kompaktitetsteoremet ursprungligen på detta sätt. Senare hittades "rent semantiska " bevis. Ett av dessa bevis förlitar sig på ultragränser .

Länkar

• Boolos, George; Jeffrey, Richard; Burgess, John. Beräkningsbarhet och logik  (neopr.) . - fjärde. — Cambridge University Press , 2004.
• Chang, C.C.; Keisler, H. Jerome. Modellteori  (obestämd) . — tredje. - Elsevier , 1989. - ISBN 0-7204-0692-7 .
• Dawson, John W. junior. The compactness of first-order logic: From Gödel to Lindström  (engelska)  // History and Philosophy of Logic : journal. - 1993. - Vol. 14 . - S. 15-37 . - doi : 10.1080/01445349308837208 .
• Hodges, Wilfrid. Modellteori  (obestämd) . - Cambridge University Press , 1993. - ISBN 0-521-30442-3 .
• Marker, David. Model Theory: An Introduction  (neopr.) . — Springer, 2002. - ISBN 0-387-98760-6 .
• Truss, John K. Grunder för matematisk analys  . - Oxford University Press , 1997. - ISBN 0-19-853375-6 .

Ordböcker och uppslagsverk	Britannica (online)