10.9: Теорема компактності

Template:MathJaxZach

Одним з важливих наслідків теореми повноти є теорема компактності. Теорема компактності стверджує, що якщо кожна скінченна підмножина множини речень задовольняється, вся множина є задовільною, навіть якщо сама множина нескінченна. Це далеко не очевидно. Ніщо, здається, не виключає, принаймні, на перший погляд, можливість існування нескінченних наборів речень, які суперечливі, але протиріччя виникає лише, так би мовити, з нескінченного числа. Теорема компактності говорить про те, що такий сценарій можна виключити: немає незадовільних нескінченних множин пропозицій, кожне скінченне підмножина яких задовольняється. Як і теорема повноти, вона має версію, пов'язану з тягненням: якщо нескінченний набір речень тягне за собою щось, вже кінцева підмножина робить.

Визначення$\PageIndex{1}$

Набір$\Gamma$ формул кінцево задовольняється тоді і тільки тоді, коли кожен$\Gamma_0 \subseteq \Gamma$ скінченний задовольняється.

Теорема$\PageIndex{1}$: Compactness Theorem

Наступне утримання для будь-яких речень$\Gamma$ і$A$:

1. $\Gamma \Entails A$якщо є кінцеве$\Gamma_0 \subseteq \Gamma$ таке, що$\Gamma_0 \Entails A$.

2. $\Gamma$є задовільним тоді і тільки тоді, коли він кінцево задовольняється.

Доказ. Доводимо (2). Якщо$\Gamma$ задовольняється, то є будова$\Struct{M}$ така, що$\Sat{M}{A}$ для всіх$A \in \Gamma$. Звичайно, це${\Struct{M}}$ також задовольняє кожну скінченну підмножину$\Gamma$, так що$\Gamma$ це кінцево задовольняється.

Тепер припустимо, що$\Gamma$ це остаточно задовольняється. Тоді кожне скінченне підмножина$\Gamma_0 \subseteq \Gamma$ задовольняється. За обґрунтованості (Слідства 9.11.2 та 8.12.3) кожна кінцева підмножина є послідовною. Тоді$\Gamma$ сама повинна відповідати Пропозиціям 8.8.5 та 9.7.5. За повнотою (теорема 10.8.1), оскільки$\Gamma$ є послідовним, вона задовольняється. ◻

Проблема$\PageIndex{1}$

Доведіть (1) теореми$\PageIndex{1}$.

Приклад$\PageIndex{1}$

У кожній моделі$\Struct{M}$ теорії кожен термін$\Gamma$,$t$ звичайно, виділяє елемент$\Domain{M}$. Чи можемо ми гарантувати, що це також правда, що кожен елемент$\Domain{M}$ вибирається тим чи іншим терміном? Іншими словами, чи існують теорії,$\Gamma$ всі моделі яких висвітлюються? Теорема компактності показує, що це не так, якщо$\Gamma$ має нескінченні моделі. Ось як це побачити: Дозвольте$\Struct{M}$ бути нескінченною моделлю$\Gamma$, і нехай$c$ буде постійним символом не мовою$\Gamma$. $\Delta$Дозволяти множина всіх речень$\eqN[c][t]$ для$t$ терміна мовою$\Lang{L}$$\Gamma$, тобто

$$\Delta = \Setabs{\eqN[c][t]}{t \in \Trm[L]}.\nonumber$$ кінцева підмножина$\Gamma \cup \Delta$ може бути записана як$\Gamma' \cup \Delta'$, з$\Gamma' \subseteq \Gamma$ і$\Delta' \subseteq \Delta$. Оскільки$\Delta'$ є кінцевим, він може містити лише скінченно багато термінів. $a \in \Domain{M}$Дозволяти бути елементом$\Domain{M}$ не вибрано жодним з них, і нехай$\Struct{M'}$ буде структура, яка так само$\Struct{M}$, як, але також$\Assign{c}{M'} = a$. Так як$a \neq \Value{t}{M}$ за все$t$ відбувається в$\Delta'$,$\Sat{M'}{\Delta'}$. Так як$\Sat{M}{\Gamma}$$\Gamma' \subseteq \Gamma$, і$c$ не зустрічається в$\Gamma$, теж$\Sat{M'}{\Gamma'}$. Разом,$\Sat{M'}{\Gamma' \cup \Delta'}$ для кожного кінцевого$\Gamma' \cup \Delta'$ підмножини$\Gamma \cup \Delta$. Таким чином, кожен кінцевий$\Gamma \cup \Delta$ підмножина задовольняється. За компактності$\Gamma \cup \Delta$ сама по собі задовольняється. Так з'являються моделі$\Sat{M}{\Gamma \cup \Delta}$. Кожен такий$\Struct{M}$ є зразком$\Gamma$, але не покривається, так як$\Value{c}{M} \neq \Value{t}{M}$ для всіх$t$ умов$\Lang{L}$.

