Teoria kategorii dla informatyków/Ćwiczenia 14: Równania rekurencyjne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

==Zadanie==

Udowodnić, że w są granice dowolnych diagramów.

Wskazówka:
Rozwiązanie:

==Zadanie==

Udowodnić Lemat ?.

Rozwiązanie:


Poniższe zadania zawierają przykłady rozwiązań rekursywnych równań w kategorii . Wszystkie te rozwiązania konstruujemy w następujący sposób: mając dany lokalnie ciągły funktor definiujemy rekursywnie ciąg kolejnych dcpo poczynając od posetu jednoelementowego (czyli elementu końcowego w :



wraz z odpowiednimi, naturalnymi parami e-p. Taki ciąg tworzy diagram. Funktor , zgodnie z Lematem ?, rozszerza się do funktora ciągłego, a zatem Lemat ? mówi, że dla granicy diagramu mamy . W poniższych zadaniach zamiast podawania szczegółowych dowodów kładziemy nacisk na intuicyjne zrozumienie konstrukcji dla prostych funktorów.

==Zadanie==

Znaleźć punkt stały funktora , który dodaje element najmniejszy: .

Wskazówka:
Rozwiązanie:

==Zadanie==

Znajdź rozwiązanie równania

gdzie jest koproduktem w kategorii .

Wskazówka:


Rozwiązanie:

==Zadanie==

Znaleźć rozwiązanie równania

gdzie jest sumą rozłączna i , do której dodany jest nowy element najmniejszy.

Rozwiązanie:

==Zadanie==

Rozwiązać równanie


Rozwiązanie:

==Zadanie==

Rozwiązać równanie

gdzie: to znane z Zadania  ? płaskie liczby naturalne, zaś jest funktorem przypisującym dcpo </math>P</math>,</math>Q</math> ich produkt zredukowany (ang. smash product) . Produkt zredukowany jest ilorazem produktu przez relację równoważności , która identyfikuje ze sobą wszystkie elementy produktu, w których na choćby jednej współrzędnej znajduje się .

Rozwiązanie: