SW wykład 9 - Slajd13

<<powrót do strony wykładu

Dziedziny podstawowe Suma i produkt Suma spłaszczona i produkt spłaszczony Przestrzeń funkcji ciągłych Izomorfizm dziedzin Konstruowanie funkcji ciągłych Złożenie funkcji i indeksowanie Inne konstrukcje Operator punktu stałego Równania stałopunktowe Równania dziedzinowe Rekurencyjne równania dziedzinowe Rekurencyjne równania dziedzinowe Problemy Dziedziny refleksywne Rozwiązanie naiwne dziedziny Scotta

Powtórzmy zatem poprzedni slajd, utożsamiając zagnieżdżone w prawo pary elementów z odpowiednimi skończonymi ciągami.

Kolejne iteracje operatora na zbiorach łańcuchowo zupełnych, wprowadzonego po prawej stronie naszego równania, rozpoczynamy od najmniejszego zbioru łańcuchowo zupełnego, zawierającego tylko "potok nieokreślony". W kolejnej iteracji, taki nieokreślony potok nadal mamy i jest on w relacji porządku z ciągami rozpoczynającymi się od dowolnego elementu --- a dalej zawierającymi znów potok nieokreślony, co należy intuicyjnie rozumieć jako "brak informacji o dalszym ciągu tego potoku". Zauważmy, że ta iteracja w naturalny sposób zawiera poprzednią. W kolejnej iteracji dochodzą potoki, gdzie znamy już pierwsze dwa elementy. Uwaga: ponieważ potok nieokreślony był w relacji porządku z potokami, gdzie mieliśmy określony pierwszy element, to teraz z kolei te potoki są w relacji porządku w potokami, gdzie mamy określone dwa początkowe elementy (o ile oczywiście pierwsze elementy są tożsame). Powstają więc tu nietrywialne łańcuchu trzyelementowe. I znów, ta iteracja w naturalny sposób zawiera poprzednią. W kolejnych iteracjach dokładamy potoki, gdzie znane są kolejne elementy; powstają też wówczas coraz dłuższe (ale wciąż skończone) łańcuchy. Otrzymujemy przy tym ciąg iteracji, z których każda zawarta jest w naturalny sposób w następnej. Przesumujmy teraz (teoriomnogościowo) wszystkie te kolejne zbiory łańcuchowo zupełne. Tu pojawia się problem: taka suma nie jest zbiorem łańcuchowo zupełnym, bo zawiera nieskończone łańcuchy (ciągów określających kolejne elementy potoku, wszystkie zakończone "brakiem informacji o dalszej części potoku") bez kresu górnego. Pozostaje nam jednak oczywisty teraz krok: dodajmy dla każdego takiego łańcucha nowy element, będący ich kresem górnym w definiowanym zbiorze łańcuchowo zupełnym. Nieformalnie, odpowiadają one nieskończonym potokom kolejnych elementów identyfikowanych przez kolejne (skończone) ciągi w łańcuchu. Zauważmy, że w tych dodanych nieskończonych potokach nie ma nic nowego. Pełna informacja o takim nieskończonym potoku zawarta już była w łańcuchu, którego jest on kresem: tam przecież już się pojawił każdy z jego elementów.

W ten sposób pokazaliśmy, jak rozważane rekurencyjne równanie dziedzinowe definiuje oczekiwany, "najmniejszy" zbiór łańcuchowo zupełny będący (z dokładnością do izomorfizmu) jego rozwiązaniem.