משחק טופולוגי

משחק טופולוגי הוא משחק סכום אפס דינמי לשני שחקנים בעלי ידיעה שלמה שבו כל שחקן בוחר אובייקט טופולוגי (נקודה, קבוצה פתוחה, קבוצה סגורה, כיסוי וכו') על בסיס הבחירות הקודמות שלו ושל היריב. בסוף המשחק, אשר כולל מספר בן-מניה של מהלכים, נקבע המנצח על בסיס מטרה מוגדרת מראש לכל אחד מהשחקנים.^[1] על-פי רוב מוגדר המשחק הטופולוגי להיות משחק בעל זמן בדיד ולרוב בזמן אינסופי (טרנספיניטי).

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

המשחק הטופולוגי הראשון נהגה בשנת 1935 על ידי המתמטיקאי הפולני סטניסלב מזור ונקרא משחק בנך-מזור^[2] על שמם של מזור וסטפן בנך (שהיה מנחה עבודת הדוקטורט של מזור ושותף למחקריו).

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

בניית המשחק

בהינתן מרחב טופולוגי $X$ ושני שחקנים אליס ובוב, משחק טופולוגי $G(X)$ הוא מערך כללים לפיו מתקיים התהליך הבא:

אליס בוחרת אובייקט טופולוגי $I_{1}$ .
בוב בוחר אובייקט טופולוגי $J_{1}$ תחת אילוצים הנובעים מבחירת $I_{1}$ (יש לשים לב כי $J_{1}$ יכול להיות אובייקט טופולוגי מסוג שונה מאשר $I_{1}$ ).
אליס בוחרת אובייקט טופולוגי חדש $I_{2}$ ואחריה בוב בוחר $J_{2}$ , שניהם נבחרים תחת אילוצים הנובעים מבחירות קודמות.
אליס ובוב ממשיכים לבחור $I_{n}$ ו- $J_{n}$ לסירוגין עד לאינסוף.

אליס מנצחת את המשחק אם ורק אם הסדרה $(I_{1},J_{1},I_{2},J_{2},I_{3},J_{3},\dots )$ (אשר קרויה מהלך משחק) מקיימת תנאי כלשהו אשר ידוע מראש לשני השחקנים. אחרת, בוב מנצח. $G(X)$ הוא אוסף האילוצים לפיהם קובעים אליס ובוב את $I_{n}$ ו- $J_{n}$ בתורם, וכן תנאי הניצחון לאליס (או לבוב).

ניתן לשחק את אותו המשחק הטופולוגי על מרחבים טופולוגיים שונים ועל כן המשחק ותוצאתו תלויים במרחב הטופולוגי $X$ . על-פי רוב המשחק הטופולוגי אינו סימטרי ולשני השחקנים מטרות שונות.

תכסיס והכרעה

במסגרת המשחק הטופולוגי, הן לאליס והן לבוב יש אפשרות להשתמש בתכסיס (אסטרטגיה) על מנת לנצח במשחק.

תכסיס של אליס מוגדר להיות פונקציה $\varphi$ המגדירה לכל סדרת מהלכים של בוב $(J_{1},J_{2},\dots ,J_{n})$ מהלך עבור אליס. מכיוון שאליס משחקת ראשונה, התכסיס של אליס מגדיר גם את פעולת הפתיחה של אליס. תכסיס $\varphi$ יקרא תכסיס מנצח עבור אליס למשחק $G(X)$ אם לכל סדרת מהלכים $J_{n}$ של בוב, מהלך המשחק $(\varphi (),J_{1},\varphi (J_{1}),J_{2},\varphi (J_{1},J_{2}),\dots )$ מנוצח על ידי אליס. אם לאליס קיים תכסיס מנצח, מסמנים ${\text{Alice}}\uparrow G(X)$ .

באופן דומה, תכסיס של בוב מוגדר להיות פונקציה $\psi$ המגדירה לכל סדרת מהלכים של אליס $(I_{1},I_{2},\dots ,I_{n})$ מהלך עבור בוב. מכיוון שבוב לא משחק ראשון, התכסיס של בוב לא נדרש להגדיר פעולת פתיחה. תכסיס $\psi$ יקרא תכסיס מנצח עבור בוב למשחק $G(X)$ אם לכל סדרת מהלכים $I_{n}$ של אליס, מהלך המשחק $(I_{1},\psi (I_{1}),I_{2},\psi (I_{1},I_{2}),\dots )$ מנוצח על ידי בוב. אם לבוב קיים תכסיס מנצח, מסמנים ${\text{Bob}}\uparrow G(X)$ .

אם לאחד מהשחקנים קיים תכסיס מנצח (כלומר, ${\text{Alice}}\uparrow G(X)$ או ${\text{Bob}}\uparrow G(X)$ ), המשחק $G(X)$ ייקרא משחק בר-הכרעה. אחרת, המשחק ייקרא משחק שאינו בר-הכרעה. אם מניחים את אקסיומת הבחירה, ניתן לבנות משחק טופולוגי שאינו בר-הכרעה. ניתן להוכיח שלא קיים משחק טופולוגי עבורו גם לאליס וגם לבוב יש אסטרטגיה מנצחת.

אחת מהמטרות העקריות של משחקים טופולוגיים היא להוכיח מה הם התנאים המינימליים עבור מרחב טופולוגי $X$ שעבורם המשחק $G(X)$ הוא בר-הכרעה ומי מבין שני השחקנים מנצח בו.

משחקים דואליים

שני משחקים טופולוגיים $G$ ו- $G'$ נקראים משחקים דואליים אם ורק אם לכל מרחב טופולוגי $X$ מתקיימים שני התנאים הבאים:^[3]

${\text{Alice}}\uparrow G(X)\Leftrightarrow {\text{Bob}}\uparrow G'(X)$
${\text{Bob}}\uparrow G(X)\Leftrightarrow {\text{Alice}}\uparrow G'(X)$

ניתן להסיק כי עבור זוג משחקים דואליים $G$ ו- $G'$ ומרחב טופולוגי $X$ , המשחק $G(X)$ הוא בר-הכרעה אם ורק אם $G'(X)$ הוא בר הכרעה. המשמעות היא שניתן להשתמש בכל אחד מהמשחקים הדואליים כדי לחקור את התכונות של מרחב טופולוגי נתון.

דוגמה פרטית

להלן משחק טופולוגי על המספרים הטבעיים:

מגדירים $a_{0}=0$
לכל $n\in \mathbb {N}$ אליס בוחרת מספר טבעי $b_{n}>a_{n-1}$ ובעקבותיה בוב בוחר מספר טבעי $a_{n}>b_{n}$

אליס מנצחת את המשחק אם אוסף הקטעים הסגורים $\bigcup _{n=1}^{\infty }{[a_{n}+1,b_{n}]}$ מכיל לכל היותר מספר סופי של חזקות של 2.

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

עם זאת, לבוב קיימת אסטרטגיה מנצחת שמבטיחה את ניצחונו. כל שעליו לעשות הוא לבחור בכל פעם מספר מהצורה $2^{k}-1$ , כלומר מספר אשר קטן מחזקה של 2 ב-1. מאחר שקיימות אינסוף חזקות של 2, מובטח כי בוב יכול לבצע בחירה שכזו. מאחר שאליס בוחרת מספר גדול יותר מזה של בוב, הקטע שאותו היא תבחר בהכרח יכיל את המספר $2^{k}$ . הדבר קורה אינסוף פעמים, לכן הקטעים של אליס יכילו אינסוף חזקות של 2.

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

משחקים טופולוגיים מוכרים

משחק בנך-מזור

בהינתן מרחב טופולוגי $X$ , קבוצה כלשהי $E\subset X$ (לאו דווקא פתוחה או סגורה) ומשפחה ${\mathcal {W}}$ של תת-קבוצות של $X$ (לאו דווקא פתוחות או סגורות) המקיימת את התנאים הבאים:

$\emptyset \notin {\mathcal {W}}$
לכל קבוצה פתוחה $\emptyset \neq U\subseteq X$ קיימת קבוצה $W\in {\mathcal {W}}$ כך ש- $W\subseteq U$
לכל $W\in {\mathcal {W}}$ קיימת קבוצה פתוחה $\emptyset \neq U\subseteq X$ כך ש- $U\subseteq W$

משחק בנך-מזור מסומן ב- $\operatorname {BM} (X,E,{\mathcal {W}})$ ומהלכו כדקלמן:^[4]

אליס בוחרת קבוצה $U_{1}\in {\mathcal {W}}$ ובעקבותיה בוב בוחר קבוצה $U_{2}\in {\mathcal {W}}$ כך ש- $U_{2}\subset U_{1}$ .
אליס בוחרת קבוצה $U_{3}\in {\mathcal {W}}$ כך ש- $U_{3}\subset U_{2}$ ובעקבותיה בוב בוחר קבוצה $U_{4}\in {\mathcal {W}}$ כך ש- $U_{4}\subset U_{3}$ .
ממשיכים עד לאינסוף.

אליס מנצחת את המשחק אם ורק אם $E\cap \bigcap _{n\in \mathbb {N} }{U_{n}}\neq \emptyset$ . במשחק זה $E$ נקראת קבוצת היעד.

משפט אוקסטובי קובע כי ${\text{Bob}}\uparrow \operatorname {BM} (X,E,{\mathcal {W}})$ אם ורק אם $E$ היא קבוצה מקטגוריה ראשונה (כלומר, קבוצה שהיא איחוד בן-מניה של קבוצות דלילות).

משחק שוקה

בהינתן מרחב טופולוגי $X$ , משחק שוקה מסומן ב- $\operatorname {CH} (X)$ ומהלכו כדקלמן:^[5]

אליס בוחרת קבוצה פתוחה לא ריקה $U_{1}$ ובעקבותיה בוב בוחר קבוצה פתוחה לא ריקה $U_{2}\subset U_{1}$ .
אליס בוחרת קבוצה קבוצה פתוחה לא ריקה $U_{3}\subset U_{2}$ ובעקבותיה בוב בוחר קבוצה פתוחה לא ריקה $U_{4}\subset U_{3}$ .
ממשיכים עד לאינסוף.

אליס מנצחת את המשחק אם ורק אם $\bigcap _{n\in \mathbb {N} }{U_{n}}\neq \emptyset$ .

משחק שוקה הוא למעשה מקרה פרטי של משחק בנך-מזור כאשר קבוצת היעד היא המרחב כולו $E=X$ ו- ${\mathcal {W}}$ היא משפחת כל הקבוצות הפתוחות השונות מהקבוצה הריקה. אם לבוב יש אסטרטגיה מנצחת במשחק שוקה, המרחב $X$ נקרא מרחב בייר. מקורות מסוימים מגדירים את משחק בנך-מזור כמשחק שוקה כפי שהוא מופיע כאן.^[1]

משחק נקודה-קבוצה פתוחה

בהינתן מרחב טופולוגי $X$ , משחק נקודה-קבוצה פתוחה מסומן ב- $\operatorname {PO} (X)$ ומהלכו כדקלמן:^[6]

אליס בוחרת נקודה $x_{1}\in X$ ובוב בוחר סביבה פתוחה של $x_{1}$ המסומנת ב- $U_{1}$ .
אליס בוחרת נקודה $x_{2}\in X$ ובוב בוחר סביבה פתוחה של $x_{2}$ המסומנת ב- $U_{2}$ .
ממשיכים עד לאינסוף.

אליס מנצחת את המשחק אם $\bigcup _{n\in N}{U_{n}}=X$ .

משחק רותברגר

בהינתן מרחב טופולוגי $X$ , משחק רותברגר מסומן ב- $\operatorname {RO} (X)$ ומהלכו כדלקמן:^[1]

אליס בוחרת כיסוי פתוח ${\mathcal {U}}_{1}$ של המרחב $X$ ובוב בוחר קבוצה פתוחה מתוך הכיסוי $U_{1}\in {\mathcal {U}}_{1}$ .
אליס בוחרת כיסוי פתוח ${\mathcal {U}}_{2}$ של המרחב $X$ ובוב בוחר קבוצה פתוחה מתוך הכיסוי $U_{2}\in {\mathcal {U}}_{2}$ .
ממשיכים עד לאינסוף.

בוב מנצח את המשחק אם $\{U_{n}\}_{n\in \mathbb {N} }$ הוא כיסוי פתוח של $X$ . ניתן להוכיח כי משחק רותברגר ומשחק נקודה-קבוצה פתוחה הם משחקים דואליים.^[3] מרחב $X$ שעבורו ${\text{Bob}}\uparrow \operatorname {RO} (X)$ (או לחלופין ${\text{Alice}}\uparrow \operatorname {PO} (X)$ , מטעמי דואליות) נקרא מרחב רותברגר.

משחק מנגר

בהינתן מרחב טופולוגי $X$ , משחק מנגר מסומן ב- $\operatorname {MG} (X)$ ומהלכו כדלקמן:^[7]

אליס בוחרת כיסוי פתוח ${\mathcal {U}}_{1}$ של המרחב $X$ ובוב בוחר תת-קבוצה סופית של הכיסוי ${\mathcal {F}}_{1}\subset {\mathcal {U}}_{1}$ .
אליס בוחרת כיסוי פתוח ${\mathcal {U}}_{2}$ של המרחב $X$ ובוב בוחר תת-קבוצה סופית של הכיסוי ${\mathcal {F}}_{2}\subset {\mathcal {U}}_{2}$ .
ממשיכים עד לאינסוף.

בוב מנצח את המשחק אם $\bigcup _{n\in \mathbb {N} }{{\mathcal {F}}_{n}}$ הוא כיסוי פתוח של $X$ . מרחב $X$ שעבורו ${\text{Bob}}\uparrow \operatorname {MG} (X)$ נקרא מרחב מנגר. ניתן להוכיח כי כל מרחב רותברגר הוא מרחב מנגר.

אקסיומת ההכרעה

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

אקסיומת ההכרעה היא אקסיומה לפיה משחק בנך-מזור $\operatorname {BM} (\mathbb {R} ,\mathbb {R} ,{\mathcal {W}})$ כאשר ${\mathcal {W}}$ היא קבוצת כל הקטעים הסגורים הוא משחק בר-הכרעה. נהוג לסמן אקסיומה זו באותיות ${\text{AD}}$ .^[8]

ניתן להוכיח כי אקסיומת ההכרעה ואקסיומת הבחירה סותרות זו את זו בהינתן אקסיומות צרמלו-פרנקל. כלומר, ניתן לבנות מודל אקסיומתי מהצורה ${\text{ZF}}+{\text{AD}}$ (אקסיומות צרמלו-פרנקל בתוספת אקסיומת ההכרעה) אשר סותר את מערכת האקסיומות הנהוגה ${\text{ZFC}}$ (אקסיומות צרמלו-פרנקל בתוספת אקסיומת הבחירה).

אם מניחים את מערכת האקסיומות ${\text{ZF}}+{\text{AD}}$ , מתקבלות מספר תוצאות חשובות, ביניהן שכל תת-קבוצה של המספרים הממשיים מדידה לפי לבג ושפרדוקס בנך-טרסקי לא מתקיים.^[9]

עם זאת, ללא אקסיומת הבחירה לא ניתן להוכיח את הלמה של צורן אשר ממנה נובעות תוצאות חשובות רבות, כמו למשל קיומו של בסיס לכל מרחב וקטורי. מסיבה זו, מרבית המתמטיקאים משתמשים ב- ${\text{ZFC}}$ ולא ב- ${\text{ZF}}+{\text{AD}}$ .

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

An impossible game at the heart of math, בביצוע SackVideo, סרטון באתר יוטיוב

הערות שוליים

^ ¹ ² ³ Leandro F. Aurichi, Rodrigo R. Dias, A minicourse on topological games, Topology and its Applications 258, 2019-05-15, עמ' 305–335 doi: 10.1016/j.topol.2019.02.057
^ RASTISLAV TELGÂRSKY, [http://www.telgarsky.com/1987-RMJM-Telgarsky-Topological-Games.pdf TOPOLOGICAL GAMES: ON THE 50TH ANNIVERSARY OF THE BANACH-MAZUR GAME], ‏1987 (באנגלית)
^ ¹ ² Leandro F. Aurichi, Rodrigo R. Dias, Topological games and Alster spaces, Canadian Mathematical Bulletin 57, 2014-12-01, עמ' 683–696 doi: 10.4153/CMB-2013-048-5
^ Banach-Mazur game - Encyclopedia of Mathematics, encyclopediaofmath.org
^ Gustave Choquet, Lectures on Analysis: Integration and topological vector spaces, W. A. Benjamin, 1969, ISBN 978-0-8053-6960-1. (באנגלית)
^ Janusz Pawlikowski, Undetermined sets of point-open games, Fundamenta Mathematicae 144, 1994, עמ' 279–285
^ Marion Scheepers, A Direct Proof of a Theorem of Telgársky, Proceedings of the American Mathematical Society 123, 1995, עמ' 3483–3485 doi: 10.2307/2161096
^ Samantha Stanton, The Axiom of determinicity, Virginia Commonwealth University, ‏2010 (באנגלית)
^ Peter Koellner, Large Cardinals and Determinacy, Spring 2014, Metaphysics Research Lab, Stanford University, 2014

[:0-1] ¹ ² ³ Leandro F. Aurichi, Rodrigo R. Dias, A minicourse on topological games, Topology and its Applications 258, 2019-05-15, עמ' 305–335 doi: 10.1016/j.topol.2019.02.057

[2] RASTISLAV TELGÂRSKY, [http://www.telgarsky.com/1987-RMJM-Telgarsky-Topological-Games.pdf TOPOLOGICAL GAMES: ON THE 50TH ANNIVERSARY OF THE BANACH-MAZUR GAME], ‏1987 (באנגלית)

[:1-3] ¹ ² Leandro F. Aurichi, Rodrigo R. Dias, Topological games and Alster spaces, Canadian Mathematical Bulletin 57, 2014-12-01, עמ' 683–696 doi: 10.4153/CMB-2013-048-5

[4] Banach-Mazur game - Encyclopedia of Mathematics, encyclopediaofmath.org

[5] Gustave Choquet, Lectures on Analysis: Integration and topological vector spaces, W. A. Benjamin, 1969, ISBN 978-0-8053-6960-1. (באנגלית)

[6] Janusz Pawlikowski, Undetermined sets of point-open games, Fundamenta Mathematicae 144, 1994, עמ' 279–285

[7] Marion Scheepers, A Direct Proof of a Theorem of Telgársky, Proceedings of the American Mathematical Society 123, 1995, עמ' 3483–3485 doi: 10.2307/2161096

[8] Samantha Stanton, The Axiom of determinicity, Virginia Commonwealth University, ‏2010 (באנגלית)

[9] Peter Koellner, Large Cardinals and Determinacy, Spring 2014, Metaphysics Research Lab, Stanford University, 2014

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]