הלמה של קניג

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

הלמה של קניג היא כלי חשוב בתורת הגרפים. המתמטיקאי W. T. Tutte כתב עליה:

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

— W. T. Tutte, Commentery, in Denes Konig Theory of Finite and Infinite Graphs, Boston: Birkhauser, 1990, pp. 25

נוסח הלמה

עץ אינסופי, שכל הדרגות בו סופיות, מכיל ענף (קרי, מסלול היוצא מהשורש) אינסופי.

באופן כללי יותר, יהא $G=\left(V,E\right)$ גרף קשיר עם אינסוף קדקודים, כך שדרגת כל קדקוד היא סופית (קרי, מכל קדקוד יוצאות מספר סופי של צלעות אל קדקודים אחרים). אזי, $G$ מכילה מסלול פשוט (קרי, ללא מעגלים) באורך אינסופי.

הוכחה

נוכיח את הגרסה הכללית. יהא $G=\left(V,E\right)$ הגרף עם אינסוף קדקודים שיסומנו $v_{i}$ , כך שדרגת כל אחד מהם סופית.

נתחיל עם קדקוד $v_{1}$ . מהקשירות של הגרף נובע שקיים מסלול פשוט ממנו לכל אחד מהקדקודים האחרים ב־ $V$ , כל מסלול כזה עובר דרך אחד השכנים של $v_{1}$ ויש מספר סופי של שכנים כאלה, מסופיות הדרגה שלו. קיים אם כן קדקוד שכן אחד שניתן להגיע ממנו אל אינסוף קדקודים שלא דרך $v_{1}$ , אחרת, נקבל שמכל אחד מהשכנים שלו ניתן להגיע למספר סופי של קדקודים ונקבל שיש מספר סופי של קדקודים בגרף, בסתירה להנחה שישנם אינסוף קדקודים.

נסמן את הקדקוד השכן שבחרנו $v_{2}$ . ישנם כעת, מהבחירה, אינסוף קדקודים שיש מסלול פשוט ממנו אליהם שלא דרך $v_{1}$ . כל מסלול כזה עובר דרך אחד השכנים שלו שהוא לא $v_{1}$ וכמו קודם קיים שכן אחד שממנו ניתן להגיע לאינסוף מקדקודי הגרף. נבחר אותו ונסמנו $v_{3}$ .

נמשיך כעת באותו אופן באינדוקציה מתמטית. נקבל שבכל שלב מהנחת האינדוקציה יש שכן שממנו ניתן להגיע לאינסוף מקדקודי הגרף במסלול פשוט שלא עובר דרך הקודמים. מהאינדוקציה נקבל שלכל מספר טבעי $n$ ניתן לבחור קדקוד $v_{n}$ כך שקיים מסלול פשוט בגרף באורך $n$ .

היסטוריה

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

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

ב־1914 הציג קניג את מאמרו הראשון הקשור לנושא, Sur un probléme de la théorie générales des ensembles et la théorie des graphes, ב־"קונגרס לפילוסופיה מתמטית" בפריז. המאמר עצמו פורסם תשע שנים אחר־כך. במאמר ניגש קניג להוכחתו של ברנשטיין מכיוון של תורת הגרפים במקום תורת הקבוצות וכך נתן הכללה שתוצאתו של ברנשטיין היא מקרה פרטי שלה. ב־1916 פרסם בגיליון ה־77 של הMathematische Annalen את מאמרו השני בנושא — Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. במאמר זה זנח קניג לחלוטין את השפה של תורת הקבוצות ונתן הוכחה לתוצאה מקבילה של משפט ברנשטיין בגרפים.

