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

Wersja z 16:50, 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} .$

@@ Linia 62: / Linia 62: @@
 Przejdźmy do dowodu (5). Niech <math>m\in \omega</math>. Mamy:
+<math>e_m\circ p_m (x_n\mid n\in \omega) = e_m(x_m) = (\bigvee_{k\geq n,m} p_{nk}\circ e_{km}(x_m)\mid n\in\omega)  = (\bigvee_{k\geq n,m} p_{nk}\circ e_{km} \circ p_{mk} (x_k)\mid n\in\omega) \subseteq (\bigvee_{k\geq n,m} p_{nk} (x_k)\mid n\in\omega) = (\bigvee_{k\geq n} p_{nk} (x_k)\mid n\in\omega) = (x_n\mid n\in\omega).</math>
+Ponadto, <math>p_m\circ e_m (x) = p_m (\bigvee_{k\geq n,m} p_{nk}\circ e_{km}(x)\mid n\in\omega ) =  \bigvee_{k\geq m} p_{mk}\circ e_{km}(x) = x</math>.
+Bliższa analiza pokazuje, że <math>e_m\circ p_m</math>  pozostawi niezmienione
+te elementy ciągu <math>(x_n\mid n\in\omega)</math> gdzie <math>n\leq m</math>:
+<math>p_n(e_m\circ p_m (x_n\mid n\in \omega)) = ... = p_n(\bigvee_{k\geq n,m} p_{nk}\circ e_{km} \circ p_{mk} (x_k)\mid n\in\omega)  = p_n(\bigvee_{k\geq n,m} p_{nm}\circ p_{mk} \circ e_{km} \circ p_{mk} (x_k)\mid n\in\omega)  = p_n(\bigvee_{k\geq n,m} p_{nm}\circ  p_{mk} (x_k)\mid n\in\omega)  = p_n(\bigvee_{k\geq n} p_{nk} (x_k)\mid n\in\omega) = p_n(\bigvee_{k\geq n} x_n\mid n\in\omega) = p_n(x_n\mid n\in\omega) = x_n.</math>
+To dowodzi, że <math>\bigvee_n e_n\circ p_n = 1_{D}</math>, czyli (5).
+Korzystając z powyższego mamy też natychmiast:
+<math>h = 1_D\circ h = \bigvee_n E_n\circ p_n\circ h = \bigvee e_m \circ g_n,</math>
+co kończy dowód (6).
+Do pokazania pozostała nam (7), czyli fakt, że <math>\{e_n\colon D_n\to D\}</math>  jest granicą odwrotną diagramu <math>F</math>   Jeśli <math>\{f_n\colon E\to D_n\}</math>  jest dowolną inną granicą, to sprawdźmy najpierw czy funkcja <math>f = \bigvee_n f_n\circ p_n</math>  jest dobrze zdefiniowana, tj. czy supremum jest nad zbiorem skierowanym. Ale tak jest, ponieważ dla <math>n\leq m</math>:
+<math>f_n \circ p_n = f_m \circ e_{mn}\circ p_{nm}\circ p_m\sqsubseteq f_m\circ p_m.</math>

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

Wersja z 16:50, 20 cze 2006

Twierdzenie o zgodności granicy prostej i odwrotnej

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia