להיות אינסופי, להרגיש סופי

המתמטיקאי הגדול של תחילת המאה העשרים, דויד הילברט, אמר פעם ” הה, האינסוף – המרתק בין המושגים שהמתמטיקאים חוקרים”. מה שהילברט התכוון אליו הוא שהאינסוף תמיד מפתיע. למשל, קבוצה יכולה להיות שווה בגודלה לקבוצה שהיא חלקית לה ממש. קבוצה א’ יכולה להיות שווה בגודלה לקבוצה ב’ שמכילה אינסוף עותקים של א’ – אכן מפתיע! אבל יש מקרים שקבוצה היא אינסופית, ומתנהגת כמו קבוצה סופית. התופעה הזאת נקראת “קומפקטיות”, והיא לפעמים מועילה.

1. איך צדים אריה על הקטע \({[0,1]}\)

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

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

השיטה הזאת עומדת בבסיסו של משפט מתמטי שנקרא על שמם של בולצאנו ויירשטרס (\({Bolzano, ~~Weierstrass}\)). הם לא מצאו את המשפט בעבודה משותפת – בסוף המאה התשע עשרה עבודה משותפת עדיין לא הייתה באופנה. הם גילו אותו משפט בנפרד.

נניח שנתונה לכם קבוצה של מספרים, נקרא לה \({A}\). נקודה (מספר) \({a}\) נקראת “נקודת הצטברות” של \({A}\) אם יש לידה אינסוף נקודות מ- \({A}\). מה פירוש “לידה”? האם זה מונח מתמטי? לא בדיוק, אבל אפשר להפוך אותו למושג מדויק. הנה ההגדרה המדויקת:

הגדרה 1.1 \({a}\) נקראת “נקודת הצטברות” של \({A}\) אם כל קטע פתוח שמכיל את \({a}\) (קטע כזה נקרא “סביבה של \({a}\)”) מכיל אינסוף נקודות מ-\({A}\).

כמובן, כדי של-\({A}\) תהיה נקודת הצטברות היא צריכה להיות אינסופית בעצמה. האם לכל קבוצה אינסופית יש נקודת הצטברות? לאו דווקא. למשל, לקבוצת המספרים הטבעיים אין נקודת הצטברות. אין נקודה שבכל סביבה שלה יש אינסוף מספרים טבעיים. הסיבה היא כמובן ש-\({A}\) מתפרשת על פני תחום אינסופי – כך יכולות להיות אינסוף נקודות בלי שיצטברו בשום נקודה. משפט בולצאנו וירשטרס אומר שכאשר הקבוצה מוכלת בקטע סופי, אז יש לה נקודת הצטברות. לצורך העניין לא חשוב מהו הקטע הסופי. אם כן, בואו ניקח את הקטע \({[0,1]}\).

משפט 1.2 לקבוצה אינסופית שמוכלת בקטע \({[0,1]}\) יש נקודת הצטברות בקטע הזה.

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

2. עקרון שובך היונים האינסופי

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

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

מדוע? כי אם מכל סוג יש רק מספר סופי של איברים, ומספר הסוגים הוא סופי, יש יחד רק מספר סופי של איברים. סופי + סופי הוא סופי, עובדה שבה אתם משתמשים כל אימת שאתם מחברים מספרים.

3. הוכחת משפט בולצאנו ויירשטרס

ההוכחה משתמשת בעקרון שובך היונים האינסופי וב”שיטת האריה”. נחלק את הקטע \({[0,1]}\) לשני חלקים שווים על ידי נקודה באמצעו. על פי עקרון שובך היונים האינסופי באחד החצאים יש אינסוף נקודות מ-\({A}\). ניקח את החצי הזה, ונחלק אותו לשניים על ידי נקודה באמצעו. שוב, באחד החצאים יש אינסוף נקודות מ=\({A}\). נחלק אותו לשניים על ידי נקודה באמצעו, וכולי. הקטעים שבחרנו (אלה שבהם יש אינסוף נקודות מ-\({A}\)) קטנים והולכים, וכל אחד מהם מוכל בקודמו. קל להוכיח אז שהם “שואפים לנקודה אחת”, שפירושו שהקצוות הימניים שלהם והקצוות השמאליים שואפים לאותה נקודה, נקרא לה \({x}\). קל גם לראות שכל סביבה של \({x}\) מכילה את אחד הקטעים שבחרנו (אלה שמכילים אינסוף נקודות מ-\({A}\)) – זה נובע מכך שהאורך של הקטעים שואף ל-\({0}\). אם כן, הסביבה המדוברת מכילה קטע שמכיל אינסוף נקודות מ-\({A}\), אם כן היא עצמה מכילה אינסוף נקודות מ-\({A}\), שפירושו ש- \({x}\) היא נקדות ההצטברות המבוקשת.

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

