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ą ilość dzieci, to musi istnieć nieskończona gałąź.

[edytuj] Dowód

Pod korzeniem znajduje się nieskończona ilość podwęzłów. Wybierzmy to z dzieci pod którym również znajduje się nieskończona ilość podwęzłów. Ponieważ ilość wszystkich podwęzłów korzenia - czyli ilość wszystkich węzłów-dzieci (która jest skończona) plus suma ilości 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ą ilość 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 ilość, któreś z nich musi stać się nieskończone. Ponieważ jednak każdy węzeł ma skończoną ilość 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.