Teorema kompaktnosti

U matematičkoj logici, teorema kompaktnosti glasi da skup (može da bude i beskonačan) iskaza prvog reda ima model, akko svaki njegov konačan podskup ima model. Postoji uopštenje kompaktnosti za jezike višeg reda (u odnosu na jezik prvog reda). U odnosu na teorije bazirane na logikama koje su strogo jače od logike prvog reda, kompaktnost se smatra isuviše jakim svojstvom.

Teorema kompaktnosti za iskazni račun je posledica teoreme Tihonova (koja glasi da je proizvod kompaktnih prostora kompaktan) primenjene na kompaktne Stounove prostore; i otuda ime teoreme.

Primene

Iz teoreme sledi na primer da ako neki iskaz prvog reda važi za svako polje karakteristike nula, onda postoji konstanta p, takva da iskaz važi za svako polje karakteristike veće od p. Ovo se može posmatrati na sledeći način: pretpostavimo da je φ dati iskaz. Onda njegova negacija, ¬φ, zajedno sa poljem aksioma i beskonačnim redom iskaza 1+1 ≠ 0, 1+1+1 ≠ 0, … po pretpostavci nije zadovoljiva. Stoga konačan podskup ovih iskaza nije zadovoljiv, što znači da φ važi u onim poljima koja imaju dovoljno veliku karakteristiku.

Takođe, iz teoreme sledi da svaka teorija koja ima beskonačan model ima modele proizvoljno velike kardinalnosti (teorema Levenhajm-Skolem). Tako na primer postoje nestandardni modeli za Peanovu aritmetiku sa neprebrojivo mnogo 'prirodnih brojeva'.

Teorema kompaktnosti implicira da postoje nestandardni modeli realnih brojeva, to jest konzistentna proširenja teorije realnih brojeva koji sadrže infinitezimalne brojeve.

Dokazi

Teorema kompaktnosti se može dokazati korišćenjem Gedelove teoreme o potpunosti, koja tvrdi da je skup iskaza zadovoljiv ako i samo ako se iz njega ne može dokazati kontradikcija. Kako su dokazi uvek konačni i stoga uključuju samo konačno mnogo od datih iskaza, sledi teorema kompaktnosti. U stvari, teorija kompaktnosti je ekvivalentna Gedelovoj teoremi o potpunosti, a obe su ekvivalentne lemi o ultrafilterima, slabijem obliku aksiome izbora.

Gedel je prvo dokazao teoremu kompaktnosti samo na ovaj način, ali kasnije su pronađeni neki čisto semantički dokazi ove teoreme, to jest dokazi koji se odnose na istinu a ne na dokazivost. Sledi jedan od ovih dokaza koji se oslanja na ultraproizvode:

Dokaz: Fiksirajmo jezik prvog reda L, i uzmimo da je Σ kolekcija L-rečenica, takvih da svaka konačna podkolekcija L-rečenica, i ⊆ Σ ima model ${\mathcal {M}}_{i}$. Takođe, neka je $\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}$ direktan proizvod struktura i I je kolekcija konačnih podskupova od Σ. Za svko i iz I neka je A_i := { j ∈ I : j ⊇ i}. Familija svih ovih skupova A_i generiše filter, pa postoji ultrafilter U koji sadrži sve skupove oblika A_i.

Sada za svaku formulu φ iz Σ imamo:

• skup A_{φ} je unutar U
• kada god j ∈ A_{φ}, tada φ ∈ j, stoga φ važi u ${\mathcal {M}}_{j}$
• skup svih j sa svojstvom da φ važi u ${\mathcal {M}}_{j}$ je nadskup od A_{φ}, i stoga takođe u U

Korišćenjem Losove teoreme se vidi da φ važi u ultraproizvodu $\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U$. Znači ovaj ultraproizvod zadovoljava sve formule iz Σ.

Vidi još

• Teorema Levenhajm-Skolem
• Lindstremova teorema
• Erbranova teorema

Literatura

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Computability and Logic (4. izd.). "Cambridge University Press. 
• Chang, C.C.; Keisler, H. Jerome (1989). Model Theory (3. izd.). Elsevier. ISBN 978-0-7204-0692-4. 
• Dawson, John W. junior (1993). „The compactness of first-order logic: From Gödel to Lindström”. History and Philosophy of Logic. 14: 15—37. doi:10.1080/01445349308837208. 
• Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 978-0-521-30442-9. 
• Hummel, Christoph (1997). Gromov's compactness theorem for pseudo-holomorphic curves. Basel, Switzerland: Birkhäuser. ISBN 978-3-7643-5735-1. 
• Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics 217. Springer. ISBN 978-0-387-98760-6. 
• Truss, John K. (1997). Foundations of Mathematical Analysis. Oxford University Press. ISBN 978-0198533757.