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

אם היא תורה עקבית, אזי קיימת קבוצת אקסיומות כך ש- ו- תורה שלמה.

הוכחה

עריכה

נגדיר   כקבוצת כל הנוסחאות הסגורות בשפה  .
נגדיר  .
  לא ריקה, כי   עקבית ולכן  .
  היא מטיפוס סופי. זאת מפני שהיסקים הם סופיים, כלומר מסתמכים על קבוצה סופית של אקסיומות, ולכן מקבוצה ניתן להסיק סתירה אם ורק אם מכל תת-קבוצה סופית שלה ניתן להסיק סתירה.

מלמת טייכמילר-טיוקי, שמופיעה מטה, קיים איבר מקסימלי  .
נגדיר  .
  עקבית מתוך הגדרת  , נוכיח כי היא גם שלמה.

תהי נוסחה סגורה  . נראה כי   או  .
אם   סיימנו, כעת נניח כי  .
נניח בשלילה  , אזי   אינה עקבית מתוך מקסימליות  , כלומר, ניתן להסיק בה סתירה:  .
לפי משפט הדדוקציה:  , אך זוהי גרירה טאוטולוגית של   בסתירה להנחה.
כלומר  , וממילא   כנדרש.

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

עריכה

הגדרות

עריכה

נניח ש-  קבוצה, ו-  אוסף תת-קבוצות של  .
  תיקרא מטיפוס סופי אם מתקיים   אם ורק אם כל תת-קבוצה סופית   מקיימת  .

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

עריכה

אם   לא ריקה מטיפוס סופי, אזי יש   איבר מקסימלי.
כלומר, קיים  , כך שאם   אז  .
הערה: כדי להוכיח למה זו אנו זקוקים לאקסיומת הבחירה.