SW wykład 8 - Slajd7
Częściowe porządki zupełne Przykłady Funkcje ciągłe Intuicje Intuicje, c.d. Przestrzeń funkcji częściowych Twierdzenie o punkcie stałym Techniki dowodowe Semantyka while
Powyższy aparat pojęciowy wprowadziliśmy dla uzasadnienia najważniejszego tu dla nas, choć już teraz bardzo prostego, faktu: każda funkcja ciągła ze zbioru łańcuchowo zupełnego w tenże zbiór ma najmniejszy punkt stały zadany jako kres górny łańcucha kolejnych iteracji tej funkcji na elemencie najmniejszym zbioru.
Dowód jest prosty. Najpierw pokazujemy, przez prostą indukcję, że kolejne iteracje funkcji ciągłej (która jest monotoniczna) na elemencie najmniejszym tworzą łańcuch. Jego kres górny istnieje z definicji zbioru łańcuchowo zupełnego. Jest on punktem stałym tej funkcji, bo jako funkcja ciągła, zachowuje ona kres tego łańcucha, a element najmniejszy możemy dołożyć do każdego łańcucha nie zmieniając jego kresu. I w końcu, jest to najmniejszy punkt stały tej funkcji, bo przez prostą indukcję łatwo pokazać, że każda z iteracji tej funkcji na elemencie najmniejszym jest w relacji porządku z dowolnym punktem stałym tej funkcji. Zatem dowolny punkt stały tej funkcji jest ograniczeniem górnym łańcucha tych iteracji, a więc kres górny tego łańcucha jest w nim w relacji porządku.
Warto dodać, że w istocie jest to tylko przykład twierdzenia o istnieniu (najmniejszych) punktów stałych dla pewnych funkcji na zbiorach uporządkowanych spełniających pewne własności. Twierdzenia te wywodzą się z twierdzenia Knastera i Tarskiego, że zbiór punktów stałych funkcji z kraty zupełnej w nią samą tworzy (pod)kratę zupełna, o ile tylko funkcja ta zachowuje kresy niepustych podzbiorów kraty. Osłabiając lub wzmacniając założenia o istnieniu kresów w zbiorze częściowo uporządkowanym i o zachowaniu tych kresów przez rozważane funkcje można otrzymać wiele wersji tego faktu. Można na przykład pokazać, że jeśli w danym zbiorze częściowo uporządkowanym istnieją kresy wszystkich łańcuchów, to każda funkcja monotoniczna z tego zbioru w niego samego ma najmniejszy punkt stały (dowód jest podobny do dowodu faktu na slajdzie, ale wymaga pozaskończonych iteracji danej funkcji na elemencie najmniejszym).
Na potrzeby naszego wykładu, wersja podana na slajdzie wydaje się najważniejsza --- przynajmniej o ile nie chcemy wykraczać poza świat funkcji ciągłych.
