משפט נילסן-שרייר – הבדלי גרסאות

מ
בוט החלפות: \1תת-, \1על ידי
אין תקציר עריכה
מ (בוט החלפות: \1תת-, \1על ידי)
נביא הוכחה נוספת, דומה אך קומבינטורית יותר (ללא שיקולים כלל מטופולוגיה אלגברית)
 
תהי F חבורה חופשית הנוצרת ע"יעל ידי a<sub>1</sub>,...,a<sub>n</sub> ותהי H תת -חבורה שלה. נבנה גרף G בצורה הבאה: הקודקודים יהיו המחלקות השמאליות של H, ותהיה קשת מהקודקוד Hx עם הסימן a<sub>i</sub> לקודקוד Hxa<sub>i</sub> (קל לראות שזה מוגדר היטב) כיוון שהכפלה ב-a<sub>i</sub> היא פרמוטציה על המחלקות, לכל קודקוד נכנסת בדיוק קשת אחת עם כל יוצר ויוצאת בדיוק קשת אחת. (למרות שתהיה חשיבות לכיוון של הקשתות, כללית נתייחס לגרף כלא מכוון, כלומר הילוכים בגרף יוכלו לעבור בקשתות גם נגד כיוונן)
 
כעת נסמן {A={a<sub>1</sub>,...,a<sub>n</sub>,a<sub>1</sub><sup>-1</sup>,...,a<sub>n</sub><sup>-1</sup>. לכל קודקוד v ולכל איבר מ-A, "ללכת על האיבר" פירושו יהיה: אם האיבר הוא a<sub>i</sub>, לעבור לקודקוד u כך שיש קשת מ-v ל-u עם הסימן a<sub>i</sub>, ואם האיבר a<sub>i</sub><sup>-1</sup>, לעעבור לקודקוד u כך שיש קשת מ-u ל-v עם הסימן a<sub>i</sub>, ואם האיבר a<sub>i</sub><sup>-1</sup>. (מוגדר היטב כי ראינו שלכל יוצר וקודקוד יש קשת אחת נכנסת ואחת יוצאת מכל סימן) כמו כן למילה w נגדיר "ללכת על המילה" ללכת אחד אחד על איבריה. קל לראות באינדוקציה שאם נצא מהקודקוד Hx ונלך על המילה w נגיע לקודקוד Hxw. מכאן נובע מייד שהגרף קשיר כי כדי להגיע מהקודקוד Hx לקודקוד Hy אפשר ללכת על המילה x<sup>-1</sup>y.
נקרא למסלול בגרף "מסלול טוב" אם הוא מתחיל ונגמר ב-H, ואין בו מעבר פעמיים רצוף על אותה קשת בכיוונים הפוכים ("פניית פרסה"). נסמן את קבוצת המסלולים הטובים ב-P. ראשית נראה התאמה חח"ע ועל בין H ל-P: בכיוון אחד, לכל מילה w ב-H נתאים את המסלול שלה (בצורתה המצומצמת) שיוצא מ-H. הוא חוזר ל-H בסוף כי המילה ב-H, והוא גם לא כולל פניות פרסה כי מילים בצורה מצומצמת לא כוללות איבר ומייד לאחר מכן ההופכי שלו. בכיוון ההפוך, נתאים למסלול טוב את המילה שלו, והיא ב-H כי המסלול התחיל ונגמר ב-H.
 
כעת נראה התאמה חח"ע ועל בין P לחבורה החופשית הנוצרת ע"יעל ידי E: בכיוון אחד, יהי מסלול טוב, אז נתאים לו את המילה מעל E שמורכבת מכל הקשתות ב-E שעברנו עליהן במהלך המסלול הזה (אם עברנו נגד הכיוון זה יהיה האיבר ההופכי). בכיוון ההפוך, בהינתן מילה מ-E, נבנה את המסלול הטוב בצורה הבאה: אם המילה היא e<sub>1</sub>...e<sub>n</sub>, כצעד ראשון נלך מ-H להתחלה של הקשת e1 (או לסוף אם היא e<sub>1</sub><sup>-1</sup>) בלי לעבור בקשתות מ-E. קיימת דרך יחידה לעשות זאת, כי הגרף ללא E הוא עץ (בעץ יש מסלול יחיד בין כל שני קודקודים) לאחר מכן נלך מהסוף של e<sub>1</sub> להתחלה של e<sub>2</sub>, שוב בלי לעבור ב-E (אפשרי מאותה סיבה) נעשה זאת על כל איברי המילה, ולבסוף נחזור מסוף e<sub>n</sub> חזרה ל-H מבלי לעבור ב-E. יחד עם הקשתות e<sub>1</sub>,...,e<sub>n</sub> עצמן, קיבלנו מסלול טוב שהקשתות מ-E שהוא עובר בהן הן בדיוק e<sub>1</sub>,...,e<sub>n</sub>.
 
סה"כ הרכבת ההתאמות נותנת התאמה חח"ע ועל מ-H לחבורה החופשית הנוצרת מאיברי E. קל לראות שזה הומומורפיזם (הכפלת איברים מ-H עוברת לשרשור מסלולים טובים, שעובר לשרשור מילים מעל E) ולכן זה גם איזומורפיזם, ולכן H חופשית כרצוי.