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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

הדגמות[עריכת קוד מקור | עריכה]

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

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

המקרה החד-ממדי[עריכת קוד מקור | עריכה]

Théorème-de-Brouwer-dim-1.svg

בממד אחד, התוצאה אינטואיטיבית וקלה להוכחה. הפונקציה הרציפה \ 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.

המקרה הדו ממדי[עריכת קוד מקור | עריכה]

Brouer-fixed-point-proof-1.jpg

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


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

Brouer-fixed-point-proof-2.jpg

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

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

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

המקרה הכללי[עריכת קוד מקור | עריכה]

נתון סימפלקס סגור \rangle\ p_0,\ldots,p_n\langle נסמנו \ \Delta ונתונה פונקציה רציפה \ f : \Delta \rightarrow \Delta. יש להראות שקיימת נקודה p \in \Delta כך ש-\ f(p)=p.

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

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

מכאן יוצא שהקבוצות \ F_0,\ldots,F_n מקיימות את תנאי הלמה של קנסטר-קורטובסקי-מזורקביץ', ולכן קיימת נקודה \ p' \in \bigcap_{i=0}^n F_i. פירוש הדבר ש- \ p' מקיימת לכל 0 \le i \le n ש-\lambda_i' \le \lambda_i. אולם \displaystyle\sum_{i=0}^n \lambda_i=\displaystyle\sum_{i=0}^n \lambda_i'=1 ולכן בהכרח לכל \ i מתקיים ש-\ \lambda_i' = \lambda_i כלומר \ p' היא נקודת שבת של \ f.

שימושים של המשפט[עריכת קוד מקור | עריכה]

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

שימושי המשפט בטופולוגיה אלגברית[עריכת קוד מקור | עריכה]

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

שימושי המשפט בתורת המשחקים[עריכת קוד מקור | עריכה]

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]


הערות שוליים[עריכת קוד מקור | עריכה]

  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