בלוגיקה, פרדוקס התלויות האינסופיות הוא פרדוקס המבוסס על התייחסות עצמית, ומשתמש במספר אינסופי של פסוקים. קיימת מחלוקת האם הפרדוקס כולל התייחסות מעגלית לעצמו, או לא.[1]
רקע
התייחסות עצמית של קבוצת פסוקים כוללת התייחסות שלהם לערך האמת של עצמם, כגון פרדוקס השקרן:
- משפט מספר 1 הוא שקר.
לא ניתן לשים ערך אמת למשפט זה: אם הוא אמת הוא שקר, ואם הוא שקר הוא אמת.
גם אם אוסרים התייחסות של משפט לעצמו, ניתן למצוא פרדוקס עם התייחסות מעגלית בצורה הבאה:
- משפט 2 הוא אמת.
- משפט 1 הוא שקר.
גם קבוצה זאת היא פרדוקסלית: אם משפט 1 הוא אמת, גם 2 הוא אמת, ואז 1 הוא שקר. ואילו אם 1 הוא שקר, אז 2 הוא שקר, ואז 1 הוא אמת.
עם זאת, ניתן להראות שכל עוד קבוצת המשפטים היא סופית, תלות שאיננה מעגלית לא תוביל לסתירה. כדי להגדיר תלות מעגלית, נכין גרף שקודקודיו הם המשפטים, ויש קשת מפסוק i לפסוק j אם i מתייחס לערך האמת של j. אז אם יש בגרף מעגל, הקבוצה עשויה להכיל סתירה. אך אם אין מעגל, היא לא. הוכחה: נגדיר מיון טופולוגי על הגרף, ונעבור על הקודקודים שלו לפי הסדר ההפוך, כאשר עוברים על משפט רק לאחר שעברנו על כל המשפטים שהוא מתייחס אליהם. אז כאשר הגענו למשפט, ערך האמת של כל המשפטים שהוא מתייחס אליהם כבר נקבע, לכן גם ערך האמת שלו יכול להיקבע מבלי לחשוש לסתירה עם הפסוקים הקודמים.
לעומת זאת, כאשר הגרף אינסופי, גם אם אין בו מעגלים, ההוכחה הזאת לא תעבוד כי לא בהכרח אפשר להתחיל ממשפט שלא תלוי באף משפט אחר. ואכן ניתן למצוא קבוצה פרדוקסלית.
הפרדוקס
נתבונן בקבוצת המשפטים האינסופית הבאה:
- לכל i>1, משפט מספר i הוא שקר.
- לכל i>2, משפט מספר i הוא שקר.
באופן כללי, משפט מספר n אומר שלכל i>n, משפט מספר i הוא שקר.
אין פה תלות מעגלית, שכן כל משפט תלוי רק בערך האמת של המשפטים שאחריו.
נראה שלא ניתן להציב למשפטים ערך אמת: תחילה נניח שקיים משפט אמת, נסמנו n. אז לכל i>n, משפט i הוא שקר, ועל כן גם משפט n+1 הוא אמת, בסתירה לכך שהוא שקר.
כעת נניח שכל המשפטים הם שקר, אז נובע שמשפט 1 (ולמעשה כל משפט) הוא אמת.
שתי האפשרויות מובילות לסתירה.
קישורים חיצוניים
הערות שוליים
