שלמות
 |
ערך ללא מקורות
| |
| ערך ללא מקורות |
שלמות (באנגלית: Completeness) בלוגיקה ובלוגיקה מתמטית היא תכונה של מערכת אקסיומטית. מערכת נתונה של אקסיומות וכללי היסק היא שלמה אם אפשר להכריע בה לגבי כל נוסחה אמיתית, כלומר, אפשר להוכיח את הנוסחה או את שלילתה. במילים אחרות, אין בה טענות עצמאיות.
שלמות ונאותות
הלוגיקה בוחנת את תכונותיה הצורניות של כל מערכת לוגית אקסיומטית. מערכות פורמליות כאלו כוללות נוסחאות בנויות כהלכה מבחינה תחבירית, שחלקן מקבלות מעמד מיוחד של אקסיומות, וכן מערך של כללי היסק באמצעותם ניתן לבצע גזירות של נוסחאות אחדות מתוך נוסחאות אחרות, דהיינו להוכיח אותן. למחקר של התכונות של מערכות מסוג זה קוראים גם מטא-תאוריה או מטאלוגיקה. השלמות היא אחת התכונות החשובות ביותר של מערכות לוגיות. ייקל להבין אותה בהשוואה לשתי תכונות נוספות, עקביות ונאותות:
- עקביות (consistency) - זוהי תכונתן של מערכות לוגיות שאין סתירה בין אי אלו מן הטענות המוכלות בהן.
- שלמות (completeness) - זוהי תכונתן של מערכות לוגיות שבהן לגבי כל נוסחה אמיתית, ניתן לספק לה הוכחה מן האקסיומות.
- נאותות (soundness) - בניגוד לנאותות של טיעון, שהיא התכונה של טיעון תקף שבו כל ההנחות אמיתיות, נאותות של מערכת לוגית היא התכונה לפיה אם נוסחה מסוימת ניתנת להוכחה מן האקסיומות על פי חוקי התחשיב, אזי נוסחה זו אמיתית.
הוכחות לשלמות ולנאותות מעידות על הזיקה שבין התחביר (סינטקס) והסמנטיקה של המערכת. התחביר קובע איזו נוסחה היא תיאורמה (או משפט), דהיינו איזו נוסחה ניתנת לגזירה מן האקסיומות, באמצעות כללי ההיסק. הסמנטיקה קובעת איזו נוסחה היא טאוטולוגיה, דהיינו איזו נוסחה היא אמיתית בהכרח מכוח משמעותם של המונחים המקושרים בה והאופן בו הם מקושרים. לפי הגדרות אלו, למערכת יש שלמות, כאשר כל טאוטולוגיה היא גם תיאורמה. למערכת יש נאותות, כאשר כל תיאורמה היא טאוטלוגיה.
אי-שלמות
ניתן לראות כי התכונות נאותות ושלמות קשורות זו לזו, אף שלא כל מערכת נאותה היא גם שלמה. קורט גדל הוכיח ב-1931 שבכל מערכת לוגית שהיא חזקה מספיק יש נוסחאות אמיתיות שלא ניתן להוכיח אותן או את שלילתן. מערכת חזקה מספיק היא כל מערכת אפקטיבית ועקבית, המבוססת על שפה מסדר ראשון, שיש בה מספיק מושגים כדי לנסח טענות על כפל במספרים השלמים. מערכת כזו, הכוללת את האריתמטיקה בתוכה, היא המערכת שהציע ברטראנד ראסל לראשונה ב"פרינקיפיה מתמטיקה". מכאן ששפה אפקטיבית חזקה מספיק אינה יכולה להיות עקבית, נאותה ושלמה. חוק זה נקרא "משפט האי-שלמות של גדל", ובעקבותיו השתנה היחס של מתמטיקאים לתוכנית הילברט לבסס את כל המתמטיקה על קבוצה סופית של אקסיומות.
38373395שלמות