בתשובה ליוסי, 29/06/04 23:04
 |
|
 |
||
|
||||
 |
אני מניח שכוונתך להוכחות קיום מתמטיות בהן מראים שמשהו ישנו אך לא מצביעים על בנייה מפורשת שלו. יש לעתים גם ויכוח על מהי "בנייה מפורשת"; מתמטיקאים מהזרם הקונסטרוקטיביסטי (במיוחד Brouwer) גילו נוקשות רבה בעניין הזה, ועל-כן אפילו את קיומם של מספרים ממשיים הם לא מוכנים לקבל. דוגמאות יותר סטנדרטיות הן אלו המסתמכות על אקסיומת-הבחירה, שהיא העיקרון האקסיומטי הבסיסי המאפשר להגיד "יש X" בלי להגיד איך לבנות אותו. למשל: * קיום סדר טוב על הממשיים. כאן מוכיחים שאפשר להגדיר יחס סדר על המספרים הממשיים באופן כזה שבכל קבוצה יהיה איבר קטן ביותר. הסדר הרגיל על הממשיים אינו כזה; למשל "המספרים הממשיים הגדולים מאפס" הם קבוצה שאין בה איבר קטן ביותר. אפשר להוכיח (אם מקבלים את אקסיומת הבחירה) ש*יש* סדר כזה, אבל לא ניתן לכתוב מפורשות מהו. * קיום קבוצה לא מדידה: נגדיר שני מספרים (ממשיים, בקטע [0,1] נניח) כשקולים אם ההפרש ביניהם הוא רציונלי, ונבחר נציג יחיד מכל מחלקת שקילות. הקבוצה המתקבלת היא כזו שאפשר לכסות את כל הקטע ע"י איחוד זר של הזזות שלה, ולכן לא ניתן לייחס לה שום "אורך". שוב, ההגדרה אינה קונסטרוקטיבית ומסתמכת על אקסיומת הבחירה. * הפרדוקס של באנאך-טרסקי (הסתכל בפתיל תחת תגובה 175833). ייתכן שכוונתך למצבים בעלי אופי אחר - למשל, יש הרבה משוואות דיפרנציאליות שלא ניתן לרשום את פתרונן כפונקציה "אלמנטרית" אבל קל להוכיח שיש פתרון כזה. אם מחשיבים טור חזקות כבנייה (וזה מאוד מאוד סביר), אז זו לא דוגמה טובה. עוד מקרה: המשחק של Gail. מציירים מלבן על דף משובץ, נניח עם 7 שורות ו-13 עמודות, ומוחקים את הפינה השמאלית התחתונה - היא לא חלק מהלוח. יש שני שחקנים, וכל שחקן בתורו בוחר משבצת לבנה כלשהי, וצובע בשחור אותה וגם את כל המשבצות הנמצאות או מעליה או מימין לה (או שניהם). מי שלא יכול לזוז (כי אין יותר משבצת לבנה) מפסיד. יש הוכחה קצרה ומקסימה1 לכך שלשחקן הצועד ראשון יש אסטרטגיה מנצחת: אם הוא משחק נכון, הוא יכול תמיד לנצח בלי קשר לחוכמתו של השחקן השני. מצד שני, אף אחד לא יודע מהי האסטרטגיה הזו. מצד שלישי, לכל לוח נתון אפשר (תאורטית) להעסיק מחשב כמה מיליוני שנים ולמצוא את האסטרטגיה הזו, כך שאין כאן בעייה תאורטית, רק פרקטית. מצד רביעי, למצוא את *כל* האסטרטגיות ל*כל* המלבנים אפילו עם מחשב אי-אפשר, למרות שההוכחה תופסת לכל מלבן שהוא. עזרתי? 1 זו חידה, אבל אם רוצים אסביר. |
 |
 |
 |
