Перегляд вихідного коду сторінки Теорема про компактність

{{Вичитати|дата=травень 2017}}

У [[Математична логіка|математичній логіці]] теорема компактності стверджує, що набір пропозицій [[Логіка першого порядку|першого порядку]] має [[Теорія моделей|модель]] тоді і тільки тоді, коли кожна кінцева [[підмножина]] має модель. Ця теорема є важливим інструментом в [[Теорія моделей|теорії моделей]], оскільки вона являє собою корисний метод побудови моделей будь-якого набору пропозицій, які є кінцево [[Несуперечливість|несуперечливі]]. Теорема компактності для обчислення виразів є наслідком [[Теорема Тихонова|теореми Тихонова]] (яка стверджує, що твір [[Компактний простір|компактних просторів]] компактно), застосоване до компактних {{Нп|кам'яні простори|кам'яних просторів||Stone space}}<ref>See Truss (1997).</ref> , і, отже, назви теореми. Так само воно аналогічно характеристиці [[Властивість скінченного перетину|властивості скінченного перетину]] компактності в топологічних просторах: набір замкнутих множин в компактному просторі має непорожній перетин, якщо у кожного кінцевого підкомплексу є непорожній перетин. Теорема компактності є однією з двох ключових властивостей, як і теорема зниження [[Теорема Льовенгейма — Сколема|Льовенгейма-Сколема,]] що використовується в {{Нп|Теорема Ліндстрема|теоремі Ліндстрема||Lindström's theorem}} для характеристики логіки першого порядку. Хоча є деякі узагальнення теореми компактності в логіках не першого порядку, сама теорема компактності в них не виконується.

== Історія ==
[[Курт Гедель]] довів теорему про лічильну компактність у 1930 році. Анатолій Мальцев довів незліченний випадок в 1936 році.<ref>[[Robert Lawson Vaught|Vaught, Robert L.]]: Alfred Tarski's work in model theory. J. Symbolic Logic 51 (1986), no. 4, 869—882</ref>
<ref>[[Abraham Robinson|Robinson, A.]]: Non-standard analysis. North-Holland Publishing Co., Amsterdam 1966. page 48.</ref>

== Додатки ==
Теорема компактності має багато додатків у теорії моделей. Тут наведено кілька типових результатів. З теореми компактності випливає [[принцип Робінсона]]: якщо в кожному полі характеристики нуль є пропозиція першого порядку, то існує константа p така, що пропозиція виконується для будь-якого [[Поле (алгебра)|поля]] [[Характеристика (алгебра)|характеристики]], більшого p. Це можна побачити в такий спосіб: припустимо, що φ&nbsp;— пропозиція, яка виконується в кожному полі характеристики нуль. Тоді її заперечення ¬φ разом з аксіомами полів і нескінченної послідовністю пропозицій 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0, …, не здійснено (оскільки не існує поля характеристики 0, в якому виконано ¬φ, І нескінченна послідовність пропозицій гарантує, що будь-яка модель буде полем характеристики 0). Тому існує кінцева підмножина А цих пропозицій, яка не може бути здійсненною. Припустимо, що A містить ¬φ, аксіоми поля, і для деяких k перші k пропозицій виду 1 + 1 + … + 1 ≠ 0 (оскільки додавання більшої кількості пропозицій не змінює незручності). Нехай B містить всі пропозиції A, крім ¬φ. Тоді будь-яке поле з характеристикою, більшою k, є моделлю B, а ¬φ разом з B нездійсненна. Це означає, що φ має виконуватися в кожній моделі B, а це значить, що φ має місце в кожному полі характеристики більше k.

Друге застосування теореми компактності показує, що будь-яка теорія, що має великі кінцеві моделі або одну нескінченну модель, має моделі довільної великої [[Потужність множини|потужності]] (це висхідна теорема [[Теорема Льовенгейма — Сколема|Левенгейма&nbsp;— Сколема]]). Так, наприклад, існують нестандартні моделі [[Аксіоми Пеано|арифметики Пеано]] з незліченною кількістю «натуральних чисел». Для цього нехай T&nbsp;— вихідна теорія і κ&nbsp;— [[Кардинальне число|кардинальне число.]] Додайте до мови T один постійний символ для кожного елемента κ. Потім додайте в T набір пропозицій, які говорять, що об'єкти, позначені будь-якими двома різними постійними символами з нової колекції, різні (це набір пропозицій κ<sup>2</sup>). Так як кожна кінцева підмножина цієї нової теорії здійсненна за допомогою досить великої кінцевої моделі Т або будь-якої нескінченної моделі, то вся розширена теорія здійсненна. Але будь-яка модель розширеної теорії має потужність, принаймні х.

Третє застосування теореми компактності&nbsp;— це побудова [[Нестандартний аналіз|нестандартних моделей]] дійсних чисел, тобто послідовних розширень теорії дійсних чисел, що містять «нескінченно малі» числа. Щоб переконатися в цьому, хай Σ&nbsp;— аксіоматизація першого порядку теорії дійсних чисел. Розглянемо теорію, отриману додаванням до мови нового постійного символу ε і прилеглу до Σ аксіому ε> 0 і аксіом ε <1 / n для всіх натуральних чисел n. Ясно, що стандартні речові числа R є моделлю будь-якої кінцевої підмножини цих аксіом, так як речові числа задовольняють у Σ і при відповідному виборі ε можуть бути виконані для будь-якої кінцевої
підмножини аксіом щодо ε. За теоремою компактності існує модель * R, яка задовольняє Σ і містить нескінченно малий елемент ε. Аналогічне міркування, що примикає до аксіом ω> 0, ω> 1 і&nbsp;т.&nbsp;д.,показує, що існування нескінченно великих цілих чисел не може бути виключено будь-якою аксіоматизацією Σ дійсних чисел.<ref name="Goldblatt">{{cite book |title=Lectures on the Hyperreals |url=https://archive.org/details/lecturesonhyperr00gold_064 |last=Goldblatt |first=Robert |authorlink=Robert Goldblatt |year=1998 |publisher=[[Springer Verlag|Springer]] |location=New York |isbn=0-387-98464-X |pages=[https://archive.org/details/lecturesonhyperr00gold_064/page/n24 10]–11 }}</ref>

== Докази ==
Можна довести теорему компактності, використовуючи [[Теорема Геделя про повноту|теорему Геделя про повноту]], яка встановлює, що безліч пропозицій здійсненна тоді і тільки тоді, коли на ній не можна довести протиріччя. Оскільки докази завжди кінцеві і, отже, містять тільки кінцеве число заданих пропозицій, слідує теорема компактності. Справді, теорема компактності еквівалентна теоремі Геделя про повноту, і обидві вони еквівалентні [[Теорема про булеві прості ідеали|теоремі про булевий простий ідеал]], слабку форму [[Аксіома вибору|аксіоми вибору]].<ref>See Hodges (1993).</ref>
Спочатку Гедель довів теорему компактності саме таким чином, але пізніше були знайдені деякі «чисто семантичні» доведення теореми компактності, тобто докази, які відносяться до істини, але не до доказовості. Одне з цих доказів ґрунтується на {{Нп|Ультрадобуток|ультрадобутках||ultraproduct}}, що залежать від аксіоми вибору наступним чином: Proof: Зафіксуємо мову першого порядку L, і нехай Σ набір L-пропозицій, таких, що кожна кінцева добірка L-пропозицій, ''i''&nbsp;⊆&nbsp;Σ , є модель <math>\mathcal{M}_i</math>. Нехай прямий добуток структур, а I&nbsp;— набір кінцевих підмножин Σ. Для кожного i з I нехай: A<sub>''i''</sub> := { ''j'' ∈ ''I'' : ''j'' ⊇ ''i''}.

Сімейство всіх цих множин Ai породжує власний [[Фільтр (порядок)|фільтр]], тому існує [[Ультрафільтр (математика)|ультрафільтр]] U, що містить всі множини виду Ai.

Тепер для будь-якої формули φ з Σ маємо:
* множина A<sub>{φ}</sub> &nbsp;знаходиться в ''U''
* ''щоразу, коли j''&nbsp;∈&nbsp;A<sub>{φ}</sub>,то φ&nbsp;∈&nbsp;''j'', отже φ лежить в <math>\mathcal M_j</math>
* множина усіх ''j'' с властивістю, що φ, яка лежить в <math>\mathcal M_j</math>, є надмножиною A<sub>{φ}</sub>, лежить також в ''U''
Використовуючи {{Нп|Теорема Лося|теорему Лося||Łoś's theorem}}, ми бачимо, що φ має лежить в ультрадобутку <math>\prod_{i \subseteq \Sigma}\mathcal{M}_i/U</math>. Таким чином, цей {{Нп|ультрадобуток|||ultraproduct}}, задовольняє всім формулам з Σ.

== Див. також ==
* [[Список тем Булевої Алгебри]]
* [[Теорема Льовенгейма — Сколема]]
* [[Теорема Ербрана]]
* [[Теорема Баруайза]]

== Примітки ==
{{reflist}}

== Посилання ==
* {{cite book | last=Boolos | first=George |author2=Jeffrey, Richard |author3=Burgess, John  | title=''Computability and Logic'' | edition=fourth | year=2004 | publisher="Cambridge University Press }}
* {{cite book | last=Chang | first=C.C. |author2=Keisler, H. Jerome |authorlink2=Howard Jerome Keisler  | publisher=[[Elsevier]] | title=Model Theory | year=1989 | edition=third | isbn=0-7204-0692-7 }}
* {{cite journal | last=Dawson | first=John W. junior | title=The compactness of first-order logic: From Gödel to Lindström | journal=History and Philosophy of Logic | year=1993 | volume=14 | pages=15–37 | doi=10.1080/01445349308837208 }}
* {{cite book | last=Hodges | first=Wilfrid | authorlink=Wilfrid Hodges | publisher=[[Cambridge University Press]] | title=Model theory | year=1993 | isbn=0-521-30442-3 | url-access=registration | url=https://archive.org/details/modeltheory0000hodg }}
* {{cite book | last=Marker | first=David | title= Model Theory: An Introduction | url=https://archive.org/details/modeltheoryintro0217mark | publisher=Springer | year=2002 | isbn=0-387-98760-6| series=[[Graduate Texts in Mathematics]] 217}}
* {{cite book | last=Truss | first=John K. | title=Foundations of Mathematical Analysis | url=https://archive.org/details/foundationsofmat0000trus | year=1997 | publisher=[[Oxford University Press]] | isbn=0-19-853375-6 }}

== Додатковий матеріал ==
* {{cite book |author=Hummel, Christoph |title=Gromov's compactness theorem for pseudo-holomorphic curves |publisher=Birkhäuser |location=Basel, Switzerland |year=1997 |pages= |isbn=3-7643-5735-5 |oclc= |doi=}}

{{Логіка-доробити}}

{{Математична логіка|state=collapsed}}

[[Категорія:Теорія моделей]]
[[Категорія:Основи математики|Компактність]]
[[Категорія:Метатеореми|Компактність]]