Skip to main content
LibreTexts - Ukrayinska

10.5: Лемма Лінденбаума

  • Page ID
    52828
  • \( \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

    Зараз ми доведемо лему, яка показує, що будь-який послідовний набір речень міститься в деякому наборі речень, який є не просто послідовним, але й повним. Доказ працює, додаючи одне речення за раз, гарантуючи на кожному кроці, що набір залишається послідовним. Робимо це так, щоб за кожен\(A\), або\(A\) або\(\lnot A\) додавався на якомусь етапі. Об'єднання всіх етапів у цій конструкції потім містить\(A\) або його заперечення\(\lnot A\) і, таким чином, завершено. Це також послідовно, оскільки ми подбали про те, щоб на кожному етапі не вводити невідповідність.

    Лемма\(\PageIndex{1}\): Lindenbaum’s Lemma

    Кожен послідовний набір\(\Gamma\) мовою\(\Lang{L}\) можна розширити до повного та послідовного набору\(\Gamma^*\).

    Доказ. Нехай\(\Gamma\) буде послідовним. Нехай\(A_0\)\(A_1\),,... бути перерахуванням всіх пропозицій\(\Lang L\). Визначте\(\Gamma_0 = \Gamma\), і\[\Gamma_{n+1} = \begin{cases} \Gamma_n \cup \{ A_n \} & \textrm{if $\Gamma_n \cup \{A_n\}$ is consistent;} \\ \Gamma_n \cup \{ \lnot A_n \} & \textrm{otherwise.} \end{cases}\nonumber\] нехай\(\Gamma^* = \bigcup_{n \geq 0} \Gamma_n\).

    Кожен\(\Gamma_n\) послідовний:\(\Gamma_0\) узгоджений за визначенням. Якщо\(\Gamma_{n+1} = \Gamma_n \cup \{A_n\}\), це тому, що останній послідовний. Якщо це не так,\(\Gamma_{n+1} = \Gamma_n \cup \{\lnot A_n\}\). Ми повинні переконатися, що\(\Gamma_n \cup \{\lnot A_n\}\) це послідовно. Припустимо, це не так. Тоді обидва\(\Gamma_n \cup \{A_n\}\) і\(\Gamma_n \cup \{\lnot A_n\}\) несумісні. Це означає, що це\(\Gamma_n\) було б неузгоджено Пропозиціями 8.9.3 та 9.8.3, всупереч індукційній гіпотезі.

    Для кожного\(n\) і кожного\(i < n\),\(\Gamma_i \subseteq \Gamma_n\). Це випливає за допомогою простої індукції на\(n\). Бо\(n=0\), немає\(i < 0\), тому претензія тримається автоматично. Для індуктивного кроку, припустимо, це вірно для\(n\). У нас є\(\Gamma_{n+1} = \Gamma_n \cup \{A_n\}\) або\(= \Gamma_n \cup \{\lnot A_n\}\) по будівництву. Отже\(\Gamma_n \subseteq \Gamma_{n+1}\). Якщо\(i < n\), то\(\Gamma_i \subseteq \Gamma_n\) шляхом індуктивної гіпотези, і так\(\subseteq \Gamma_{n+1}\) по транзитивності\(\subseteq\).

    З цього випливає, що кожна кінцева\(\Gamma^*\) підмножина є підмножиною\(\Gamma_n\) для деяких\(n\), оскільки кожен\(B \in \Gamma^*\) ще не в\(\Gamma_0\) додається на певному етапі\(i\). Якщо\(n\) останній з них, то всі\(B\) в кінцевому підмножині знаходяться в\(\Gamma_n\). Таким чином, кожна кінцева підмножина\(\Gamma^*\) є послідовним. За пропозиціями 8.8.5 і 9.7.5,\(\Gamma^*\) є послідовним.

    Кожне речення\(\Frm[L]\) з'являється у списку, який використовується для визначення\(\Gamma^*\). Якщо\(A_n \notin \Gamma^*\), то це тому, що\(\Gamma_n \cup \{A_n\}\) було непослідовним. Але потім\(\lnot A_n \in \Gamma^*\), так\(\Gamma^*\) завершено. ◻