4. משפט ארדש-דה ברוין

לעקרון הקומפקטיות יש שימושים בקומבינטוריקה אינסופית. אחד המפורסמים בהם הוא משפט של ארדש-דה ברוין (\({Erdos-de~Brujn}\)) – הפעם זוהי באמת עבודה משותפת. ב-\({1951}\), שנת הלידה של המשפט הזה, הייתה עבודה משותפת כבר יותר מקובלת, עקב ההתניידות הגדולה יותר של המדענים, והתקשורת המהירה יותר (אם מדברים על ניידות – לא היה נייד יותר מפול ארדש, שבילה את חייו בנסיעות בין שותפים לעבודה).

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

11

“צביעה” (או “צביעה חוקית”) של גרף היא חלוקה של הקדקודים לקבוצות בלתי תלויות. כל קבוצה בלתי תלויה היא “צבע”. אם כן, אפשר לנסח את מושג הצביעה גם כך: זוהי חלוקה של הקדקודים לצבעים, כך שכל שני קדקודים באותו צבע אינם מחוברים. למשל, במעגל מאורך 6 יש צביעה ב-2 צבעים, כמו בציור הבא:

12הנה משפט ארדש דה ברוין:

משפט 4.1 אם בגרף אינסופי אפשר לצבוע בצורה חוקית כל קבוצה סופית של קדקודים ב-\({k}\) צבעים, אז יש צביעה חוקית של כל הגרף ב-\({k}\) צבעים.

בואו נוכיח את המשפט הזה ל-\({k=3}\). ההוכחה דומה לכל \({k}\). ועוד הגבלה – נוכיח זאת לגרפים ניתנים להימנות, כלומר גרפים שבהם אפשר למנות את הקדקודים כך:

\(\displaystyle v_1, v_2, v_3, \ldots\)

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

בואו נקרא לצבעים שלנו כ, א ו-צ (כחול, אדום וצהוב). 

לפי ההנחה של המשפט יש צביעה חוקית של הקדקוד \({v_1}\) )למעשה לא נחוצה כאן שום הנחה – צבעו אותו באיזה צבע שאתם רוצים). לפי אותה הנחה יש גם צביעה חוקית, נקרא לה \({C_2}\), של הקדקודים \({v_1,v_2}\) (גם זה לא קשה, אם נתונים לכם שלושה צבעים. פשוט צבעו את שני הקדקודים האלה בצבעים שונים). 

לפי אותה הנחה יש גם צביעה, נקרא לה \({C_3}\), של הקדקודים \({v_1,v_2, v_3}\) (גם זה לא קשה, אם נתונים לכם שלושה צבעים. פשוט צבעו כל קדקוד בצבע שונה).

לפי אותה הנחה יש גם צביעה, נקרא לה \({C_4}\), של הקדקודים \({v_1,v_2, v_3, v_4}\) (הפעם אנחנו באמת זקוקים להנחה. לו כל ארבעה הקדקודים היו מחוברים זה לזה, לא היינו מצליחים לצבוע אותם בצורה חוקית בעזרת שלושה צבעים בלבד. ההנחה אומרת שזה לא קורה).

וכך הלאה – לכל \({n}\) יש לפי ההנחה צביעה חוקית \({C_n}\) ב-כ, א, צ של הקדקודים \({v_1,v_2, \ldots, v_n}\).

יש לנו אינסוף צביעות (כל צביעה רק של חלק מן הקדקודים), ורק שלושה צבעים. אם כן, על פי עקרון שובך היונים האינסופי, יש אינסוף ערכי \({n}\) שעבורם הקדקוד הראשון, \({v_1}\), צבוע באותו צבע, נאמר כ. כזכור – אנחנו רוצים לצבוע את כל הגרף. אז נצבע את \({v_1}\) ב-כ. 

