Skip to main content
LibreTexts - Ukrayinska

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

Template:MathJaxZach

Зараз ми доведемо лему, яка показує, що будь-який послідовний набір речень міститься в деякому наборі речень, який є не просто послідовним, але й повним. Доказ працює, додаючи одне речення за раз, гарантуючи на кожному кроці, що набір залишається послідовним. Робимо це так, щоб за кожен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.

нехайΓ=n0Γn.

КоженΓ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Γ, такΓ завершено. ◻

  • Was this article helpful?