ב־1926 פרסם קניג יחד עם סטפן ולקו בגיליון ה־95 של כתב העת Mathematische Annalen את המאמר Über mehrdeutige Abbildungen von Mengen הכולל את ההכללה של משפט ברנשטיין שלשמה הם נדרשו ללמה עצמה, ובמיוחד את המקרה הפרטי שלה בנוגע לעצים. מעט לאחר מכן פרסם קניג לבד את המאמר Sur les correspondances multivoques des ensebles ובו חזר לשפת תורת הקבוצות כדי "לא להזדקק לשום אינטואיציה גאומטרית", אך גם, כפי שהתוודה מאוחר יותר, כדי להתאים עצמו לסגנון של כתב העת Fundamenta Mathematicae. הלמה מופיעה במאמר זה בצורה הבאה: "תהא $E_{1},E_{2},E_{3},\dots$ סדרה בת מנייה של קבוצות לא ריקות, ויהיה $R$ יחס כך שלכל איבר $x_{n+1}$ של כל קבוצה $E_{n+1}$ קיים לפחות איבר אחד $x_{n}$ בתוך $E_{n}$ כך ש־ $x_{n}Rx_{n+1}$ לכל $n\in \mathbb {N}$ . אזי אפשרי לבחור מכל $E_{n}$ איבר $a_{n}$ כך שמתקיים $a_{n}Ra_{n+1}$ עבור סדרה אינסופית $\left(a_{1},a_{2},a_{3}\dots \right)$ ".

ב־1927 פרסם קניג את המאמר Über eine Schlussweise aus dem Endlichen ins Unendliche ולראשונה הלמה עצמה הייתה הנושא המרכזי בו. במאמר מופיעים שלושה נוסחים של הלמה — הראשון בנוסח תורת הקבוצות השאוב מהמאמר מ־1926, ושניים בלשון תורת הגרפים:

"אם קבוצה בת מנייה של נקודות של גרף אינסופי היא איחוד של מספר בן מנייה של קבוצות סופיות ולא ריקות $E_{1},E_{2},\dots$ כך שכל נקודה של $E_{n+1}$ ניתנת לחיבור לנקודה ב־ $E_{n}$ על ידי צלע, אזי קיים בגרף מסלול אינסופי $a_{1},a_{2},\dots$ שמכיל נקודה $a_{n}$ מכל קבוצה $E_{n}$ (ואין הכרח שהקבוצות $E_{n}$ תהיינה זרות)".
"אם לכל נקודה בגרף אינסופי קשיר יש מספר סופי של צלעות היוצאות ממני, אזי הגרף מכיל מסלול אינסופי".

כדי להדגיש את החשיבות של הלמה עצמה מחוץ להקשר של משפט ברנשטיין קניג ציין 4 יישומים של הלמה:

הכללה של משפט בורל הקובע כי "עבור $E$ תת-קבוצה של הקטע $\left(0,1\right)$ ו־ $I$ משפחה של קטעים עם התכונה שכל נקודה ב־ $E$ מוכלת באיזשהו קטע בה. אזי קיים מספר טבעי $n$ כך שאם הקטע $\left(0,1\right)$ מחולק ל־ $2^{n}$ תת-קטעים, אזי תת-קטעים המכילים נקודה מ־ $E$ מוכלים בקטע הנמצא ב־ $I$ ".
הוכחת מקרה פרטי של משפט ארבעת הצבעים.
הוכחה לטענה שאם נניח שהמין האנושי לעולם לא ייכחד, אזי קיים בינינו אדם שיש לו אינסוף צאצאים.
הוכחה שבשחמט קיים מספר טבעי $N$ התלוי במספר $q$ , כך שאם הלבן משחק החל מנקודה $q$ אזי הלבן יכול לנצח בפחות מ־ $N$ מהלכים.

הקשר לאינטואיציוניזם

משפט הפריסות הפיניטריות (The fan theorem) של בראואר הוא, מנקודת מבט של המתמטיקה הקלאסית היפוך לוגי של גרסה חלשה של הלמה של קניג. תת-קבוצה $S$ של $\{0,1\}^{<\omega }\,$ נקרא חסם (bar) אם לכל פונקציה מ־ $\omega$ אל הקבוצה $\{0,1\}$ יש קטע התחלתי ב־ $S$ . חסם הוא בר־הפרדה (detachable) אם כל רצף סופי הוא או בחסם או שאינו בחסם (הנחה זו הכרחית כי במתמטיקה אינטואיציוניסטית כלל השלישי מן הנמנע לא תמיד נכון). חסם הוא אחיד (uniform) אם קיים מספר טבעי $N$ כך שלכל פונקציה מ־ $\omega$ אל הקבוצה $\{0,1\}$ (רצף אינסופי, הנקרא גם אלמנט), יש קטע התחלתי בחסם באורך שלא עולה על $N$ . משפט הפריסות הפיניטריות של בראואר טוען שכל חסם בר־הפרדה הוא גם אחיד.^[2]

