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

במתמטיקה, משפט נקודת השבת של בראואר הוא משפט בטופולוגיה, הקובע כי אם $f:B^n\to B^n$ היא פונקציה רציפה אזי יש לה נקודת שבת. הקבוצה $B^n$ היא כדור היחידה הסגור במרחב האוקלידי ה־$n$־ממדי, כלומר קבוצת כל הנקודות שמרחקן מראשית הצירים אינו גדול מ־1.

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

דוגמאות

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

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

הכללה

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

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

המקרה החד־ממדי

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

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

גם ההוכחה הפורמלית במקרה זה איננה מסובכת. תהי $f$ פונקציה רציפה מהקטע הסגור $[a,b]$ לעצמו. נגדיר $g(x)=f(x)-x$. מתקיים $g(a)\ge 0,g(b)\le 0$. על־פי משפט ערך הביניים קיימת נקודה $x_0$ עבורה $g(x_0)=0$ ולכן $f(x_0)=x_0$.

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

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

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

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

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

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

המקרה הכללי

נתון סימפלקס סגור $\mathrm{\Delta }=⟨p_0,\dots ,p_n⟩$ ונתונה פונקציה רציפה $f:\mathrm{\Delta }\to \mathrm{\Delta }$. יש להראות שקיימת נקודה $p\in \mathrm{\Delta }$ עבורה $f(p)=p$.

נציג את $f$ בקואורדינטות הבריצנטריות $f\left(\sum _{i=0}^n{\lambda }_i{p}_i\right)=\sum _{i=0}^n{{\lambda }_i}^{\prime }{p}_i$; המקדמים כולם חיוביים, ומתקיים $\sum _{i=0}^n{\lambda }_i=\sum _{i=0}^n{{\lambda }_i}^{\prime }=1$. כיוון ש־$f$ רציפה וההתאמה בין נקודות הסימפלקס לבין הקואורדינטות הבריצנטריות גם היא רציפה, ההצגה הזו מגדירה את ${{\lambda }_1}^{\prime },\dots ,{{\lambda }_n}^{\prime }$ כפונקציות רציפות של המשתנים ${\lambda }_1,\dots ,{\lambda }_n$, שהן חיוביות וסכומן 1 בתחום שבו המשתנים חיוביים וסכומם 1.

כעת נגדיר עבור $i=0,\dots ,n$ את הקבוצות $F_i=\{p\in \mathrm{\Delta }:{{\lambda }_i}^{\prime }\le {\lambda }_i\}$, שהן קבוצות סגורות. תהי $p\in ⟨p_{i_0},\dots ,p_{i_k}⟩:0\le i_0<\dots <i_k\le n$ נקודה על אחת השפות, כלומר ${\lambda }_{i_0}+\cdots +{\lambda }_{i_k}=1$, ולכן $\sum _{j=0}^k{\lambda }_{{i_j}^{\prime }}\le \sum _{i=0}^k{\lambda }_{i_j}$. כיוון שמדובר בערכים אי־שליליים, קיים לפחות מקום אחד $0\le j\le k$ עבורו ${\lambda }_{{i_j}^{\prime }}\le {\lambda }_{i_j}$ ואז $p\in F_{i_j}$. לכן $⟨p_{i_0},\dots ,p_{i_k}⟩\subseteq F_{i_0}\cup \dots \cup F_{i_k}$.

הקבוצות $F_0,\dots ,F_n$ מקיימות את תנאי הלמה של קנסטר-קורטובסקי-מזורקביץ', ולכן קיימת נקודה $p^{\prime }\in \bigcap _{i=0}^n{F}_i$. כלומר $p^{\prime }$ מקיימת ${{\lambda }_i}^{\prime }\le {\lambda }_i$ לכל $0\le i\le n$. אולם $\sum _{i=0}^n{\lambda }_i=\sum _{i=0}^n{{\lambda }_i}^{\prime }=1$ ולכן בהכרח לכל $i$ מתקיים ${{\lambda }_i}^{\prime }={\lambda }_i$, כלומר $p^{\prime }$ נקודת שבת של $f$.

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

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

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

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

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

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

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

ראו גם

• מחלקת הסיבוכיות PPAD שמציאת נקודת השבת היא בעיה שלמה עבורה.

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

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0