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

Last updated
Save as PDF

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^*$ завершено. ◻