Приклад$\PageIndex{2}$

Розглянемо мову,$\Lang{L}$ що містить символ присудка$<$, постійні символи$\Obj{0}$$\Obj{1}$, і символи функції$+$,$\times$,$-$,$\div$. $\Gamma$Дозволяти бути сукупністю всіх речень в цій мові істинно в$\Struct{Q}$ області$\Rat$ і очевидних тлумачень. $\Gamma$це сукупність всіх речень$\Lang{L}$ істинних про раціональні числа. Звичайно, в$\Rat$ (і навіть в$\Real$), немає чисел, які більше,$0$ але менше, ніж$1/k$ для всіх$k \in \PosInt$. Таке число, якби воно існувало, було б нескінченно малим: ненульовим, але нескінченно маленьким. Теорема компактності показує, що існують моделі,$\Gamma$ в яких існують нескінченності:$\Delta$ Дозволяти бути$\{0<c\} \cup \Setabs{c < (\Obj{1} \div \num{k})}{k \in \PosInt}$ (де$\num{k} = (\Obj{1} + (\Obj{1} + \dots + (\Obj{1} + \Obj{1})\dots))$ з$k$$\Obj{1}$). Для будь-якого$\Delta_0$ скінченного підмножини$\Delta$ існує$K$ таке, що всі пропозиції$c < (\Obj{1} \div \num{k})$ в$\Delta_0$ have$k < K$. Якщо ми розширимо$\Struct{Q}$ до$\Struct{Q'}$ з$\Assign{c}{Q'} = 1/K$ ми маємо$\Sat{Q'}{\Gamma \cup \Delta_0}$, що, і так кінцево$\Gamma \cup \Delta$ задовольняється (Вправа: доведіть це детально). За компактності,$\Gamma \cup \Delta$ задовольняється. Будь-яка модель$\Struct{S}$$\Gamma \cup \Delta$ містить нескінченно мале, а саме$\Assign{c}{S}$.

Проблема$\PageIndex{2}$

У стандартній моделі арифметики немає елемента$\Struct{N}$,$k \in \Domain{N}$ який задовольняє кожну формулу$\num{n} < x$ (де$\num{n}$$\Obj{0}^{\prime\dots\prime}$$n$$\prime$ with's). Використовуйте теорему компактності, щоб показати, що набір речень в мові арифметики, які є істинними в стандартній моделі арифметики, також$\Struct{N}$ вірні в структурі$\Struct{N'}$, яка містить елемент, який задовольняє кожній формулі. $\num{n} < x$.

Приклад$\PageIndex{3}$

Ми знаємо, що логіка першого порядку з присудком ідентичності може висловити, що розмір домену повинен мати якийсь мінімальний розмір: речення$A_{\ge n}$ (яке говорить «є принаймні$n$ різні об'єкти») вірно лише в структурах, де$\Domain{M}$ має принаймні $n$об'єкти. Так що, якщо ми візьмемо,

$$\Delta = \Setabs{A_{\ge n}}{n \ge 1}\nonumber$$ то будь-яка модель$\Delta$ повинна бути нескінченною. Таким чином, ми можемо гарантувати, що теорія має лише нескінченні моделі, додавши$\Delta$ до неї: моделі$\Gamma \cup \Delta$ - це все і лише нескінченні моделі$\Gamma$.

Таким чином, логіка першого порядку може виражати нескінченність. Теорема компактності показує, що вона не може виражати кінцевість, однак. Бо припустимо, що деякі сукупності пропозицій$\Lambda$ були задоволені у всіх і тільки кінцевих структурах. Тоді$\Delta \cup \Lambda$ кінцево задовольняється. Чому? Припустимо$\Delta' \cup \Lambda' \subseteq \Delta \cup \Lambda$, є кінцевим з$\Delta' \subseteq \Delta$ і$\Lambda' \subseteq \Lambda$. $n$Дозволяти найбільшу кількість таких, що$A_{\ge n} \in \Delta'$. $\Lambda$, будучи задоволеним у всіх кінцевих структурах, має модель$\Struct{M}$ з скінченно багатьма, але$\ge n$ елементами. Але потім$\Sat{M}{\Delta' \cup \Lambda'}$. За компактності,$\Delta \cup \Lambda$ має нескінченну модель, що суперечить припущенню, що$\Lambda$ задовольняється тільки в скінченних структурах.