מבין אינסוף הצביעות שבהן \({v_1}\) צבוע כ יש אינסוף שבהן \({v_2}\) צבוע באותו צבע, נאמר צ. נצבע את \({v_2}\) ב-צ. 

 

מבין אינסוף הצביעות שבהן \({v_1}\) צבוע כ ו-\({v_2}\) צבוע צ יש אינסוף שבהן \({v_3}\) צבוע באותו צבע, נאמר שוב כ. נצבע את \({v_3}\) ב-כ.

מבין אינסוף הצביעות שבהן \({v_1}\) צבוע כ ו-\({v_2}\) צבוע צ ו -\({v_3}\) צבוע כ יש אינסוף שבהן \({v_4}\) צבוע באותו צבע, נאמר א. נצבע את \({v_4}\) ב-א.

אני חושבת שההמשך ברור, ואין צורך לכתוב אותו בצורה פורמלית. הטענה היא עתה שהצביעה של כל הגרף שאנחנו מקבלים בדרך זו היא חוקית. הדבר נובע מכך ש”חוקיות” נקבעת על פי זוגות, כלומר 2 קדקודים, ו-2 הוא מספר סופי. אנחנו צריכים להוכיח שלכל \({i<j}\) אם \({v_i}\) מחובר ל-\({v_j}\) אז הם צבועים בצבעים שונים. ובניסוח על דרך השלילה, צריך להוכיח שאם \({v_i}\) ו-\({v_j}\) צבועים שניהם באותו צבע אז הם לא מחוברים.

נניח ששניהם צבועים באותו צבע, נאמר צ. פירוש הדבר הוא שמצאנו תחילה אינסוף צביעות חוקיות שבהן \({v_i}\) היה צבוע ב-צ, ומתוכן מצאנו אינסוף צביעות חוקיות שבהן \({v_j}\) צבוע צ. הצביעות המדוברות הן כולן חוקיות, ובכולן \({v_i}\) ו-\({v_j}\) צבועים שניהם ב-צ. החוקיות של הצביעות האלה אומרת ש-\({v_i}\) ו-\({v_j}\) אינם מחוברים – שהוא מה שרצינו להוכיח.

5. חלוקות לא ידידותיות

בגיליון \({13}\) של העיתון הגדרנו מהי חלוקה לא ידידותית של גרף (כאן). זוהי חלוקה של הקדקודים של הגרף לשתי קבוצות, \({A}\) ו-\({B}\), שמקיימת את התכונה הבאה: כל קדקוד מחובר ללא פחות קדקודים בקבוצה שאינה שלו מאשר לקדקודים בקבוצה שלו.

במאמר בגיליון \({13}\) הראינו שבכל גרף סופי יש חלוקה לא ידידותית, ואתגרנו את הקוראים להוכיח שהדבר נכון גם לגרפים אינסופיים שבהם כל קדקוד מחובר בצלעות רק למספר סופי של קדקודים (השערה מפורסמת למדי היא שהדבר נכון לכל גרף ניתן להימנות, כלומר כזה שאפשר למנות את קדקודיו “ראשון, שני, שלישי…”: ההשערה אינה נכונה באופן כללי).

הבטחתי לכם להביא הוכחה באחד הגליונות הבאים, ואני מקיים את ההבטחה, לפחות במקרה הניתן להימנות. הנה היא ההוכחה.

נמנה את הקדקודים: \({v_1, v_2, v_3, \ldots}\)

לכל מספר \({n}\) נסמן ב-\({G_n}\) את הגרף המושרה על \({v_1, v_2, v_3, \ldots, v_n}\). זהו גרף סופי, ולכן יש לו חלוקה לא ידידותית לקבוצות \({A_n,B_n}\).

