שינויים

[http://en.wikipedia.org/wiki/First-order_logic לוגיקה מסדר ראשון] הינה היא שפת הבסיס של המתמטיקטים המתמטיקה, כפי שלמדנו בקורס [[88-101 חשיבה מתמטית]]. זו שפה המכילה קשרים לוגיים (או, וגם, שלילה, גרירה), כמתים (לכל, קיים), פסוקים הבנויה מפסוקים ("לכל x קיים y הגדול ממנו") ופרדיקטים ("ל-x קיים y הגדול ממנו"), המחוברים באמצעות קשרים לוגיים (או, וגם, שלילה, גרירה) וכמתים (לכל, קיים). '''הוכחה''' בשפה זו היא אוסף משפטים אשר כל אחד נובע מקודמיו, או ידוע כנכון מהוכחה אחרת, או אקסיומה.

למדנו שעל מנת להעריך "גודל" של קבוצה אינסופית אנו משתמשים במושג [[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 6|עוצמותעוצמה]]. כמו כן, ראינו ב[[מדיה:11BdidaTargil5.pdf|תרגיל]] כי אוסף המילים מעל אלפאבית סופי הוא בן מנייה. באופן דומה, אוסף המשפטים והטקסטים הסופיים בכלל הוא בן מנייה. נשתמש בעובדה זו בהמשך.

'''הגדרה:''' בלוגיקה מסדר ראשון, '''מערכת אקסיומטית ראוייה''' הינה אוסף סופי או בן מנייה של משפטים מהשפה הנקראים '''אקסיומות''' המכיל את אוסף האקסיומות הבסיסיות של האריתמטיקה (אלו המאפשרות לנו לבנות את המספרים הטבעיים)

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

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

::--מערכת אקסיומתית אקסיומטית ראוייה הינה היא שלימה אם"ם ורק אם היא אינה עקבית.

::--מערכת אקסיומתית אקסיומטית ראוייה הינה עקבית אם"ם לא ניתן להוכיח שהיא עקבית (על ידי הוכחה בתוך התאוריה)

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