משפטי אי השלימות של גדל (Gödel): הבדלים בין גרסאות בדף
אין תקציר עריכה |
אין תקציר עריכה |
||
| שורה 3: | שורה 3: | ||
למדנו שעל מנת להעריך "גודל" של קבוצה אינסופית אנו משתמשים במושג [[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 6|עוצמות]]. כמו כן, ראינו ב[[מדיה:11BdidaTargil5.pdf|תרגיל]] כי אוסף המילים מעל אלפאבית סופי הוא בן מנייה. באופן דומה, אוסף המשפטים והטקסטים הסופיים בכלל הוא בן מנייה. נשתמש בעובדה זו בהמשך. | למדנו שעל מנת להעריך "גודל" של קבוצה אינסופית אנו משתמשים במושג [[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 6|עוצמות]]. כמו כן, ראינו ב[[מדיה:11BdidaTargil5.pdf|תרגיל]] כי אוסף המילים מעל אלפאבית סופי הוא בן מנייה. באופן דומה, אוסף המשפטים והטקסטים הסופיים בכלל הוא בן מנייה. נשתמש בעובדה זו בהמשך. | ||
'''הגדרה:''' בלוגיקה מסדר ראשון, '''מערכת אקסיומטית ראוייה''' הינה אוסף סופי או בן מנייה של משפטים מהשפה הנקראים '''אקסיומות''' המכיל את אוסף האקסיומות הבסיסיות של | '''הגדרה:''' בלוגיקה מסדר ראשון, '''מערכת אקסיומטית ראוייה''' הינה אוסף סופי או בן מנייה של משפטים מהשפה הנקראים '''אקסיומות''' המכיל את אוסף האקסיומות הבסיסיות של האריתמטיקה (המאפשרות לנו לבנות את המספרים הטבעיים) | ||
'''הגדרה:''' מערכת אקסיומתית נקראת '''עקבית''' אם לא קיים משפט בתאוריה שניתן להוכחה וגם השלילה שלו ניתנת להוכחה. | '''הגדרה:''' מערכת אקסיומתית נקראת '''עקבית''' אם לא קיים משפט בתאוריה שניתן להוכחה וגם השלילה שלו ניתנת להוכחה. | ||
'''הגדרה:''' מערכת אקסיומתית נקראת '''שלימה''' אם ניתן להוכיח או להפריך כל משפט הניתן לניסוח בתאוריה. | '''הגדרה:''' מערכת אקסיומתית נקראת '''שלימה''' אם ניתן להוכיח או להפריך כל משפט הניתן לניסוח בתאוריה. | ||
גרסה מ־14:15, 12 באוקטובר 2011
לוגיקה מסדר ראשון הינה שפת הבסיס של המתמטיקטים כפי שלמדנו בקורס 88-101 חשיבה מתמטית. זו שפה המכילה קשרים לוגיים (או, וגם, שלילה, גרירה), כמתים (לכל, קיים), פסוקים ("לכל x קיים y הגדול ממנו") ופרדיקטים ("ל-x קיים y הגדול ממנו"). הוכחה בשפה זו היא אוסף משפטים אשר כל אחד נובע מקודמיו, או ידוע כנכון מהוכחה אחרת, או אקסיומה.
למדנו שעל מנת להעריך "גודל" של קבוצה אינסופית אנו משתמשים במושג עוצמות. כמו כן, ראינו בתרגיל כי אוסף המילים מעל אלפאבית סופי הוא בן מנייה. באופן דומה, אוסף המשפטים והטקסטים הסופיים בכלל הוא בן מנייה. נשתמש בעובדה זו בהמשך.
הגדרה: בלוגיקה מסדר ראשון, מערכת אקסיומטית ראוייה הינה אוסף סופי או בן מנייה של משפטים מהשפה הנקראים אקסיומות המכיל את אוסף האקסיומות הבסיסיות של האריתמטיקה (המאפשרות לנו לבנות את המספרים הטבעיים)
הגדרה: מערכת אקסיומתית נקראת עקבית אם לא קיים משפט בתאוריה שניתן להוכחה וגם השלילה שלו ניתנת להוכחה.
הגדרה: מערכת אקסיומתית נקראת שלימה אם ניתן להוכיח או להפריך כל משפט הניתן לניסוח בתאוריה.