TKI Moduł 13: Różnice pomiędzy wersjami

Wersja z 17:32, 20 cze 2006

Udowodnijmy teraz podstawowe twierdzenie na temat diagramów w kategorii Dcpo.

Twierdzenie. W Dcpo istnieją granice dowolnych diagramów.

Dowód: Dowód przeprowadzimy dla szczególnego diagramu:

[DIAGRAM]

(Dowód ogólny jest analogiczny lecz wymaga bardziej technicznego zapisu, wiec go pominiemy.) Pokażemy, że granica powyższego diagramu jest dana jako

$D = {(x_{0}, x_{1}, . . .) ∣ (\forall n \in ω) (f_{n} (x_{n + 1}) = x_{n})} .$

Zauważmy, że zbiór $D$ jest posetem, w którym elementy są uporządkowane po współrzędnych (to znaczy, że porządek jest dziedziczony z produktu $Π_{n \in ω} D_{n}$ . Jeśli $G \subseteq D$ jest zbiorem skierowanym, to dla każdego $n \in ω$ zbiór $π_{n} [G] = {x_{n} ∣ x \in G}$ jest skierowanym podzbiorem $D_{n}$ . Niech $y_{n} = ⋁ {x_{n} ∣ x \in G}$ . Z ciągłości funkcji tworzących diagram mamy: $f_{n} (y_{n + 1}) = ⋁ f_{n} ({x_{n + 1} ∣ x \in G}) = ⋁ {x_{n} ∣ x \in G} = y_{n}$ . To znaczy, że $(y_{0}, y_{1}, . . .) \in D$ i, jak łatwo zauważyć, element ten jest supremum skierowanym zbioru $G$ . Pokazaliśmy więc, że $D \in$ Dcpo.

Udowodnimy teraz, że $D$ wraz z projekcjami ${π_{n} : D \to D_{n} ∣ n \in ω}$ jest granicą. Po pierwsze, dla $G \subseteq D$ mamy

$π_{n} (⋁ G) = y_{n} = ⋁ {x_{n} ∣ x \in G} = ⋁ π_{n} [G],$

a więc projekcje są ciągłe. Po drugie, jeśli ${g_{k} : E \to D_{k} ∣ k \in ω}$ jest dowolną inną granicą, to zdefiniujmy $h : E \to D$ jako $h (x) = (g_{0} (x), g_{1} (x), . . .)$ . Z definicji powyższej wynika, że dla każdego $k \in ω$ mamy $\pi_k \circ h = g_k</math>. Zauważmy, że to świadczy o jednoznaczności wyboru $h$ . A zatem $D$ jest granicą omawianego diagramu. Co więcej, z jednoznaczności granicy wnioskujemy, że $D ≅ E$ . QED

Uwaga! Powyższe twierdzenie nie zachodzi dla klas dziedzin ciągłych i algebraicznych w ogólności. Aby granica była również posetem odpowiedniej klasy, musimy nałożyć poewne restrykcje zarówno na kształ diagramów, jak i na własności funkcji tworzących diagram.

Twierdzenie o zgodności granicy prostej i odwrotnej

Przedstawimy teraz twierdzenie o zgodności granicy prostej i odwrotnej pewnych szczególnych diagramów w kategorii posetów zupełnych. Wynik ten jest znany w literaturze angielskojęzycznej jako limit-colimt coincidence i jest jednym z kamieni milowych w teorii dziedzin. Twierdzenie to wykorzystuje się przede wszystkim przy rozwiązywaniu tak zwanych rekursywnych równań dziedzinowych (ang. recursive domain equations). Przykładem takiego równania jest $D ≅ [D \to D]$ . Okazuje się, że jego nietrywialne rozwiązania istnieja! Tak więc istnieją posety, które są izomorficzne z przestrzenią swoich ciągłych endofunkcji! Jeden z takich częściowych porządków skonstruujemy poniżej, pod koniec wykładu.

Twierdzenie. Rozważmy diagram $F$ w kategorii Dcpo taki, że:

1. Wierzchołkami $F$ są posety $D_{0}, D_{1}, D_{2}, . . .$ ;

2. Dla $n \leq m$ istnieją funkcje $e_{m n} : D_{n} \to D_{m}$ i $p_{n m} : D_{m} \to D_{n}$ tworzące parę e-p; 3. Dla każdego $n \in ω$ mamy $e_{n n} = 1_{D_{n}}$ ;

4. Dla $n \leq m \leq k$ mamy $e_{k n} = e_{k m} \circ e_{m n}$ oraz $p_{n k} = p_{n m} \circ p_{m k}$ .

Zdefiniujmy:

$D = {(x_{0}, x_{1}, . . .) ∣ (\forall n \leq m) (x_{n} = p_{n m} (x_{m}))},$

$p_{m} : D \to D_{m}, (x_{0}, x_{1}, . . .) \mapsto x_{m}, m \in ω$

$e_{m} : D_{m} \to D, x \mapsto (\underset{k \geq n, m}{⋁} p_{n k} \circ e_{k m} (x) ∣ n \in ω) .$

Wtedy:

5. Para $(e_{m}, p_{m})$ jest parą e-p i zachodzi $\underset{n \in ω}{⋁} e_{n} \circ p_{n} = 1_{D}$ ,

6. ${p_{n} : D \to D_{n}}$ jest granicą diagramu $F$ . Jeśli ${g_{n} : C \to D_{n}}$ jest dowolną inną granicą, to izmorfizm $h : C \to D$ jest dany jako $h (x) = (g_{n} (x) ∣ n \in ω)$ lub $h = \underset{n}{⋁} e_{n} \circ g_{n}$ ;

7. ${e_{n} : D_{n} \to D}$ jest granicą odwrotną diagramu $F$ . Jeśli ${f_{n} : E \to D_{n}}$ jest dowolną inną granicą, to izmorfizm $f : D \to E$ jest dany jako $f (x_{n} ∣ n \in ω) = \underset{n}{⋁} f_{n} (x_{n})$ lub $f = \underset{n}{⋁} f_{n} \circ p_{n}$ .

Dowód: W Twierdzeniu ??? pokazaliśmy już, że granicą diagramu jest ${p_{n} : D \to D_{n}}$ i że izomorfizm $h : C \to D$ ma (pierwszą z) postulowanych postaci. Pokażmy teraz, że funkcje $e_{m}$ są dobrze zdefiniowane, tj. że $y = e_{m} (x)$ należy do $D$ dla dowolnego $m \in ω$ . Niech $m$ będzie dowolne i załóżmy, że $n \leq n^{'}$ . Mamy:

$p_{n n^{'}} (y_{n^{'}}) = p_{n n^{'}} (\underset{k \geq n^{'}, m}{⋁} p_{n^{'} k} \circ e_{k m} (x)) = \underset{k \geq n^{'}, m}{⋁} p_{n n^{'}} \circ p_{n^{'} k} \circ e_{k m} (x) = \underset{k \geq n^{'}, m}{⋁} p_{n k} \circ e_{k m} (x) = y_{n} .$

W dowodzie korzystaliśmy kolejno z: definicji $y_{n^{'}}$ , ciągłości $p_{n n^{'}}$ i definicji $y_{n}$ . A zatem $y = (y_{0}, y_{1}, . . .) \in D$ . Co więcej, funkcje $e_{m}$ są ciągłe, gdyż tylko funkcje ciągłe zostały użyte w ich definicji.

Przejdźmy do dowodu (5). Niech $m \in ω$ . Mamy:

$e_{m} \circ p_{m} (x_{n} ∣ n \in ω) = e_{m} (x_{m}) = (\underset{k \geq n, m}{⋁} p_{n k} \circ e_{k m} (x_{m}) ∣ n \in ω) = (\underset{k \geq n, m}{⋁} p_{n k} \circ e_{k m} \circ p_{m k} (x_{k}) ∣ n \in ω) \subseteq (\underset{k \geq n, m}{⋁} p_{n k} (x_{k}) ∣ n \in ω) = (\underset{k \geq n}{⋁} p_{n k} (x_{k}) ∣ n \in ω) = (x_{n} ∣ n \in ω) .$

Ponadto, $p_{m} \circ e_{m} (x) = p_{m} (\underset{k \geq n, m}{⋁} p_{n k} \circ e_{k m} (x) ∣ n \in ω) = \underset{k \geq m}{⋁} p_{m k} \circ e_{k m} (x) = x$ .

Bliższa analiza pokazuje, że $e_{m} \circ p_{m}$ pozostawi niezmienione te elementy ciągu $(x_{n} ∣ n \in ω)$ gdzie $n \leq m$ :

$p_{n} (e_{m} \circ p_{m} (x_{n} ∣ n \in ω)) = . . . = p_{n} (\underset{k \geq n, m}{⋁} p_{n k} \circ e_{k m} \circ p_{m k} (x_{k}) ∣ n \in ω) = p_{n} (\underset{k \geq n, m}{⋁} p_{n m} \circ p_{m k} \circ e_{k m} \circ p_{m k} (x_{k}) ∣ n \in ω) = p_{n} (\underset{k \geq n, m}{⋁} p_{n m} \circ p_{m k} (x_{k}) ∣ n \in ω) = p_{n} (\underset{k \geq n}{⋁} p_{n k} (x_{k}) ∣ n \in ω) = p_{n} (\underset{k \geq n}{⋁} x_{n} ∣ n \in ω) = p_{n} (x_{n} ∣ n \in ω) = x_{n} .$

To dowodzi, że $\underset{n}{⋁} e_{n} \circ p_{n} = 1_{D}$ , czyli (5).

Korzystając z powyższego mamy też natychmiast:

$h = 1_{D} \circ h = \underset{n}{⋁} E_{n} \circ p_{n} \circ h = ⋁ e_{m} \circ g_{n},$

co kończy dowód (6).

Do pokazania pozostała nam (7), czyli fakt, że ${e_{n} : D_{n} \to D}$ jest granicą odwrotną diagramu $F$ Jeśli ${f_{n} : E \to D_{n}}$ jest dowolną inną granicą, to sprawdźmy najpierw czy funkcja $f = \underset{n}{⋁} f_{n} \circ p_{n}$ jest dobrze zdefiniowana, tj. czy supremum jest nad zbiorem skierowanym. Ale tak jest, ponieważ dla $n \leq m$ :

$f_{n} \circ p_{n} = f_{m} \circ e_{m n} \circ p_{n m} \circ p_{m} ⊑ f_{m} \circ p_{m} .$

Co więcej,

$f \circ e_{m} = \underset{n \leq m}{⋁} f_{n} \circ p_{n} \circ e_{m} = \underset{n \leq m}{⋁} f_{n} \circ p_{n} \circ e_{n} \circ e_{n m} = \underset{n \leq m}{⋁} f_{n} \circ e_{n m} = \underset{n \leq m}{⋁} f_{m} = f_{m} .$

W końcu pokażemy, że funkcja $f$ o podanych własnościach jest tylko jedna. Jeśli dla $f^{'} : D \to E$ zachodzi $f^{'} \circ e_{m} = f_{m}$ , to $f^{'} \circ e_{m} \circ p_{m} = f_{m} \circ p_{m}$ , a zatem $\underset{m}{⋁} f^{'} \circ e_{m} \circ p_{m} = \underset{m}{⋁} f_{m} \circ p_{m},$ czyli z ciągłości $f^{'}$ : $f^{'} (\underset{m}{⋁} \circ e_{m} \circ p_{m}) = \underset{m}{⋁} f_{m} \circ p_{m} .$ Ale $\underset{m}{⋁} \circ e_{m} \circ p_{m} = 1_{D}$ oraz $\underset{m}{⋁} f_{m} \circ p_{m} = f$ co daje $f^{'} \circ 1_{D} = f$ czyli $f^{'} = f$ . QED.

Kategoria ${D c p o}_{⊥}^{E P}$

W tej kategorii obiektami są posety zupełne posiadające element najmniejszy, zaś morfizmami są pary e-p, o których była mowa na początku wykładu ???. Złożenie morfizmów

[DIAGRAM]

definiujemy w naturalny sposób jako morfizm

[DIAGRAM]

Czy $(e_{2} \circ e_{1}, p_{1} \circ p_{2})$ jest parą e-p? Tak, ponieważ: $e_{2} \circ e_{1} \circ p_{1} \circ p_{2} ⊑ e_{2} \circ 1_{E} \circ p_{2} = e_{2} \circ p_{2} ⊑ 1_{F}$ oraz $p_{1} \circ p_{2} \circ e_{2} \circ e_{1} = p_{1} \circ 1_{E} \circ e_{1} = p_{1} \circ e_{1} = 1_{D} .$ A zatem złożenie par e-p jest dobrze zdefiniowane, a co za tym idzie, i co łatwo już teraz pokazać, $D c p o_{⊥}^{E P}$ jest kategorią.

Definicja. Nazwijmy $ω$ -kategorią każdą kategorię, w której diagram postaci

[DIAGRAM]

posiada granicę odwrotną.

Zauważmy, że twierdzenie o zgodności granicy prostej i odwrotnej (Twierdzenie ???) mówi, że $D c p o_{⊥}^{E P}$ jest $ω$ -kategorią!

Definicja. Funktor $F$ między $ω$ -kategoriami nazywamy ciągłym, jeśli zachowuje granice odwrotne, t.j. jeśli $D_{\infty}$ jest granicą diagramu ???, to $F (D_{\infty})$ jest granicą diagramu

[DIAGRAM]

Lemat. Niech $𝐀$ będzie $ω$ -kategorią, $F : 𝐀 \to 𝐀$ funktorem ciągłym, $f : A \to F (A)$ morfizmem w $𝐀$ oraz niech diagram

[DIAGRAM]

posiada granicę odwrotną $D_{\infty}$ . Wówczas $D_{\infty} ≅ F (D_{\infty})$ .

@@ Linia 84: / Linia 84: @@
 <math>f_n \circ p_n = f_m \circ e_{mn}\circ p_{nm}\circ p_m\sqsubseteq f_m\circ p_m.</math>
+Co więcej,
+<math> f\circ e_m = \bigvee_{n\leq m} f_n\circ p_n\circ e_m = \bigvee_{n\leq m} f_n\circ p_n\circ e_n\circ e_{nm} = \bigvee_{n\leq m} f_n\circ e_{nm} = \bigvee_{n\leq m} f_m  = f_m. </math>
+W końcu pokażemy, że funkcja <math>f</math>  o podanych własnościach jest
+tylko jedna. Jeśli dla <math>f'\colon D\to E</math> zachodzi <math>f'\circ e_m = f_m</math>, to <math>f'\circ e_m \circ p_m = f_m\circ p_m</math>, a zatem <math>\bigvee_m f'\circ e_m \circ p_m = \bigvee_m f_m\circ p_m,</math> czyli z ciągłości <math>f'</math>: <math>f'(\bigvee_m \circ e_m \circ p_m) = \bigvee_m f_m\circ p_m.</math> Ale <math>\bigvee_m \circ e_m \circ p_m = 1_D</math>  oraz <math>\bigvee_m f_m\circ p_m = f</math>   co daje <math>f'\circ 1_D = f</math>   czyli <math>f'=f</math>. QED.
+== Kategoria <math>\mathrm{Dcpo}^{EP}_{\bot}</math> ==
+W tej kategorii obiektami są posety zupełne  posiadające element najmniejszy, zaś morfizmami są
+pary e-p, o których była mowa na początku wykładu ???. Złożenie morfizmów
+[DIAGRAM]
+definiujemy w naturalny sposób jako morfizm
+[DIAGRAM]
+Czy <math>(e_2\circ e_1, p_1\circ p_2)</math>  jest parą e-p? Tak, ponieważ: <math>e_2\circ e_1\circ p_1\circ p_2 \sqsubseteq e_2\circ 1_E\circ p_2 = e_2\circ p_2\sqsubseteq 1_F</math> oraz <math>p_1\circ p_2\circ e_2\circ e_1 = p_1\circ 1_E\circ e_1 = p_1\circ e_1 = 1_D.</math> A zatem złożenie par e-p jest dobrze zdefiniowane, a co za tym idzie, i co łatwo już teraz pokazać, <math>Dcpo^{EP}_{\bot}</math>  jest kategorią.
+'''Definicja'''. Nazwijmy '''<math>\omega</math>-kategorią''' każdą kategorię, w której diagram postaci
+[DIAGRAM]
+posiada granicę odwrotną.
+Zauważmy, że twierdzenie o zgodności granicy prostej i odwrotnej (Twierdzenie ???) mówi, że <math>Dcpo^{EP}_{\bot}</math>  jest <math>\omega</math>-kategorią!
+'''Definicja'''. Funktor <math>F</math>  między <math>\omega</math>-kategoriami nazywamy '''ciągłym''', jeśli zachowuje granice odwrotne, t.j. jeśli <math>D_{\infty}</math>  jest granicą diagramu ???, to <math>F(D_{\infty})</math> jest granicą diagramu
+[DIAGRAM]
+'''Lemat'''. Niech <math>\mathbf{A}</math>  będzie <math>\omega</math>-kategorią, <math>F\colon \mathbf{A}\to \mathbf{A}</math>  funktorem ciągłym, <math>f\colon A\to F(A)</math>  morfizmem w <math>\mathbf{A}</math>  oraz niech diagram
+[DIAGRAM]
+posiada granicę odwrotną <math>D_{\infty}</math>. Wówczas <math>D_{\infty}\cong F(D_{\infty})</math>.

TKI Moduł 13: Różnice pomiędzy wersjami

Wersja z 17:32, 20 cze 2006

Twierdzenie o zgodności granicy prostej i odwrotnej

Kategoria ${D c p o}_{⊥}^{E P}$

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

TKI Moduł 13: Różnice pomiędzy wersjami

Wersja z 17:32, 20 cze 2006

Twierdzenie o zgodności granicy prostej i odwrotnej

Kategoria Dcpo⊥EP

Menu nawigacyjne

Szukaj

Kategoria ${D c p o}_{⊥}^{E P}$