Kompakteca teoremo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

La kompakteca teoremo estas baza fakto en simbola logiko kaj modela teorio kaj asertas, ke aro (eble malfinia) 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[redakti | redakti fonton]

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 malfinia 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 malfinian 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 malfiniaj naturaj nombroj aperas, ebleco, kiu ne povas esti ekskludita per ajna aksiomigo - kio ankaŭ estas sekvo de la kompakteca teoremo.

Pruvoj[redakti | redakti fonton]

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 Ai := { jI : ji}.  La familio de ĉiuj tiuj aroj Ai generas filtrilon, do estas ultrafiltrilo U entenanta ĉiujn arojn de la formo Ai.

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ŭ[redakti | redakti fonton]

Referencoj[redakti | redakti fonton]