Lemat Königa

Z Wikipedii

Lemat Königa to lemat mówiący o tym, że jeśli drzewo jest nieskończone, a każdy węzeł ma skończoną liczbę dzieci, to musi istnieć nieskończona gałąź.

[edytuj] Dowód

Pod korzeniem znajduje się nieskończona liczba podwęzłów. Wybierzmy to z dzieci pod którym również znajduje się nieskończona liczba podwęzłów. Ponieważ liczba wszystkich podwęzłów korzenia - czyli liczba wszystkich węzłów-dzieci (która jest skończona) plus suma liczb wszystkich ich podwęzłów jest nieskończona, musi zawsze być choć jeden taki węzeł. Powtórzmy operację dla każdego kolejnego wybranego węzła. Procedura ta nigdy się nie skończy, bo przeczyło by to założeniu że pod danym węzłem jest nieskończona liczba podwęzłów. Znaleźliśmy w ten sposób nieskończoną gałąź.

[edytuj] Przykład użycia

Udowodnijmy że jeśli porządek na zbiorze jest dobrze ufundowany, to dobrze ufundowany jest również następujący porządek na multizbiorach skończonych złożonych z elementów zbioru : jeśli z multizbioru usuniemy dowolny element i na jego miejsce wstawimy dowolną skończoną liczbę elementów mniejszych od usuniętego, uzyskany multizbiór będzie mniejszy od początkowego.

Załóżmy, że istnieje nieskończony malejący ciąg skończonych multizbiorów zaczynający się od X. Dla każdego elementu X zbudujmy drzewo - i kiedy jakiś element jest usuwany wstawmy w podwęzły te elementy które go zastąpią. Ponieważ na każdym kroku dodajemy do któregoś z drzew przynajmniej jeden element, a drzew jest skończona liczba, któreś z nich musi stać się nieskończone. Ponieważ jednak każdy węzeł ma skończoną liczbę dzieci, w tym drzewie musi istnieć nieskończona gałąź - a więc nieskończony ciąg malejących elementów należących do , tak więc doszliśmy do sprzeczności.