לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

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

הוכחה

[עריכה]

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

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

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

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

[עריכה]

הגדרות

[עריכה]

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

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

[עריכה]

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