הלמה של קניג

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

נוסח הלמה

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

הוכחה

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

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

משפט הפריסות הפיניטריות (The fan theorem) של בראואר הוא, מנקודת מבט של המתמטיקה הקלאסית היפוך לוגי של גרסה חלשה של הלמה של קניג. תת-קבוצה  של  נקרא חסם (bar) אם לכל פונקציה מ־ אל הקבוצה  יש קטע התחלתי ב־. חסם הוא בר־הפרדה (detachable) אם כל רצף סופי הוא או בחסם או שאינו בחסם (הנחה זו הכרחית כי במתמטיקה אינטואיציוניסטית כלל השלישי מן הנמנע לא תמיד נכון). חסם הוא אחיד (uniform) אם קיים מספר טבעי  כך שלכל פונקציה מ־ אל הקבוצה  (רצף אינסופי, הנקרא גם אלמנט), יש קטע התחלתי בחסם באורך שלא עולה על . משפט הפריסות הפיניטריות של בראואר טוען שכל חסם בר־הפרדה הוא גם אחיד.
המשפט ניתן להוכחה בשיטות קלאסיות כאשר רואים בחסם כיסוי פתוח של המרחב הטופולוגי הקומפקטי . כל רצף בחסם הוא קבוצה פתוחה במרחב (הקבוצה היא כל מה שמתחיל ברצף הזה). מההנחה, זהו כיסוי של כל המרחב. מקומפקטיות, יש לכיסוי תת-כיסוי סופי. את  נוכל לבחור בתור אורך הרצף הגדול ביותר מבין הרצפים המתאימים לתת-הכיסוי הסופי שבחרנו. כאמור, ההוכחה שקולה להוכחת גרסה חלשה של הלמה של קניג: לכל מספר טבעי , לכל תת-עץ אינסופי של  יש מסלול אינסופי. נשים לב כי ההוכחה שנתנו כמו גם ההוכחה שניתנה למשפט הכללי, אינה קונסטרוקטיבית. בהוכחה מעלה, הסיבה היא שבכל שלב יש שימוש בהוכחה על דרך השלילה כדי למצוא את הקדקוד השכן הבא במסלול. החשיבות של משפט הפריסות הפיניטריות הוא בכך שהוא התקבל (בין אם כאקסיומה או על ידי הוכחה קונסטרוקטיבית מעקרון קודם) באסכולות הקונסטרוקטיביות ובאינטואיציוניזם בפרט כלגיטימי ובכך איפשר עבודות רבות באנליזה קונסטרוקטיבית.

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

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

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

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