הפרדוקס של ברי

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

תיאור הפרדוקס

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

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

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

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

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

פתרון הפרדוקס

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

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

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

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

ראו גם

• משפט האי-שלמות של צ'ייטין

לקריאה נוספת

• מריוס כהן, "פרדוקס ברי", גליליאו 103, מרץ 2007.

קישורים חיצוניים

• גדי אלכסנדרוביץ', הפוסט המעניין ביותר שלא ניתן לתאר בכותרת שלו, באתר "לא מדויק"