Теорема компактности — разлика између измена

С Википедије, слободне енциклопедије
Садржај обрисан Садржај додат
м Бот: Селим 13 међујезичких веза, које су сад на Википодацима на d:q1149458
Autobot (разговор | доприноси)
м разне исправке; козметичке измене
Ред 25: Ред 25:
Коришћењем [[ултрапроизвод|Лосове теореме]] се види да -{φ}- важи у ултрапроизводу <math>\prod_{i \subseteq \Sigma}\mathcal{M}_i/U</math>. Значи овај ултрапроизвод задовољава све формуле из -{Σ}-.
Коришћењем [[ултрапроизвод|Лосове теореме]] се види да -{φ}- важи у ултрапроизводу <math>\prod_{i \subseteq \Sigma}\mathcal{M}_i/U</math>. Значи овај ултрапроизвод задовољава све формуле из -{Σ}-.


== Види још==
== Види још ==
* [[Теорема Левенхајм-Сколем]]
* [[Теорема Левенхајм-Сколем]]
* [[Линдстремова теорема]]
* [[Линдстремова теорема]]
* [[Ербранова теорема]]
* [[Ербранова теорема]]


== Напомене==
== Напомене ==
{{извори}}
{{reflist}}


== Референце==
== Референце ==
* {{ cite book | last=Boolos | first=George | coauthors=Jeffrey, Richard; Burgess, John | title=''Computability and Logic'' | edition=fourth edition | year=2004 | publisher="Cambridge University Press }}
* {{ cite book | last=Boolos | first=George | coauthors=Jeffrey, Richard; Burgess, John | title=''Computability and Logic'' | edition=fourth edition | year=2004 | publisher="Cambridge University Press }}
* {{ cite book | last=Chang | first=C.C. | coauthors=[[Howard Jerome Keisler|Keisler, H. Jerome]] | publisher=[[Elsevier]] | title=Model Theory | year=1989 | edition=third edition | isbn=0-7204-0692-7 }}
* {{ cite book | last=Chang | first=C.C. | coauthors=[[Howard Jerome Keisler|Keisler, H. Jerome]] | publisher=[[Elsevier]] | title=Model Theory | year=1989 | edition=third edition | isbn=0-7204-0692-7 }}

Верзија на датум 25. април 2013. у 16:09

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

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

Примене

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

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

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

Докази

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

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

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

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

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

Коришћењем Лосове теореме се види да φ важи у ултрапроизводу . Значи овај ултрапроизвод задовољава све формуле из Σ.

Види још

Напомене

  1. ^ Види Truss (1997).

Референце

Даља литература

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