10.3: Повні послідовні набори речень

Template:MathJaxZach

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

Набір$\Gamma$ речень є повним iff для будь-якого речення$A$, або$A \in \Gamma$ або$\lnot A \in \Gamma$.

Повні комплекти пропозицій не залишають жодних питань без відповіді. Для будь-якого речення$\Gamma$ «говорить»$A$, якщо$A$ є істинним чи хибним. Важливість повних комплектів виходить за рамки доказу теореми про повноту. Наприклад, теорія, яка є повною та аксіоматизованою, завжди вирішується.

Повні послідовні набори важливі для підтвердження повноти, оскільки ми можемо гарантувати, що кожен послідовний набір речень$\Gamma$ міститься в повному послідовному наборі$\Gamma^*$. Повний послідовний набір містить для кожного речення$A$$A$ або його заперечення$\lnot A$, але не обидва. Це вірно, зокрема, для атомних речень, тому з повного узгодженого набору мовою, відповідним чином розширеної постійними символами, ми можемо побудувати структуру, де визначається інтерпретація символів присудків, відповідно до якої атомні речення знаходяться в$\Gamma^*$. Потім ця структура може бути показана, щоб зробити всі речення в$\Gamma^*$ (а отже, і всі ті в$\Gamma$) істинними. Доказ цього останнього факту вимагає, що$\lnot A \in \Gamma^*$ iff$A \notin \Gamma^*$,$(A \lor B) \in \Gamma^*$ iff$A \in \Gamma^*$ або$B \in \Gamma^*$, і т.д.

У наступному ми часто будемо мовчазно використовувати властивості рефлексивності, монотонності та перехідності$\Proves$ (див. Розділи 8.8 і 9.7).

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

Припустимо$\Gamma$, це повно і послідовно. Потім:

1. Якщо$\Gamma \Proves A$, то$A \in \Gamma$.

2. $A \land B \in \Gamma$ iff both $A \in \Gamma$ and $B \in \Gamma$.

3. $A \lor B \in \Gamma$ iff either $A \in \Gamma$ or $B \in \Gamma$.

4. $A \lif B \in \Gamma$ iff either $A \notin \Gamma$ or $B \in \Gamma$.

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

1. Якщо$\Gamma \Proves A$, то$A \in \Gamma$.

   Припустимо, що$\Gamma \Proves A$. Припустимо, навпаки, що$A \notin \Gamma$. Так як$\Gamma$ завершено,$\lnot A \in \Gamma$. За пропозиціями 8.9.3 і 9.8.3,$\Gamma$ є непослідовним. Це суперечить припущенню, яке$\Gamma$ є послідовним. Отже, це не може бути так$A \notin \Gamma$, так$A \in \Gamma$.

2. Вправа.

3. Спочатку покажемо, що якщо$A \lor B \in \Gamma$, то або$A \in \Gamma$ або$B \in \Gamma$. Припустимо$A \lor B \in \Gamma$, але$A \notin \Gamma$ і$B \notin \Gamma$. Так$\Gamma$ як повна,$\lnot A \in \Gamma$ і$\lnot B \in \Gamma$. За Пропозиціями 8.10.2 та 9.9.2, пункт (1),$\Gamma$ є непослідовним, протиріччям. Значить, або$A \in \Gamma$ або$B \in \Gamma$.

   Для зворотного напрямку припустимо, що$A \in \Gamma$ або$B \in \Gamma$. Пропозиціями 8.10.2 та 9.9.2, пункт (2),$\Gamma \Proves A \lor B$. За (1)$A \lor B \in \Gamma$, у міру необхідності.

4. Вправа.

◻

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

Заповніть доказ Пропозиції$\PageIndex{1}$.