Теорема компактности

Из Википедије, слободне енциклопедије

У математичкој логици, теорема компактности гласи да скуп (може да буде и бесконачан) исказа првог реда има модел, акко сваки његов коначан подскуп има модел. Постоји уопштење компактности за језике вишег реда (у односу на језик првог реда). У односу на теорије базиране на логикама које су строго јаче од логике првог реда, компактност се сматра исувише јаким својством.

Теорема компактности за исказни рачун је последица теореме Тихонова (која гласи да је производ компактних простора компактан) примењене на компактне Стоунове просторе;[1] и отуда име теореме.

Примене[уреди]

Из теореме следи на пример да ако неки исказ првог реда важи за свако поље карактеристике нула, онда постоји константа p, таква да исказ важи за свако поље карактеристике веће од p. Ово се може посматрати на следећи начин: претпоставимо да је φ дати исказ. Онда његова негација, ¬φ, заједно са пољем аксиома и бесконачним редом исказа 1+1 ≠ 0, 1+1+1 ≠ 0, … по претпоставци није задовољива. Стога коначан подскуп ових исказа није задовољив, што значи да φ важи у оним пољима која имају довољно велику карактеристику.

Такође, из теореме следи да свака теорија која има бесконачан модел има моделе произвољно велике кардиналности (теорема Левенхајм-Сколем). Тако на пример постоје нестандардни модели за Пеанову аритметику са непребројиво много 'природних бројева'.

Теорема компактности имплицира да постоје нестандардни модели реалних бројева, то јест конзистентна проширења теорије реалних бројева који садрже инфинитезималне бројеве.

Докази[уреди]

Теорема компактности се може доказати коришћењем Геделове теореме о потпуности, која тврди да је скуп исказа задовољив ако и само ако се из њега не може доказати контрадикција. Како су докази увек коначни и стога укључују само коначно много од датих исказа, следи теорема компактности. У ствари, теорија компактности је еквивалентна Геделовој теореми о потпуности, а обе су еквивалентне леми о ултрафилтерима, слабијем облику аксиоме избора.

Гедел је прво доказао теорему компактности само на овај начин, али касније су пронађени неки чисто семантички докази ове теореме, то јест докази који се односе на истину а не на доказивост. Следи један од ових доказа који се ослања на ултрапроизводе:

Доказ: Фиксирајмо језик првог реда L, и узмимо да је Σ колекција L-реченица, таквих да свака коначна подколекција L-реченица, i ⊆ Σ има модел \mathcal{M}_i. Такође, нека је \prod_{i \subseteq \Sigma}\mathcal{M}_i директан производ структура и I је колекција коначних подскупова од Σ. За свко i из I нека је Ai := { jI : ji}. Фамилија свих ових скупова Ai генерише филтер, па постоји ултрафилтер U који садржи све скупове облика Ai.

Сада за сваку формулу φ из Σ имамо:

  • скуп A{φ} је унутар U
  • када год j ∈ A{φ}, тада φ ∈ j, стога φ важи у \mathcal M_j
  • скуп свих j са својством да φ важи у \mathcal M_j је надскуп од A{φ}, и стога такође у U

Коришћењем Лосове теореме се види да φ важи у ултрапроизводу \prod_{i \subseteq \Sigma}\mathcal{M}_i/U. Значи овај ултрапроизвод задовољава све формуле из Σ.

Види још[уреди]

Референце[уреди]

Литература[уреди]

Даља литература[уреди]

  • Hummel, Christoph (1997). Gromov's compactness theorem for pseudo-holomorphic curves. Basel, Switzerland: Birkhäuser. ISBN 978-3-7643-5735-1.