המשפט ניתן להוכחה בשיטות קלאסיות כאשר רואים בחסם כיסוי פתוח של המרחב הטופולוגי הקומפקטי $\{0,1\}^{<\omega }\,$ . כל רצף בחסם הוא קבוצה פתוחה במרחב (הקבוצה היא כל מה שמתחיל ברצף הזה). מההנחה, זהו כיסוי של כל המרחב. מקומפקטיות, יש לכיסוי תת-כיסוי סופי. את $N$ נוכל לבחור בתור אורך הרצף הגדול ביותר מבין הרצפים המתאימים לתת-הכיסוי הסופי שבחרנו. כאמור, ההוכחה שקולה להוכחת גרסה חלשה של הלמה של קניג: לכל מספר טבעי $k$ , לכל תת-עץ אינסופי של $\{0,\ldots ,k\}^{<\omega }\,$ יש מסלול אינסופי. נשים לב כי ההוכחה שנתנו כמו גם ההוכחה שניתנה למשפט הכללי, אינה קונסטרוקטיבית. בהוכחה מעלה, הסיבה היא שבכל שלב יש שימוש בהוכחה על דרך השלילה כדי למצוא את הקדקוד השכן הבא במסלול. החשיבות של משפט הפריסות הפיניטריות הוא בכך שהוא התקבל (בין אם כאקסיומה או על ידי הוכחה קונסטרוקטיבית מעקרון קודם) באסכולות הקונסטרוקטיביות ובאינטואיציוניזם בפרט כלגיטימי ובכך איפשר עבודות רבות באנליזה קונסטרוקטיבית.^[3]

הקשר לאקסיומת הבחירה

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

הלמה של קניג היא אפוא הגבלה של עקרון הבחירה התלויה ליחס שלם $R$ כך שלכל $x$ קיימים מספר סופי של $y$ כך ש־ $xRy$ . אמנם באופן כללי אקסיומת הבחירה חזקה יותר מעקרון הבחירה התלויה וגוררת אותו, ההגבלה הזו של העיקרון שקולה להגבלה של אקסיומת הבחירה. כאשר הבחירה בכל קדקוד נעשית על תת-קבוצה סופית של קבוצה שאינה בהכרח בת מנייה, הלמה של קניג אומרת ש־"כל עץ אינסופי בעל דרגה סופית מכיל מסלול אינסופי" שקול לכך שכל קבוצה בת מנייה של קבוצות סופיות מכילה פונקציית בחירה^[4]. ניסוח זה של הלמה של קניג ושל אקסיומת הבחירה אינו יכיח באקסיומת צרמלו פרנקל.

בתורת ההוכחות

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

המערכת $WKL_{0}$ (קיצור של Weak König's lemma, כאשר ה־ $0$ מסמל שבמערכת זו אינדוקציה מתמטית היא מסדר שני), שהיא אחת מחמש המערכות המרכזיות, מוגדרת בין היתר על ידי הלמה של קניג. היא מורכבת מהאקסיומות של מערכת $RCA_{0}$ יחד עם הגרסה החלשה של הלמה הטוענת שכל עץ בינארי מלא (קרי, עץ כל הסדרות של $0$ ו־ $1$ ) מכיל מסלול אינסופי. טענה זו, הקרויה "למת קניג החלשה" פשוטה לתיאור בשפת האריתמטיקה מסדר שני.

לשתי המערכות, $WKL_{0}$ ו־ $RCA_{0}$ יש אותה שפה מסדר ראשון, ופירושו ששתי המערכות מוכיחות אותן טענות הכתובות בשפה מסדר ראשון. לעומת זאת, $WKL_{0}$ חזקה יותר מרעותה, שכן משפטים מתמטיים מרכזיים רבים יכיחים בה ולא ב־ $RCA_{0}$ , אלו משפטים המנוסחים בשפה מסדר שני שלא ניתנים לניסוח בסדר ראשון.

ישנן מספר טענות השקולות ללמת קניג החלשה, ולכן ל־ $WKL_{0}$ במערכת $RCA_{0}$ . בין היתר:

משפט היינה-בורל לקטעי יחידה סגורים — לכל כיסוי על ידי סדרת קטעים פתוחים יש תת-כיסוי סופי.^[5].
משפט היינה-בורל למרחבים מטריים ספרביליים חסומים לחלוטין.
משפט ויירשטראס הראשון לקטעים סגורים — כל פונקציה רציפה ממשית על קטע סגור היא חסומה.
משפט נקודת השבת של בראואר, לפונקציות רציפות על מכפלה סופית של קטעי יחידה.
משפט השלמות של גדל (לשפות בנות־מנייה).
משפט עקום ז'ורדן(אנ').

