Kompakteca teoremo

La kompakteca teoremo estas baza fakto en matematika logiko kaj modelteorio kaj asertas, ke aro (eble nefinia) de unua-ordaj propozicioj estas kontentigebla (tio estas, havas modelon), se kaj nur se ĉiu finia subaro de ĝi estas kontentigebla.

La kompakteca teoremo por la propozicia kalkulado estas rezulto de la teoremo de Tychonoff (kiu diras ke la produto de kompaktaj spacoj estas mem kompakta) aplikita al spacoj de Stone; pro tio aperis la nomo "kompakteca" de la teoremo.

Aplikoj

De la teoremo sekvas ekzemple, ke, se iu unua-orda propozicio validas por ĉiu kampo de karakterizo nulo, tiam ekzistas konstanto p tia, ke la propozicio validas por ĉiu kampo de karakterizo pli granda ol p. Tio videblas kiel sekvas: supozu ke S estas la propozicio konsiderata. Tiam ĝia neo ~S, kaj ankaŭ la kampaj aksiomoj kaj la nefinia serio de propozicioj 1+1 ≠ 0, 1+1+1 ≠ 0, ... estas ne kontentigeblaj laŭ premiso. Tial finia subaro de tiuj propozicioj estas ne kontentigebla, kio signifas, ke S validas en tiuj kampoj kiuj havas sufiĉe grandan karakterizaĵon.

Ankaŭe, sekvas de la teoremo, ke ĉiu teorio kiu havas nefinian modelon havas modelojn de ajna granda kardinalo. Do, ekzemple, estas nenormaj modeloj de peana aritmetiko kun nekalkuleble multaj 'naturaj nombroj'. La nenorma analitiko estas alia ekzemplo kie nefiniaj naturaj nombroj aperas, ebleco, kiu ne povas esti ekskludita per ajna aksiomigo - kio ankaŭ estas sekvo de la kompakteca teoremo.

Pruvoj

Oni povas pruvi la kompaktecan teoremon uzante kompletecan teoremon de Gödel, kiu certigas, ke aro de propozicioj estas kontentigebla se kaj nur se neniu kontraŭdiro povas esti pruvita de ĝi. Fakte, la kompakteca teoremo ekvivalentas al la kompleteca teoremo, kaj ambaŭ ekvivalentas al la lemo de ultrafiltrilo, malforta formo de la aksiomo pri elekto. Ĉar pruvoj estas ĉiam finiaj kaj pro tio engaĝas nur finian multon el la donitaj propozicioj, la kompakteca teoremo sekvas.

Gödel originale pruvis la kompaktecan teoremon en ĝuste tia maniero, sed poste iuj "pure semantikaj" pruvoj de la kompakteca teoremo malkovriĝis, tio estas, pruvoj, kiuj koncernas veron sed ne pruvabelecon. Unu de tiuj pruvoj sin subtenas sur ultraprodutoj dependantaj de la aksiomo pri elekto kiel sekvas:

Pruvo: Fiksu unua-ordan lingvon L, kaj lasu, ke $\Sigma$ estu kolekto de L-propozicioj tiaj, ke ĉiu finia subkolekto da L-propozicioj, $i\subseteq \Sigma$ de ĝi havas modelon ${\mathcal {M}}_{i}$. Ankaŭ lasu ke $\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}$ estu la rekta produto de la strukturoj kaj $I$ estu la kolekto de nemalplenaj finiaj subaroj de $\Sigma$.   Por ĉiu i en I lasu ke A_i := { j ∈ I : j ⊇ i}.  La familio de ĉiuj tiuj aroj A_i generas filtrilon, do estas ultrafiltrilo U entenanta ĉiujn arojn de la formo A_i.

Nun por ajna formulo φ en Σ validas ke:

• la aro A{φ} estas en U
• kiam ajn j ∈ A{φ}, tiam φ ∈ j, do φ validas en ${\mathcal {M}}_{j}$
• la aro de ĉiuj j kun la propraĵo ke φ validas en ${\mathcal {M}}_{j}$ estas superaro de A{φ}, do ankaŭ en U

Uzante la teoremon de Łoś ni vidas, ke φ validas en la ultraproduto $\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U$. Do tiu ultraproduto kontentigas ĉiujn formulojn en Σ.

Vidu ankaŭ

• Bulea algebro
• Teoremo de Löwenheim-Skolem
• Propraĵo de kompakteco
• Teoremo de Lindström

Referencoj

• C. C. Chang, H. J. Keisler. Model theory (1977) ISBN 0-7204-0692-7 angle
• David Marker. Model Theory: An Introduction (2002) Springer-Verlag, ISBN 0-387-98760-6 angle