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

Last updated
Save as PDF

Page ID: 52812

\( \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

Визначення\(\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\), це повно і послідовно. Потім:

Якщо\(\Gamma \Proves A\), то\(A \in \Gamma\).
\(A \land B \in \Gamma\) iff both \(A \in \Gamma\) and \(B \in \Gamma\).
\(A \lor B \in \Gamma\) iff either \(A \in \Gamma\) or \(B \in \Gamma\).
\(A \lif B \in \Gamma\) iff either \(A \notin \Gamma\) or \(B \in \Gamma\).

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

Якщо\(\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\).
Вправа.
Спочатку покажемо, що якщо\(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\), у міру необхідності.
Вправа.

◻

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

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