הוכחות מתמטיות/לוגיקה/משפט לינדנבאום

אם $T^{\prime }=<L^{\prime },{𝔄}^{\prime }>$ היא תורה עקבית, אזי קיימת קבוצת אקסיומות ${𝔄}^{″}$ כך ש-${𝔄}^{\prime }\subseteq {𝔄}^{″}$ ו-$T^{″}=<L^{\prime },{𝔄}^{″}>$ תורה שלמה.

הוכחה

נגדיר $E$ כקבוצת כל הנוסחאות הסגורות בשפה $L^{\prime }$.
נגדיר $𝒥=\{D\subseteq E|{𝔄}^{\prime }\cup D\text{ is consistent}\}$.
$𝒥$ לא ריקה, כי ${𝔄}^{\prime }$ עקבית ולכן $\mathrm{\varnothing }\in 𝒥$.
$𝒥$ היא מטיפוס סופי. זאת מפני שהיסקים הם סופיים, כלומר מסתמכים על קבוצה סופית של אקסיומות, ולכן מקבוצה ניתן להסיק סתירה אם ורק אם מכל תת-קבוצה סופית שלה ניתן להסיק סתירה.

מלמת טייכמילר-טיוקי, שמופיעה מטה, קיים איבר מקסימלי $M\in 𝒥$.
נגדיר ${𝔄}^{″}={𝔄}^{\prime }\cup M$.
$T^{″}$ עקבית מתוך הגדרת $𝒥$, נוכיח כי היא גם שלמה.

תהי נוסחה סגורה $A$. נראה כי ${⊢}_{{𝔄}^{″}}A$ או ${⊢}_{{𝔄}^{″}}\mathrm{\neg }A$.
אם ${⊢}_{{𝔄}^{″}}A$ סיימנו, כעת נניח כי ${⊬}_{{𝔄}^{″}}A$.
נניח בשלילה $\mathrm{\neg }A\notin M$, אזי ${𝔄}^{″}\cup \{\mathrm{\neg }A\}$ אינה עקבית מתוך מקסימליות $M$, כלומר, ניתן להסיק בה סתירה: ${⊢}_{{𝔄}^{″}\cup \{\mathrm{\neg }A\}}B\wedge \mathrm{\neg }B$.
לפי משפט הדדוקציה: ${⊢}_{{𝔄}^{″}}\mathrm{\neg }A\to B\wedge \mathrm{\neg }B$, אך זוהי גרירה טאוטולוגית של ${⊢}_{{𝔄}^{″}}A$ בסתירה להנחה.
כלומר $\mathrm{\neg }A\in M$, וממילא ${⊢}_{{𝔄}^{″}}\mathrm{\neg }A$ כנדרש.

למת טייכמילר-טיוקי

הגדרות

נניח ש-$E$ קבוצה, ו-$𝒥\subseteq P(E)$ אוסף תת-קבוצות של $E$.
$𝒥$ תיקרא מטיפוס סופי אם מתקיים $D\in 𝒥$ אם ורק אם כל תת-קבוצה סופית $D_0\subseteq D$ מקיימת $D_0\in 𝒥$.

למת טייכמילר-טיוקי

אם $𝒥$ לא ריקה מטיפוס סופי, אזי יש $𝒥$ איבר מקסימלי.
כלומר, קיים $M\in 𝒥$, כך שאם $M\subseteq N\in 𝒥$ אז $M=N$.
הערה: כדי להוכיח למה זו אנו זקוקים לאקסיומת הבחירה.