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

{{סימון מתמטי}}
במתמטיקה, '''משפט נקודת השבת של בראואר''' (Brouwer) הוא משפט ב[[טופולוגיה]]. זהו אחד ממשפטים רבים הקובעים כי לפונקציה רציפה <math>\ f</math>עם תכונות מסוימות קיימת נקודה <math>\ x_0</math> כך ש-<math>\ f(x_0) = x_0</math> (כלומר, [[נקודת שבת]]). באופן מדויק, המשפט קובע כי אם <math>\ f:B^{n}\rightarrow B^{n}</math> היא [[פונקציה רציפה]] אז ל-<math>\ f</math> יש [[נקודת שבת]]. ה[[קבוצה (מתמטיקה)|קבוצה]] <math>\ B^{n}</math> היא [[כדור יחידה|כדור היחידה]] ה[[קבוצה סגורה|סגור]] ב[[מרחב אוקלידי|מרחב האוקלידי]] ה-<math>\ n</math> ממדי, כלומר קבוצת כל הנקודות שמרחקן מראשית הצירים אינו גדול מ־1. 

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

==דוגמאות==
[[קובץ:Mainpic134.jpg|שמאל|150px|ממוזער|הצורה הוורודה נוצרה ממעגל התכלת על ידי כיווץ וקימוט. חייבת להיות נקודה שלא שינתה את מיקומה.]]
למשפט יש כמה דוגמאות "בעולם האמיתי". דוגמה אחת ליישום פשוט של המשפט ניתנת בספר [[פורטל:מתמטיקה/מדף הספרים/5|"מתמטיקה"]] מסדרת לייף: לוקחים שני גליונות נייר בגדלים זהים, מקמטים אחד (אך לא קורעים אותו) ומניחים מעל השני כך שאינו חורג מגבולותיו; לפי המשפט יש לפחות נקודה אחת בגיליון המקומט שנמצאת בדיוק מעל הנקודה המקבילה לה בגיליון השני. זו מסקנה ממשפט בראואר עבור <math>\ n=2</math>. דוגמה עבור <math>\ n=3</math> היא דגם מוקטן של שדה תעופה, בתוך שדה התעופה עצמו (דגמים כאלו ישנם בשדות תעופה רבים בעולם). הפונקציה שמעבירה נקודות במרחב האמיתי של שדה התעופה למיקום שלהם בדגם היא רציפה ולכן יש לה נקודת שבת המיוצגת בדגם דרך כלל על ידי X ("אתה נמצא כאן").
{{-}}

== הכללה ==

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

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

==המקרה החד-ממדי==
[[קובץ:Théorème-de-Brouwer-dim-1.svg|150px|שמאל]]
בממד אחד, התוצאה אינטואיטיבית וקלה להוכחה. הפונקציה הרציפה <math>\ f</math> מוגדרת על הקטע הסגור <math>\ [a,b]</math>, ולוקחת ערכים מקטע זה אל עצמו. לומר שלפונקציה <math>\ f</math> יש נקודת שבת בקטע זה, היא כמו לומר שיש לה נקודת חיתוך עם הגרף של הפונקציה <math>\ g(x)=x</math> המוגדרת באותו קטע.

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

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

==המקרה הדו־ממדי==
[[קובץ:Brouer-fixed-point-proof-1.jpg|200px|שמאל]]
את המקרה הדו־ממדי נוכיח על הקבוצה שהיא המשולש המלא. ניתן לראות בקלות כי קבוצה זו מקיימת את תנאי המשפט. מספיק להוכיח שמשפט תקף לקבוצה זו כיוון שבינה לבין כל קבוצה אחרת שמקיימת את תנאי המשפט, ניתן למצוא פונקציה רציפה שגם ההופכית שלה היא רציפה. לכן, מהרכבת פונקציות רציפות, נקבל שלכל פונקציה רציפה תהיה נקודת שבת גם על הקבוצה החדשה.


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

[[קובץ:Brouer-fixed-point-proof-2.jpg|200px|שמאל]]
כעת, נחלק את הכיוונים אליהם פונים חצים אלה לשלושה (ע"פ המעגל המופיע בשרטוט השני) - במעגל, נסמן את הזווית של חץ הפונה מעלה ב-90. אם חץ פונה בזווית של בין 0 ל-120 מעלות, נסמנו בצבע כחול, אם הוא פונה בזווית של בין 120 ל-240 מעלות נסמנו באדום, וחצים שפונים בזווית של 240 עד 360 מעלות, נסמן בירוק.

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

בעצם, עשינו פה רדוקציה של הבעיה ל[[הלמה של שפרנר|למה של שפרנר]]. למה זו קובעת כי עבור [[טריאנגולציה (גאומטריה)|טריאנגולציה]] של משולש למשולשים יותר קטנים, אם נתונה תלת צביעה של קודקודי הטריאנגולציה בשלושה צבעים כך ששלושת קודקודי המשולש הגדול צבועים בצבעים שונים וגם כל קודקוד פנימי צבוע באחד משני הצבעים בהם צבועים קודקודי המשולש הגדול שנמצאים בקצות הצלע עליה מונח הקודקוד הפנימי, אז עבור לפחות אחד מהמשולשים הקטנים – קודקודיו צבועים בשלושה צבעים שונים. לכן, בהינתן למה זו, הצלחנו למצוא נקודת שבת של <math>\ f</math> במשולש.

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

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

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

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

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

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

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

למשפט אף שימושים ב[[תורת המשחקים הקומבינטורית]] ויש לו קשר הדוק למשחק [[הקס (משחק)|הקס]]: [[דייוויד גייל]] הראה כי משפט נקודת השבת של בראואר שקול לקיומה של אסטרטגיה מנצחת בהקס (כלומר שהמשחק אינו יכול להסתיים ב[[תיקו]]){{הערה|1=David Gale, The Game of Hex and the Brouwer Fixed-Point Theorem, American Mathematical Monthly, vol 86, 1979, 818-827}}.

==ראו גם==
*[[PPAD|מחלקת הסיבוכיות PPAD]] שמציאת נקודת השבת היא בעיה שלמה עבורה{{הערה|1=(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}}.
* [[משפט נקודת השבת של קאוקטאני]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{לא מדויק|2019/03/23/banach_and_brouwer_fixed_point_theorem|משפטי נקודת השבת של בנך וברואר}}
* {{cite web | title = על בראואר, נאש ומחלקת הסיבוכית של PPAD | url = http://www.csc.liv.ac.uk/~pwg/PPADintro/PPADintro.html}} {{אנגלית}}
* {{אנציקלופדיה למתמטיקה|Brouwer_theorem}}
* {{MathWorld}}
* {{בריטניקה}}

==הערות שוליים==
{{הערות שוליים|יישור=ימין}}
{{בקרת זהויות}}

[[קטגוריה:משפטי נקודת שבת|בראואר]]