Gödel tömörségi tétel

A Gödel-féle tömörségi tétel kimondja, hogy az elsőrendű logika mondathalmazának akkor és csak akkor van modellje , ha a mondatok minden véges részhalmazának van modellje.

Ez a tétel a modellelmélet fontos eszköze , mivel kényelmes módszert biztosít végtelen mondathalmaz modelljének megalkotására.

A tétel Tyhonov tételének a következménye, miszerint a kompakt terek szorzata kompakt. Ráadásul analóg a kompakt terek jellemzésével a véges metszéspont tulajdonsága szempontjából.

Történelem

Kurt Gödel 1930-ban megszámlálhatatlan számú mondatra bebizonyította a tömörségi tételt; a megszámlálhatatlan esetet Anatolij Ivanovics Malcev bizonyította 1936-ban.

Következmények

• Ha a mondat minden nulla karakterisztikájú mezőben teljesül , akkor az kellően nagy karakterisztikájú összes mezőre igaz.
  • Valóban, maradjon φ minden karakterisztikus nulla mezőben. Ekkor a ¬φ tagadása a mező axiómáival és az 1+1 ≠ 0, 1+1+1 ≠ 0, ... végtelen propozíciósorozattal együtt ellentmondáshoz vezet (mivel nincs 0 karakterisztikus mező amelyben a mondatsorozat garantálja, hogy bármely modell 0) karakterisztikájú mező lesz. Ezért van ezeknek a mondatoknak egy véges A részhalmaza , ami ellentmondáshoz vezet. Tartalmazza B az A összes mondatát , kivéve ¬φ . Ekkor bármely nagy karakterisztikával rendelkező mező B modell, és ¬φ B -vel együtt nem kivitelezhető. Ez azt jelenti, hogy φ teljesül minden B modellben , különösen φ teljesül minden kellően nagy karakterisztikájú mezőben.

• Ha egy elméletnek tetszőlegesen nagy véges modelljei vagy egy végtelen modelljei vannak, akkor tetszőlegesen nagy teljesítményű modelljei vannak . (Ez a Löwenheim-Skolem tétel speciális esete ).
  • Így például a Peano aritmetika nem szabványos modelljei megszámlálhatatlan számú természetes számmal rendelkeznek .
  • Bizonyíték. Legyen M az eredeti elmélet modellje. Adjunk hozzá egy szimbólumot a nyelvhez a nagyszámú T halmaz minden eleméhez . Ezután adjunk hozzá egy sor mondatot, amelyek azt mondják, hogy ezek a karakterek különböznek egymástól. Mivel ennek az új elméletnek minden véges részhalmazára létezik modell, magának az elméletnek is van modellje.

• Valós számok nem szabványos modelljének felépítése , vagyis a valós számok elméletének kiterjesztése, amely " végtelen kicsinyeket " tartalmaz.
  • Legyen Σ az elsőrendű valós számok elméletének axiomatizálása. Tekintsük azt az elméletet, amelyet úgy kapunk, hogy egy új ε állandót adunk a nyelvhez, és az ε > 0 és ε < 1/ n állításokat minden n természetes számra . Nyilvánvaló, hogy a standard valós számok modellként szolgálnak ezen axiómák bármely véges részhalmazához . A tömörségi tétel szerint létezik egy olyan modell, amely minden állítást kielégít. Vagyis egy infinitezimális ε számú modell.

A bizonyítékokról

A tétel Gödel teljességi tételéből következik . Gödel eredetileg így bizonyította a tömörségi tételt. Később "pusztán szemantikai " bizonyítékokat találtak. Az egyik ilyen bizonyíték az ultralimitekre támaszkodik .

Linkek

• Boolos, George; Jeffrey, Richard; Burgess, John. Kiszámíthatóság és logika  (neopr.) . - negyedik. – Cambridge University Press , 2004.
• Chang, C. C.; Keisler, H. Jerome. Modellelmélet  (határozatlan) . — harmadik. - Elsevier , 1989. - ISBN 0-7204-0692-7 .
• Dawson, John W. junior. Az elsőrendű logika tömörsége: Gödeltől Lindströmig  (angol)  // History and Philosophy of Logic : Journal. - 1993. - 1. évf. 14 . - P. 15-37 . - doi : 10.1080/01445349308837208 .
• Hodges, Wilfrid. Modellelmélet  (határozatlan) . - Cambridge University Press , 1993. - ISBN 0-521-30442-3 .
• Marker, David. Modellelmélet : Bevezetés  (neopr.) . — Springer, 2002. - ISBN 0-387-98760-6 .
• Truss, John K. A matematikai elemzés  alapjai . - Oxford University Press , 1997. - ISBN 0-19-853375-6 .

Szótárak és enciklopédiák	Britannica (online)