משפט האי-גדירות של טרסקי
בלוגיקה מתמטית, משפט אי הגדירות של טרסקי הוא משפט הטוען שאין דרך להגדיר בתוך תורה נתונה, מספיק עשירה, את אוסף המשפטים שנכונים בה. באופן לא פורמלי, המשפט אומר כי אם ניתן לנסח במסגרת תורה מסוימת חלק מספיק גדול מתוך האריתמטיקה של המספרים הטבעיים, ובפרט ניתן לקודד כל נוסחה באמצעות מספר טבעי, אז לא קיימת נוסחה עם משתנה חופשי x שמשמעותה "המשפט המיוצג על ידי המספר x הוא נכון".
משפט זה התגלה באופן בלתי תלוי על ידי קורט גדל, במסגרת עבודתו על משפטי האי-שלמות ועל ידי טרסקי בשנת 1936.
ניסוח מדויק
נניח כי T היא תורה שלמה בשפה מסדר ראשון L, שניתן להגדיר בתוכה חלק גדול מספיק מהאריתמטיקה של הטבעיים, כך שניתן לתאר בתוכה את מספרי גדל, אז אין נוסחה True בשפה L כך שלכל משפט A מתקיים: (כאשר g(A) הוא מספר גדל המתאים לנוסחה A).
![{\displaystyle True[g(A)]\iff A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78436131256537f13904cbcbf6be87d4bfb7624a)
הוכחה
ההוכחה היא הוכחה על דרך השלילה, ומכילה רעיונות דומים לרעיונות של הוכחת משפטי האי שלמות.
נגדיר את הפונקציה d (פונקציית הלכסון):
![{\displaystyle d(g(\varphi ))=g(\varphi [g(\varphi )])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5da5d8fbfd860cf4697fddb586c3494fa0ee041a)
d היא הפונקציה שמקבלת מספר גדל של נוסחה ומחזירה את מספר גדל של הנוסחה המתקבלת מהצבת מספר גדל של הנוסחה המקורית במשתנה הראשון של הנוסחה המקורית (במידה והנוסחה המקורית היא חסרת משתנים נוסיף לה משתנה דמה). כיוון ש-d ניתנת להגדרה בתוך L ניתן גם להגדיר את הנוסחה הבאה במסגרת L:
![{\displaystyle \psi [g(A)]=\neg True[d(g(A))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d8a8351e86d1d7cb96f68bb9c7f120ab0fd4fff)
כעת נברר את ערך האמת של :
![{\displaystyle \psi [g(\psi )]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33bb48be64d6a63f94460974a428894626315be4)
![{\displaystyle \psi [g(\psi )]\iff \neg True[d(g(\psi )]\iff \neg True[g(\psi [g(\psi )])]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9246b3ffa72f45555f4bd7107622ff6a80038d63)
כלומר נוסחה זו נכונה אם ורק אם True תטען כי היא שגויה ולהפך, בסתירה להגדרת הנוסחה True.
נעיר כי מתוך ההוכחה ניתן לראות כי אין צורך להשתמש במלוא הכוח של מספרי גדל (ההוכחה אינה מתייחסת לשאלות של רקוסיביות), וניתן להחיל אותה במקרים רחבים יותר.
הערות
משפט אי הגדירות יכול לשמש כשלב בהוכחת משפטי האי-שלמות של גדל - אם כל משפט נכון היה ניתן להוכחה, אז כיוון שקיום הוכחה עבור משפט נתון ניתן להגדרה בשפות המכילות את האריתמטיקה, היינו מקבלים הגדרת אמת.
אי היכולת להגדיר את האמת עבור תורה מסוימת לא מונע את האפשרות שתהיה לה הגדרת אמת בתורה חזקה יותר. למשל בתורת הקבוצות יש הגדרת אמת עבור האריתמטיקה של הטבעיים, ולמעשה על כל מבנה המוגדר על קבוצה. בנוסף, ניתן לספק הגדרת אמת עבור השפה של תורת הקבוצות כולה בתנאי שאנחנו מגבילים את הסיבוך של הנוסחאות (במובן של מספר הכמתים המופיעים בנוסחאות).
24800318משפט האי-גדירות של טרסקי