שלמות
English: Completeness

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

שלמות ונאותות

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

  • עקביות (consistency) - זוהי תכונתן של מערכות לוגיות שאין סתירה בין אי אלו מן הטענות המוכלות בהן.
  • שלמות (completeness) - זוהי תכונתן של מערכות לוגיות שבהן לגבי כל נוסחה אמיתית, ניתן לספק לה הוכחה מן האקסיומות.
  • נאותות (soundness) - בניגוד לנאותות של טיעון, שהיא התכונה של טיעון תקף שבו כל ההנחות אמיתיות, נאותות של מערכת לוגית היא התכונה לפיה אם נוסחה מסוימת ניתנת להוכחה מן האקסיומות על פי חוקי התחשיב, אזי נוסחה זו אמיתית.

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