10.10: Пряме доказ теореми компактності

Template:MathJaxZach

Теорему компактності можна довести безпосередньо, не звертаючись до теореми повноти, використовуючи ті ж ідеї, що і в доведенні теореми повноти. На доказ теореми повноти ми почали з$\Gamma$ послідовного набору речень, розширили його до послідовного, насиченого і повного набору$\Gamma^*$ пропозицій, а потім показали, що в терміні модель$\Struct{M(\Gamma^*)}$ побудована з $\Gamma^*$, всі речення$\Gamma$ є істинними,$\Gamma$ тому задовольняється.

Ми можемо використовувати той самий метод, щоб показати, що кінцево задовільний набір речень є задовільним. Нам просто потрібно довести відповідні версії результатів, що призводять до правдивої леми, де ми замінюємо «послідовний» на «кінцево задовольняється».

Пропозиція$\PageIndex{1}$

$\Gamma$Припустимо, повна і скінченно задовольняється. Потім:

1. $(A \land B) \in \Gamma$ iff both $A \in \Gamma$ and $B \in \Gamma$.

2. $(A \lor B) \in \Gamma$ iff either $A \in \Gamma$ or $B \in \Gamma$.

3. $(A \lif B) \in \Gamma$ iff either $A \notin \Gamma$ or $B \in \Gamma$.

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

Доведіть пропозицію$\PageIndex{1}$. Уникайте використання$\Proves$.

Лемма$\PageIndex{1}$

Кожен нескінченно задовольняється набір$\Gamma$ може бути продовжений до насиченого скінченно задовольняється набору$\Gamma'$.

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

Доведіть Лемма$\PageIndex{1}$. (Підказка: Найважливішим кроком$\Gamma_n$ є показати, що він є кінцевим задоволенням, так само$\Gamma_n \cup \{D_n\}$, без будь-якого звернення до похідних або послідовності.)

Пропозиція$\PageIndex{2}$

Припустимо,$\Gamma$ це повна, скінченно задовольняється і насичена.

1. $\lexists{x}{A(x)} \in \Gamma$ iff $A(t) \in \Gamma$ for at least one closed term $t$.

2. $\lforall{x}{A(x)} \in \Gamma$ iff $A(t) \in \Gamma$ for all closed terms $t$.

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

Доведіть пропозицію$\PageIndex{2}$.

Лемма$\PageIndex{2}$

Кожен скінченно задовільний набір$\Gamma$ може бути розширений до повного і кінцево задовільного набору$\Gamma^*$.

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

Доведіть Лемма$\PageIndex{2}$. (Підказка: вирішальним кроком$\Gamma_n$ є показати, що якщо кінцево задовольняється, то$\Gamma_n \cup \{A_n\}$ або або$\Gamma_n \cup \{\lnot A_n\}$ є кінцево задовольняється.)

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

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

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

Тепер припустимо, що$\Gamma$ це остаточно задовольняється. За Lemma$\PageIndex{1}$, there is a finitely satisfiable, saturated set $\Gamma' \supseteq \Gamma$. By Lemma$\PageIndex{2}$,${\Gamma'}$ може бути продовжений до повного і кінцево задовольняє набір$\Gamma^*$, і$\Gamma^*$ is still saturated. Побудувати термінову модель$\Struct{M(\Gamma^*)}$, як у визначенні 10.6.1. Зверніть увагу, що Пропозиція 10.6.1 не покладалася на той факт, що$\Gamma^*$ is consistent (or complete or saturated, for that matter), but just on the fact that $\Struct{M(\Gamma^*)}$ is covered. Доказ істини Лемма (Lemma 10.6.1) проходить, якщо ми замінимо посилання на Пропозиція 10.3.1 та Пропозиція 10.4.2 за посиланнями на Пропозиція$\PageIndex{1}$ and Proposition $\PageIndex{2}$. ◻

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

Випишіть повне доказ Лемми Істини (Lemma 10.6.1) у версії, необхідній для доказу теореми$\PageIndex{1}$.