עצמאות (לוגיקה מתמטית)

טענה היא "עצמאית" ביחס למערכת אקסיומות אם לא ניתן להוכיח אותה ולא ניתן להוכיח את שלילתה מתוך אותן אקסיומות. מערכת הוכחה נקראת שלמה אם אין בה טענות עצמאיות.

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

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

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

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

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