10.5: Лемма Лінденбаума
Зараз ми доведемо лему, яка показує, що будь-який послідовний набір речень міститься в деякому наборі речень, який є не просто послідовним, але й повним. Доказ працює, додаючи одне речення за раз, гарантуючи на кожному кроці, що набір залишається послідовним. Робимо це так, щоб за коженA, абоA або¬A додавався на якомусь етапі. Об'єднання всіх етапів у цій конструкції потім міститьA або його заперечення¬A і, таким чином, завершено. Це також послідовно, оскільки ми подбали про те, щоб на кожному етапі не вводити невідповідність.
Лемма10.5.1: Lindenbaum’s Lemma
Кожен послідовний набірΓ мовою\LangL можна розширити до повного та послідовного наборуΓ∗.
Доказ. НехайΓ буде послідовним. НехайA0A1,,... бути перерахуванням всіх пропозицій\LangL. ВизначтеΓ0=Γ, іΓn+1={Γn∪{An}if Γn∪{An} is consistent;Γn∪{¬An}otherwise.
КоженΓn послідовний:Γ0 узгоджений за визначенням. ЯкщоΓn+1=Γn∪{An}, це тому, що останній послідовний. Якщо це не так,Γn+1=Γn∪{¬An}. Ми повинні переконатися, щоΓn∪{¬An} це послідовно. Припустимо, це не так. Тоді обидваΓn∪{An} іΓn∪{¬An} несумісні. Це означає, що цеΓn було б неузгоджено Пропозиціями 8.9.3 та 9.8.3, всупереч індукційній гіпотезі.
Для кожногоn і кожногоi<n,Γi⊆Γn. Це випливає за допомогою простої індукції наn. Боn=0, немаєi<0, тому претензія тримається автоматично. Для індуктивного кроку, припустимо, це вірно дляn. У нас єΓn+1=Γn∪{An} або=Γn∪{¬An} по будівництву. ОтжеΓn⊆Γn+1. Якщоi<n, тоΓi⊆Γn шляхом індуктивної гіпотези, і так⊆Γn+1 по транзитивності⊆.
З цього випливає, що кожна кінцеваΓ∗ підмножина є підмножиноюΓn для деякихn, оскільки коженB∈Γ∗ ще не вΓ0 додається на певному етапіi. Якщоn останній з них, то всіB в кінцевому підмножині знаходяться вΓn. Таким чином, кожна кінцева підмножинаΓ∗ є послідовним. За пропозиціями 8.8.5 і 9.7.5,Γ∗ є послідовним.
Кожне речення\Frm[L] з'являється у списку, який використовується для визначенняΓ∗. ЯкщоAn∉Γ∗, то це тому, щоΓn∪{An} було непослідовним. Але потім¬An∈Γ∗, такΓ∗ завершено. ◻