Skip to main content
LibreTexts - Ukrayinska

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

  1. Last updated
  2. Save as PDF
  • Page ID
    52798

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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}\).