קיימות גם מערכות חזקות יותר מ־ $RCA_{0}$ , אחת החשובות בהן, ובכלל, היא $ACA_{0}$ שבה הלמה של קניג בגרסתה המלאה נכונה. למעשה, ב־ $RCA_{0}$ , הלמה של קניג גוררת את $ACA_{0}$ .^[6]

הכללות לעוצמה גבוהה

אומרים שלעוצמה k יש תכונת העץ אם לכל עץ מגובה k, שבו כל רמה היא מעוצמה קטנה מ-k, יש מסלול באורך k. הלמה של קניג אומרת שלאָלֶף אֶפֶס יש תכונת העץ. אהרונשיין הוכיח של- $\ \aleph _{1}$ אין תכונת העץ (ראו עץ אהרונשיין). תכונת העץ עבור $\ \aleph _{2}$ אינה נובעת מ-ZFC, אבל היא עקבית עם ZFC, ועקבי אפילו שכל המונים $\ \aleph _{n}$ , עבור n מ-2 ואילך, הם בעלי תכונת העץ.

לקריאה נוספת

Kleene, S. C. Mathematical Logic. New York: Dover, 2002
Miriam Franchella, On the Origins of Denes Konig's Infinity Lemma, Archive History Exact Science, 51, 1997

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

הלמה של קניג, באתר MathWorld (באנגלית)

הערות שוליים

^ Miriam Franchella, On the Origins of Denes Konig's Infinity Lemma, Archive History Exact Science 51 (1997), pp. 5
^ לניסוח האינטואיציוניסטי המקורי של המשפט, כמו גם מעיין־הוכחה שלו, ראה Arend Heyting, Intuitionism: An Introduction, (1956), Chapter 3.
^ על החשיבות של המשפט במתמטיקה קונסטרוקטיבית בכלל, ועל ההתפתחות ההיסטורית של מקומו האקסיומטי ניתן לראות כאן: http://plato.stanford.edu/entries/mathematics-constructive/
^ Truss, J. Some cases of König's lemma, in Marek, V. Wiktor; Srebrny, Marian; Zarach, Andrzej, Set theory and hierarchy theory: a memorial tribute to Andrzej Mostowski, Lecture Notes in Mathematics 537, Springer, (1976), pp. 273–284; השווה Azriel Lévy, Basic Set Theory, Springer, (1979) Reprint Dover 2002, ISBN 0-486-42079-5., תרגיל IX.2.18.
^ Aboldazl Karimi, An Introduction To Reverse Mathematics, April 26th, 2014
^ Henry Towsner, Part 4: Second Order Arithmatic And Reverse Mathematic, Theorem 4.19

[1] Miriam Franchella, On the Origins of Denes Konig's Infinity Lemma, Archive History Exact Science 51 (1997), pp. 5

[2] לניסוח האינטואיציוניסטי המקורי של המשפט, כמו גם מעיין־הוכחה שלו, ראה Arend Heyting, Intuitionism: An Introduction, (1956), Chapter 3.

[3] על החשיבות של המשפט במתמטיקה קונסטרוקטיבית בכלל, ועל ההתפתחות ההיסטורית של מקומו האקסיומטי ניתן לראות כאן: http://plato.stanford.edu/entries/mathematics-constructive/

[4] Truss, J. Some cases of König's lemma, in Marek, V. Wiktor; Srebrny, Marian; Zarach, Andrzej, Set theory and hierarchy theory: a memorial tribute to Andrzej Mostowski, Lecture Notes in Mathematics 537, Springer, (1976), pp. 273–284; השווה Azriel Lévy, Basic Set Theory, Springer, (1979) Reprint Dover 2002, ISBN 0-486-42079-5., תרגיל IX.2.18.

[5] Aboldazl Karimi, An Introduction To Reverse Mathematics, April 26th, 2014

[6] Henry Towsner, Part 4: Second Order Arithmatic And Reverse Mathematic, Theorem 4.19

[1]

[2]

[3]

[4]

[5]

[6]