נסתכל על הקדקוד \({v_1}\). לכל \({n}\) הוא יכול להשתייך ל-\({A_n}\) או ל-\({B_n}\). לפעמים כך, ולפעמים כך. אבל דבר אחד בטוח – באינסוף מקרים קורה אותו דבר. כלומר, או שבאינסוף מקרים הוא שייך ל-\({A_n}\), או שבאינסוף מקרים הוא שייך ל-\({B_n}\) )יכול להיות ששני הדברים קורים(. אם \({v_1}\) שייך באינסוף מקרים ל-\({A_n}\), נשים אותו בקבוצה \({A}\). אחרת נשים אותו בקבוצה \({B}\).

נניח ששמנו את \({v_1}\) בקבוצה \({A}\). אז עבור אינסוף \({n}\)-ים הוא שייך לקבוצה \({A_n}\). וכאן בא חלק חשוב בטיעון: נסתכל רק ב-\({n}\)-ים האלו, ועכשיו נתבונן בקדקוד השני, \({v_2}\). באינסוף מן ה-\({n}\)-ים שבחרנו הוא שייך לאותו סוג קבוצה – נאמר ל-\({B_n}\). נשים אז את \({v_2}\) ב-\({B}\), ונצמצם את תשומת ליבנו לאותם אינסוף \({n}\)-ים. מתוכם באינסוף מקרים \({v_3}\) שייך לאותו סוג – נאמר שמתוכם באינסוף מקרים הוא שייך ל-\({B_n}\). נשים אותו אז ב-\({B}\). נמשיך כך.

הטענה היא עתה שהחלוקה שקיבלנו, לקבוצות \({A}\) ו-\({B}\), היא לא ידידותית. כלומר, שכל קדקוד \({v}\) מחובר ללא פחות קדקודים מן הסוג שאינו שייך אליו מאשר לקדקודים מן הסוג שלו. אם \({v}\) ב-\({A}\) אז הוא מחובר ללא פחות קדקוקדים ב-\({B}\) מאשר ב-\({A}\), וגם להפך. כמובן, הקדקוד שלנו מופיע איפה שהוא ברשימה. נאמר ש-\({v=v_k}\). עתה נשתמש בתנאי שהגרף מקיים – שכל קדקוד מחובר רק למספר סופי של קדקודים אחרים. אם כן, קבוצת הקדקודם ש-\({v_k}\) מחובר אליהם נמצאת באיזשהו קטע התחלי סופי, נאמר \({\{v_1, v_2, \ldots,v_m\}}\).

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

בחרנו אינסוף \({n}\)-ים שבהם \({v_1}\) ב-\({A_n}\);

מתוכם בחרנו אינסוף \({n}\)-ים שבהם \({v_2}\) ב-\({B_n}\);

מתוכם בחרנו אינסוף \({n}\)-ים שבהם \({v_3}\) ב-\({B_n}\);

\({\ldots}\)

(מובן, הבחירות המסוימות האלה הן רק לצורך הדוגמה, אבל אין כאן הגבלת כלליות). אם כן יש אינסוף \({n}\)-ים גדולים מ-\({m}\) שעבורם כל הקדקודים \({v_1, \ldots, v_m}\) בוחרים אותו דבר – להיות ב-\({A_n}\) או ב-\({B_n}\),

וכן – הבחירה שלנו אם לשים אותם ב-\({A}\) או ב-\({B}\) נעשית בהתאם.

אבל כל אחת מן החלוקות \({A_n,B_n}\) טובה לגרף המושרה על הקדקודים עד \({v_n}\). במיוחד, אם ניקח \({n=m}\) (זה נכון לכל \({n}\)), היא טובה עבור \({v_k}\) שלנו. כלומר בגרף המושרה על הקדקודים \({v_1, \ldots, v_n}\) הקדקוד \({v_k}\) מחובר ללא פחות קדקודים בקבוצה שאינה שלו מאשר לקדקודים בקבוצה שלו.

אבל עבור \({n= m}\) השכנים של \({v_k}\) בגרף \({G_n}\) הם בדיוק השכנים שלו בגרף כולו. אם כן, התנאי נכון גם לגבי שכניו בגרף כולו – שהוא מה שרצינו להוכיח. הוא מכיר לא פחות קדקודים מן הסוג שאינו שלו מאשר מסוגו. זה נכון לכל קדקוד, ולכן החלוקה לא ידידותית.

6. סיכום

גרף שבו כל קדקוד מחובר רק למספר סופי של קדקודים הוא בעל “אופי סופי”. ומה שהראינו אז שהוא מתנהג, לפחות מבחינת ידידותיות של חלוקות, כמו גרף סופי. במשפט ארדש דה ברוין הסופיות הייתה אחרת – שם הסתכלנו בתכונה שנקבעת על ידי מספר סופי של קדקודים (במקרה זה – זוגות של קדקודים). וגם שם ראינו שאפשר לעבור מהסופי לאינסופי – מספיק לדרוש את התנאי למספר סופי של קדקודים. זוהי הקומפקטיות.