|
|
|
||
|
||||
|
הייתי מוסיף ואומר שהפילוסופיה של הוכחה בדרך השלילה היא מאוד בכיוון של הוכחה לא קונסטרוקטיבית. | |
|
|
|
|
|
||
|
||||
|
אני מבין למה אתה מתכוון, אבל סייג: הוכחה בדרך השלילה לרוב משמשת להראות שמשהו *לא* קיים, ואז אין כל כך שאלה של קונסטרוקטיביות. | |
|
|
|
|
|
||
|
||||
|
אין לי כרגע דוגמאות קונקרטיות, אבל אני זוכר בפירוש הוכחות שהולכות ככה: יש לפחות X אחד. הוכחה: נניח שאין אף X, מכאן ש.... ומכאן נובע ש 1=0, סתירה, ולכן קיים לפחות X יחיד. (כאשר X היא תופעה מתמטית כלשהי) |
|
|
|
|
|
|
||
|
||||
|
ייתכן, אבל לרוב "נניח שאין אף X" היא נקודת פתיחה קשה בהרבה מ-"נניח שיש X מוזר שכזה, עכשיו בוא נבחן אותו ו...". נראה לי שהוכחות מהסוג שלך קל להפוך להוכחות לא בשלילה. | |
|
|
|
|
|
||
|
||||
|
משפטים במתמטיקה נוטים להיות מרובי (>1) כמתים. ואז ההבדל בין "נניח שאין X" ו-"נניח שיש X מוזר" זה ענין של סמנטיקה. לדוגמא משפט נקודת השבת של בראור עצמו. אפשר להסתכל על הנחת השלילה בתור "נניח שקיימת פונקציה כך וכך ללא נקודת שבת". לחלופין אפשר לאמר "נתונה פונקציה כך וכך נניח שאין לה נקודת שבת". | |
|
|
|
|
|
||
|
||||
|
תודה רבה. נהניתי מאוד. עזרת לי מאוד | |
|
|
|
|
|
||
|
||||
|
(לקבוצה הלא-מדידה: איחוד זר של מספר *בן-מנייה* של הזזות שלה, כמובן). | |
|
|
|
|
|
||
|
||||
|
אתה יכול להרחיב קצת בעניין הקונסטרוקטיביסטים והממשיים? חשבתי שבנו אותם יופי. | |
|
|
|
|
|
||
|
||||
|
אני ממש כותב היום שטויות לרוב. התכוונתי לזרם האינטואיציוניסטי, שבראוור היה מראשיו. קונסטרוקטיביזם יש גם אבל זה משהו אחר קצת, אני חושב. רוב המתמטיקאים מקבלים ללא סייג את הבניות של הממשיים, כמו גם את ההוכחות שהם לא בני-מנייה וכו'. עם זאת, היו (וכנראה עדיין יש) מספר מתמטיקאים שהתעקשו שרק בניות מפורשות *וסופיות* הן לגיטימיות, וכל דבר אחר הוא מוקצה. רוב המספרים הממשיים אינם ניתנים לתיאור סופי - כאן "רוב" הוא פשוט "כולם, פרט למספר בן-מנייה". שורש שתיים, כמדומני, אינו פסול עבור האינטיאיציוניסט מפני שאפשר להסביר בדיוק מה לעשות איתו (אם מעלים אותו בריבוע, יוצא שתיים, וזה בעצם כל מה שצריך לדעת על שורש שתיים) ואף אפשר לתאר אלגוריתם סופי שמייצר מפורשות את כל ספרותיו. מצד שני, ההוכחה של תהליך האלכסון איננה בונה מספר ממשי במפורש, ועל כן אינה קבילה. כנ"ל ההוכחה הכללית שקבוצת החזקה היא בעלת עצמה גבוהה מהקבוצה המקורית, ועוד הוכחות מסוג זה. יתרה מזו, האינטואיציוניסטים לא קיבלו את חוק "השלישי הנמנע" לפיו או ש-A או שלא A, מפני שעבורם "נכונות" מתפרשת כ"יש הוכחה מפורשת"; על כן, הוכחות בדרך השלילה לא מקובלות עליהם: נכון, הוכחת ש(לא A) אינו נכון, אך בכך לא הראית (מפורשות) את A. כיום, לדעתי, הנושא הזה נדון במיוחד בחוגים פילוסופיים, ולא כל כך מעסיק את המתמטיקאים עצמם (בראוור, וגם קרונקר ובמידה מסויימת הרמן וייל, היו אינטאיציוניסטים, וגם מתמטיקאים מהשורה הראשונה). לא שזה הופך את התחום ללא מעניין - דווקא יש שאלות מסקרנות מאוד בפילוסופיה של המתמטיקה שהגישה האינטואיציוניסטית רלוונטית להן. קרונקר, אגב, היא בן-פלוגתא חריף מאוד של גאורג קנטור, אבי תורת הקבוצות, בשל גישתו האינטואיציוניסטית (שאז, נדמה לי, עוד לא קראו לה כך). |
|
|
|
|
|
|
||
|
||||
|
אינטואציוניזם הוא סוג של קונסטרקטיביזם. זה אולי לא כל כך מעסיק את המתמטיקאים אבל זה בהחלט לא תרגיל בפילוסופיה של המתמטיקה בלבד. לאינטואציוניזם יש השלכות מתמטיות אמיתיות ודי מדהימות/מגוכחות מנקודת מבט מתמטית רגילה. למשל, כל פונקציה היא רציפה. ובראוור אולי היה אינטואיציוניסט אבל זה לא הפריע לו להוכיח את המשפט שלו בצורה "קלאסית", קרי, בדרך השלילה. |
|
|
|
|
|
|
||
|
||||
|
ברור שזה לא "תרגיל בפילוסופיה בלבד", אבל רוב המתמטיקאים, עובדתית, מתייחסים לתחום כאל לא יותר מקוריוז, בדיוק מסיבות כמו זו שהזכרת: כל פונקציה היא רציפה? תן לי בלם... אנשים עם רקע בלוגיקה (כמוך) נוטים להכיר את התחום טוב יותר ולפעמים ממש להתעניין בו, אבל רוב המתמטיקאים ה*אמיתיים* (סתם, סתם) יודעים עליו די מעט. לדעתי, אגב, חבל; זה די מעניין. נדמה לי שאינטואיציוניסטים מקבלים הוכחות ב-PA. לפני מספר שנים ניגש מישהו לאנדרו ויילס ושאל אותו אם הוא סבור שההוכחה שלו ניתנת לפירמול ב-PA. ויילס ענה שאין לו מושג, והשואל ציין גם שהשאלה נראתה לו (לויילס) לא מעניינת במיוחד. |
|
|
|
|
|
|
||
|
||||
|
אנא הסבר. יש לי הרגשה שזה מתחיל במשהו כמו ''לפי פון-ניומן יש אסטרטגיה מנצחת או לראשון או לשני (אין במשחק תיקו). נניח כי יש אסטרטגיה מנצחת לשני...'' ופה בערך אני נתקע |
|
|
|
|
|
|
||
|
||||
|
אם אני זוכר נכון, הטריק הוא כזה: לפי פון נוימן יש אסטרטגיה מנצחת או לראשון או לשני. נניח כי יש אסטרטגיה מנצחת לשני. פירוש הדבר הוא כי *לכל* מהלך פתיחה של השחקן הראשון, יש לשחקן השני תגובה כזו שתביא למצב שממנו יש לו אסטרטגיית ניצחון. נניח שמהלך הפתיחה של השחקן הראשון הוא צביעת המשבצת הימנית העליונה. אז כל מהלך שהשחקן השחור יעשה עכשיו יהיה זהה למהלך פתיחה שהשחקן הלבן *יכול* לעשות. מכאן שבעצם התחלפו התפקידים - הלבן, באמצעות צביעת המשבצת הימנית העליונה העביר את הכדור למגרש של השחקן השחור, ואפשר להסתכל על המשחק כעת כאילו השחקן השחור התחיל. לכן, לכל מהלך של השחקן השחור יש תגובה של הלבן שתבטיח לו את הניצחון. אז ההנחה שלנו לפיה לשחור יש אסטרטגיה מנצחת שגויה, ולכן יש ללבן אסטרטגיה מנצחת. והיא כמובן... אופס. זה כבר לא כל כך ברור. (אנחנו רק יודעים שמאוד *לא* כדאי ללבן להתחיל עם צביעת המשבצת הימנית העליונה). |
|
|
|
|
|
|
||
|
||||
|
ההסבר שלך נכון, רק את המשפט בסוגריים בסוף לא הבנתי. איך אנו יודעים שלא רצוי שצעד הפתיחה יהיה המשבצת בפינה? יש לפחות לוח אחד שבו זה בדיוק המהלך המנצח (רמז: לוח די קטן...). | |
|
|
|
|
|
||
|
||||
|
טוב, נכון, בלוח של 2X2 זה מהלך הפתיחה הנכון, אבל אם אני לא טועה זה גם המקרה היחיד שבו זו הפתיחה הנכונה. בכל שאר המקרים, אם הלבן מתחיל במשבצת הימנית העליונה, השחור יכול לעשות לו בדיוק את מה שמתואר בפתרון - לבצע את מהלך הפתיחה של הלבן שמבטיח לו ניצחון. תגיד לי שאני לא היחיד שכשהוא כותב הסברים מתמטיים מגלה באמצע כמה שהוא טועה. עכשיו כשאני חושב על זה, ייתכן שאסטרטגיית הפתיחה המנצחת של לבן כוללת צביעה של המשבצת הימנית העליונה בהתחלה, ולכן השחור לא יכול לגנוב את האסטרטגיה הזו. נו טוב, כל יום לומדים דבר חדש. אגב, במקרה של 2X2, ובכלל בכל מקרה של לוח ריבועי, יש שיטה קונסטרוקטיבית להראות את האסטרטגיה המנצחת - הוא מסמן את המשבצת השמאלית התחתונה הלפני אחרונה, כך שנשארת רק שורה אחת ועמודה אחת, ומשחק באופן סימטרי לזה של השחור. (אם השחור הוריד שלוש משבצות מהשורה, הוא יוריד שלוש משבצות מהעמודה, וכן הלאה). בסופו של דבר השחור ייאלץ לבחור את המשבצת האחרונה. (זה ע"פ הגרסה של המשחק שאני מכיר, שבה מותר לבחור כל משבצת, ולא רק לבנה, ומפסיד האחרון שבוחר משבצת. אבל אני לא חושב שיש הבדל עקרוני בין הגרסאות). |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח שלוח 2x2 הוא המקרה היחיד שבו מהלך הפתיחה הנכון הוא הפינה הימנית למעלה, ובכל מקרה אני מקווה שאנו מסכימים שאין בידינו נימוק מדוע זה כך או אחרת. את הגרסה שלך של המשחק לא הבנתי. מותר לבחור משבצת שחורה? זה לעשות Pass, אז מתי מנצחים? |
|
|
|
|
|
|
||
|
||||
|
טוב, בגרסה שלי אין משבצות שחורות או לבנות, רק משבצות. כשבוחרים משבצת, מוחקים מהלוח את המלבן שהמשבצת הזו היא הפינה השמאלית התחתונה שלו. מי שבוחר את המשבצת האחרונה, מפסיד, והמשחק מתחיל על לוח שלא גזרו ממנו אף משבצת. בכל מקרה, כמו שכבר די ברור, לא קראתי כמו שצריך את התיאור שלך של המשחק, וחשבתי משום מה שעושים אותו על לוח שחמט. מכיוון ש''שחור'' שלך זה ''מחוק'' שלי, אי אפשר לבחור משבצת שחורה במשחק שתיארת, ושוב אני סתם מקשקש. אם כבר התבלבלתי, אפשר לשאול את השאלה האם אם משחקים את המשחק על לוח שחמט, כשמותר לבחור רק משבצת לבנה (ומשחירים את המשבצות ה''מחוקות), זה משנה משהו מהמשחק או מהאסטרטגיה. נראה לי שכן, כי הרי האלכסון המשני הוא שחור, אז אי אפשר לבחור משבצות עליו. |
|
|
|
|
|
|
||
|
||||
|
אכן דיברנו על אותו משחק. וריאציית השחמט שלך נראית לי מסובכת , והמשחק המקורי מסובך דיו... ראה, למשל, כאן, קצת מידע על המקרה המאוד פרטי של לוח בגודל שלוש-על-משהו: |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
(הערה לעצמי: לקרוא את כל הדיון לפני שמגיבים. אלון: סליחה, ותודה.) | |
|
|
|
|
|
||
|
||||
|
(אין על מה להתנצל. מסתובבת שמועה שלא כל הקוראים הבינו את ההסבר של גדי; אם משהו לא ברור, להצביע). | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |