משפט נקודת השבת של בראואר

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

במתמטיקה, משפט נקודת השבת של בראואר (Brouwer) הוא משפט בטופולוגיה. זהו אחד ממשפטים רבים הקובעים כי לפונקציה רציפה ${\displaystyle \ f}$עם תכונות מסוימות קיימת נקודה ${\displaystyle \ x_{0}}$ כך ש-${\displaystyle \ f(x_{0})=x_{0}}$ (כלומר, נקודת שבת). באופן מדויק, המשפט קובע כי אם ${\displaystyle \ f:B^{n}\rightarrow B^{n}}$ היא פונקציה רציפה אז ל-${\displaystyle \ f}$ יש נקודת שבת. הקבוצה ${\displaystyle \ B^{n}}$ היא כדור היחידה הסגור במרחב האוקלידי ה-${\displaystyle \ n}$ ממדי, כלומר קבוצת כל הנקודות שמרחקן מראשית הצירים אינו גדול מ־1.

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

דוגמאות

הצורה הוורודה נוצרה ממעגל התכלת על ידי כיווץ וקימוט. חייבת להיות נקודה שלא שינתה את מיקומה.

למשפט יש כמה דוגמאות "בעולם האמיתי". דוגמה אחת ליישום פשוט של המשפט ניתנת בספר "מתמטיקה" מסדרת לייף: לוקחים שני גליונות נייר בגדלים זהים, מקמטים אחד (אך לא קורעים אותו) ומניחים מעל השני כך שאינו חורג מגבולותיו; לפי המשפט יש לפחות נקודה אחת בגיליון המקומט שנמצאת בדיוק מעל הנקודה המקבילה לה בגיליון השני. זו מסקנה ממשפט בראואר עבור ${\displaystyle \ n=2}$. דוגמה עבור ${\displaystyle \ n=3}$ היא דגם מוקטן של שדה תעופה, בתוך שדה התעופה עצמו (דגמים כאלו ישנם בשדות תעופה רבים בעולם). הפונקציה שמעבירה נקודות במרחב האמיתי של שדה התעופה למיקום שלהם בדגם היא רציפה ולכן יש לה נקודת שבת המיוצגת בדגם דרך כלל על ידי X ("אתה נמצא כאן").

הכללה

גרסה כללית יותר של המשפט קובעת שלכל קבוצה קומפקטית וקמורה (ולא ריקה) ${\displaystyle \ S\subset \mathbb {R} ^{n}}$, ולכל פונקציה רציפה ${\displaystyle \ f:S\rightarrow S}$, יש נקודת שבת.

כל התנאים במשפט הם הכרחיים: כדי להראות את הכרחיות הקמירות, ניקח את הקבוצה ${\displaystyle \ S=\{(x,y)\in R^{2}|x^{2}+y^{2}=1\}}$ (קבוצת כל הנקודות על שפת מעגל דו־ממדי שמרכזו בראשית ורדיוסו שווה ל-1), ואז לפונקציה הרציפה ${\displaystyle \ f(x,y)=-(x,y)}$ אין נקודת שבת ב-${\displaystyle \ S}$. באופן דומה, כדי להראות את הכרחיות הקומפקטיות, ניקח את הקבוצה ${\displaystyle \ C=(0,1)}$ ואז לפונקציה הרציפה ${\displaystyle \ f}$ כך ש-${\displaystyle \ f(x)={\frac {1}{2}}+{\frac {x}{2}}}$ אין נקודת שבת ב-${\displaystyle \ C}$.

המקרה החד-ממדי

בממד אחד, התוצאה אינטואיטיבית וקלה להוכחה. הפונקציה הרציפה ${\displaystyle \ f}$ מוגדרת על הקטע הסגור ${\displaystyle \ [a,b]}$, ולוקחת ערכים מקטע זה אל עצמו. לומר שלפונקציה ${\displaystyle \ f}$ יש נקודת שבת בקטע זה, היא כמו לומר שיש לה נקודת חיתוך עם הגרף של הפונקציה ${\displaystyle \ g(x)=x}$ המוגדרת באותו קטע.

אם למשל נסתכל על הקטע ${\displaystyle \ [0,1]}$, נוכל להסתכל על הדוגמה של הגרף הנתון, כאשר f היא הפונקציה בשחור ו-g בירוק. באופן אינטואיטיבי, כל קו רציף מצדו השמאלי של הריבוע לצידו הימני חייב להחתך עם הגרף הירוק.

גם ההוכחה הפורמלית במקרה זה איננה מסובכת. תהא ${\displaystyle \ f}$ פונקציה רציפה מהקטע הסגור ${\displaystyle \ [a,b]}$ לעצמו. נגדיר ${\displaystyle \ g(x)=f(x)-x}$. מתקיים ${\displaystyle \ g(a)\geq 0}$ ו-${\displaystyle \ g(b)\leq 0}$. לכן, ע"פ משפט ערך הביניים, קיימת נקודה ${\displaystyle \ x_{0}}$ כך ש-${\displaystyle \ g(x_{0})=0}$ ולכן ${\displaystyle \ f(x_{0})=x_{0}}$.

המקרה הדו־ממדי

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

תהי ${\displaystyle \ f}$ פונקציה רציפה. נחלק את המשולש למשולשים שגודלם ${\displaystyle \ \varepsilon >0}$ ועבור כל קודקוד של כל משולש בחלוקה, נסמן בחץ את הכיוון בו נמצאת הנקודה שאליה הפונקציה ${\displaystyle \ f}$ תעביר את אותו קודקוד. נשים לב שכיוון ש-${\displaystyle \ f}$ רציפה על קבוצה קומפקטית, היא רציפה במידה שווה ולכן המרחק ${\displaystyle \ \delta >0}$ שאליו ימופה הקודקוד, תלוי רק ב- ${\displaystyle \ \varepsilon }$ ולא במיקום של אותו קודקוד במשולש.

כעת, נחלק את הכיוונים אליהם פונים חצים אלה לשלושה (ע"פ המעגל המופיע בשרטוט השני) - במעגל, נסמן את הזווית של חץ הפונה מעלה ב-90. אם חץ פונה בזווית של בין 0 ל-120 מעלות, נסמנו בצבע כחול, אם הוא פונה בזווית של בין 120 ל-240 מעלות נסמנו באדום, וחצים שפונים בזווית של 240 עד 360 מעלות, נסמן בירוק.

מרציפות הפונקציה נובע שמשולש ששלושת קודקודיו צבועים בצבעים שונים חייב להכיל נקודה שהפונקציה מעבירה לתוך אותו משולש, ובפרט, נקודה שהפונקציה מעתיקה למרחק קטן או שווה ל-${\displaystyle \ \varepsilon }$. אם נבחר סדרה השואפת ל-0 של ערכי ${\displaystyle \ \varepsilon }$, נקבל סדרה אינסופית של נקודות כאלו. מהקומפקטיות נובע שלסדרה זו יש נקודת הצטברות, ונקודה זו היא נקודת שבת של הפונקציה.

בעצם, עשינו פה רדוקציה של הבעיה ללמה של שפרנר. למה זו קובעת כי עבור טריאנגולציה של משולש למשולשים יותר קטנים, אם נתונה תלת צביעה של קודקודי הטריאנגולציה בשלושה צבעים כך ששלושת קודקודי המשולש הגדול צבועים בצבעים שונים וגם כל קודקוד פנימי צבוע באחד משני הצבעים בהם צבועים קודקודי המשולש הגדול שנמצאים בקצות הצלע עליה מונח הקודקוד הפנימי, אז עבור לפחות אחד מהמשולשים הקטנים – קודקודיו צבועים בשלושה צבעים שונים. לכן, בהינתן למה זו, הצלחנו למצוא נקודת שבת של ${\displaystyle \ f}$ במשולש.

המקרה הכללי

נתון סימפלקס סגור ${\displaystyle \rangle }$${\displaystyle \ p_{0},\ldots ,p_{n}}$${\displaystyle \langle }$ נסמנו ${\displaystyle \ \Delta }$ ונתונה פונקציה רציפה ${\displaystyle \ f:\Delta \rightarrow \Delta }$. יש להראות שקיימת נקודה ${\displaystyle p\in \Delta }$ כך ש-${\displaystyle \ f(p)=p}$.

נציג את ${\displaystyle \ f}$ בקואורדינטות הבריצנטריות ${\displaystyle \ f(\displaystyle \sum _{i=0}^{n}\lambda _{i}p_{i})=\displaystyle \sum _{i=0}^{n}\lambda _{i}'p_{i}}$; המקדמים כולם חיוביים, ומתקיים ${\displaystyle \displaystyle \sum _{i=0}^{n}\lambda _{i}=\displaystyle \sum _{i=0}^{n}\lambda _{i}'=1}$. כיוון ש-${\displaystyle \ f}$ רציפה וההתאמה בין נקודות הסימפלקס לבין הקואורדינטות הבריצנטריות גם היא רציפה, ההצגה הזו מגדירה את ${\displaystyle \ \lambda _{1}',\dots ,\lambda _{n}'}$ כפונקציות רציפות של המשתנים ${\displaystyle \lambda _{1},\dots ,\lambda _{n}}$, שהן חיוביות וסכומן 1 בתחום שבו המשתנים חיוביים וסכומם 1.

כעת נגדיר עבור (${\displaystyle \ i=0,\ldots ,n}$) את הקבוצות ${\displaystyle \ F_{i}=\{p\in \Delta :\lambda _{i}'\leq \lambda _{i}\}}$, שהן קבוצות סגורות. תהי ${\displaystyle p\in \langle p_{i_{0}},\ldots ,p_{i_{k}}\rangle }$ (${\displaystyle 0\leq i_{0}<\ldots <i_{k}\leq n}$) נקודה על אחת השפות, כלומר ${\displaystyle \lambda _{i_{0}}+\ldots +\lambda _{i_{k}}=1}$, ולכן ${\displaystyle \displaystyle \sum _{j=0}^{k}\lambda _{i_{j}}'\leq \sum _{i=0}^{k}\lambda _{i_{j}}}$. כיוון שמדובר בערכים אי שליליים, קיים לפחות מקום אחד ${\displaystyle \ 0\leq j\leq k}$ שעבורו ${\displaystyle \lambda _{i_{j}}'\leq \lambda _{i_{j}}}$, ואז ${\displaystyle p\in F_{i_{j}}}$. לכן ${\displaystyle \langle p_{i_{0}},\ldots ,p_{i_{k}}\rangle \subseteq F_{i_{0}}\cup \ldots \cup F_{i_{k}}}$.

מכאן יוצא שהקבוצות ${\displaystyle \ F_{0},\ldots ,F_{n}}$ מקיימות את תנאי הלמה של קנסטר-קורטובסקי-מזורקביץ', ולכן קיימת נקודה ${\displaystyle \ p'\in \bigcap _{i=0}^{n}F_{i}}$. פירוש הדבר ש-${\displaystyle \ p'}$ מקיימת לכל ${\displaystyle 0\leq i\leq n}$ ש-${\displaystyle \lambda _{i}'\leq \lambda _{i}}$. אולם ${\displaystyle \displaystyle \sum _{i=0}^{n}\lambda _{i}=\displaystyle \sum _{i=0}^{n}\lambda _{i}'=1}$ ולכן בהכרח לכל ${\displaystyle \ i}$ מתקיים ש-${\displaystyle \ \lambda _{i}'=\lambda _{i}}$ כלומר ${\displaystyle \ p'}$ היא נקודת שבת של ${\displaystyle \ f}$.

שימושים של המשפט

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

שימושי המשפט בטופולוגיה אלגברית

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

שימושי המשפט בתורת המשחקים

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

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

ראו גם

• מחלקת הסיבוכיות PPAD שמציאת נקודת השבת היא בעיה שלמה עבורה^[2].
• משפט נקודת השבת של קאוקטאני

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

מדיה וקבצים בנושא משפט נקודת השבת של בראואר בוויקישיתוף

• גדי אלכסנדרוביץ', משפטי נקודת השבת של בנך וברואר, באתר "לא מדויק", 23 במרץ 2019
• "על בראואר, נאש ומחלקת הסיבוכית של PPAD". (באנגלית)
• משפט נקודת השבת של בראואר, באתר אנציקלופדיה למתמטיקה (באנגלית)
• משפט נקודת השבת של בראואר, באתר MathWorld (באנגלית)
• משפט נקודת השבת של בראואר, באתר אנציקלופדיה בריטניקה (באנגלית)

הערות שוליים

1. David Gale, The Game of Hex and the Brouwer Fixed-Point Theorem, American Mathematical Monthly, vol 86, 1979, 818-827
2. (Christos H. Papadimitriou, On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994