Teoria kategorii dla informatyków/Ćwiczenia 9: Sprzężenia I: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
Linia 1: Linia 1:
 
  
 
==Zadanie 9.1== {{kotwica|mod9:zad1|}}
 
==Zadanie 9.1== {{kotwica|mod9:zad1|}}
Linia 11: Linia 10:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:'''<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:'''<div class="mw-collapsible-content" style="display:none">
  
Na dowolnym zbiorze <math>X</math> są dwa najprostsze sposoby zadania topologii <math>\tau</math>: albo bierzemy <math>\tau=\{\emptyset, X\}</math>, albo <math>\tau = \mathcal{P}(X)</math>. Nasz funktor <math>F\colon \mathbf{Set}\to \mathbf{Top}</math> na obiektach będzie zdefiniowany jako  <math>F(X):= (X,\tau)</math>, zaś na strzałkach jako <math>f\mapsto f</math>. Dla zbioru <math>X</math> naturalnym kandydatem na komponent jedności <math>\eta_X\colon X\to UF(X)</math> jest identyczność <math>1_X</math>. Ta prosta postać jedności, w świetle [[Teoria_kategorii_dla_informatyków/Wykład_9:_Sprzężenia_I#mod9:thm:adj3|Twierdzenia 9.5]], pozwala nam na stwierdzenie, że <math>F\dashv U</math> wtedy i tylko wtedy, gdy dla dowolnej przestrzeni topologicznej  <math>(A,\gamma)</math>, dowolna funkcja <math>F(X)\to (A,\gamma)</math> jest ciągła. To bardzo silne wymaganie! Mówiąc precyzyjniej: topologia na <math>F(X)</math> musi być bardzo bogata, tak aby dla ''dowolnej'' funkcji <math>f</math> jak wyżej, przeciwobraz ''dowolnego'' zbioru otwartego <math>U\in \gamma</math> musi być otwarty w <math>F(X)</math>. Z pewnością <math>\tau=\{\emptyset, X \}</math> nie spełnia tego wymagania. Z pewnością również <math>\tau =\mathcal{P}(X)</math> jest dobrym kandydatem - i jedynym możliwym (bo przecież moglibyśmy wziąć <math>(A,\gamma)=(X,\mathcal{P}(X))</math> oraz <math>f=1_X</math>). Każda bowiem funkcja dziedzinie <math>(X,\mathcal{P}(X))</math> jest ciągła. Podsumujmy: funktor zapominania <math>\mathbf{Top}\to\mathbf{Set}</math> ma lewe sprzężenie <math>F\colon \mathbf{Set}\to\mathbf{Top}</math> dany jako: <math>F(X):=(X,\mathcal{P}(X))</math>, <math>F(f):=f</math>.  
+
Na dowolnym zbiorze <math>X</math> są dwa najprostsze sposoby zadania topologii <math>\tau</math>: albo bierzemy <math>\tau=\{\emptyset, X\}</math>, albo <math>\tau = \mathcal{P}(X)</math>. Nasz funktor <math>F\colon \mathbf{Set}\to \mathbf{Top}</math> na obiektach będzie zdefiniowany jako  <math>F(X):= (X,\tau)</math>, zaś na strzałkach jako <math>f\mapsto f</math>. Dla zbioru <math>X</math> naturalnym kandydatem na komponent jedności <math>\eta_X\colon X\to UF(X)</math> jest identyczność <math>1_X</math>. Ta prosta postać jedności, w świetle [[Teoria_kategorii_dla_informatyków/Wykład_9:_Sprzężenia_I#mod9:thm:adj3|Twierdzenia 9.5]], pozwala nam na stwierdzenie, że <math>F\dashv U</math> wtedy i tylko wtedy, gdy dla dowolnej przestrzeni topologicznej  <math>(A,\gamma)</math>, dowolna funkcja <math>F(X)\to (A,\gamma)</math> jest ciągła. To bardzo silne wymaganie! Mówiąc precyzyjniej: topologia na <math>F(X)</math> musi być bardzo bogata, tak aby dla ''dowolnej'' funkcji <math>f</math>, jak wyżej, przeciwobraz ''dowolnego'' zbioru otwartego <math>U\in \gamma</math> musi być otwarty w <math>F(X)</math>. Z pewnością <math>\tau=\{\emptyset, X \}</math> nie spełnia tego wymagania. Z pewnością również <math>\tau =\mathcal{P}(X)</math> jest dobrym kandydatem - i jedynym możliwym (bo przecież moglibyśmy wziąć <math>(A,\gamma)=(X,\mathcal{P}(X))</math> oraz <math>f=1_X</math>). Każda bowiem funkcja dziedzinie <math>(X,\mathcal{P}(X))</math> jest ciągła. Podsumujmy: funktor zapominania <math>\mathbf{Top}\to\mathbf{Set}</math> ma lewe sprzężenie <math>F\colon \mathbf{Set}\to\mathbf{Top}</math> dany jako: <math>F(X):=(X,\mathcal{P}(X))</math>, <math>F(f):=f</math>.  
 
</div></div>
 
</div></div>
  
Linia 25: Linia 24:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:''' <div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:''' <div class="mw-collapsible-content" style="display:none">
  
Jeśli <math>\Delta\dashv F</math> dla pewnego <math>F</math>, to po pierwsze, <math>F</math> musi mieć typ <math>\mathbf{C}\times \mathbf{C}\to \mathbf{C}</math>. Po drugie, musimy mieć naturalny  izomorfizm
+
Jeśli <math>\Delta\dashv F</math> dla pewnego <math>F</math>, to po pierwsze, <math>F</math> musi mieć typ <math>\mathbf{C}\times \mathbf{C}\to \mathbf{C}</math>. Po drugie, musimy mieć naturalny  izomorfizm:
  
 
<center><math>\mathrm{Hom}_{\mathbf{C}}(A,F(X,Y))\cong \mathrm{Hom}_{\mathbf{C}}(\Delta(A),(X,Y))\cong \mathrm{Hom}_{\mathbf{C}}(A,X)\times  \mathrm{Hom}_{\mathbf{C}}(A,Y),</math></center>
 
<center><math>\mathrm{Hom}_{\mathbf{C}}(A,F(X,Y))\cong \mathrm{Hom}_{\mathbf{C}}(\Delta(A),(X,Y))\cong \mathrm{Hom}_{\mathbf{C}}(A,X)\times  \mathrm{Hom}_{\mathbf{C}}(A,Y),</math></center>
Linia 80: Linia 79:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:''' <div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:''' <div class="mw-collapsible-content" style="display:none">
  
Operację przeciwobrazu oznaczmy <math>f^{-1}\colon \mathcal{P}(B)\to\mathcal{P}(A)</math>, zaś obraz jako  <math>im(f)\colon \mathcal{P}(A)\to\mathcal{P}(B)</math>.  Wtedy łatwo widać, że:
+
Operację przeciwobrazu oznaczmy <math>f^{-1}\colon \mathcal{P}(B)\to\mathcal{P}(A)</math>, zaś obraz jako  <math>im(f)\colon \mathcal{P}(A)\to\mathcal{P}(B)</math>.  Wtedy widać, że:
  
 
<center><math>im(f)(S)\subseteq T\iff S\subseteq  f^{-1}(T),</math></center>
 
<center><math>im(f)(S)\subseteq T\iff S\subseteq  f^{-1}(T),</math></center>
Linia 104: Linia 103:
  
  
{{uwaga|||Badając jedności i kojedności tych sprzężeń dostajemy zupełny system dedukcyjny języka <math>L</math>, tzn. każde z praw logicznych dla <math>\vdash</math> wynika z tych dwóch sprzężeń powyżej, np. kojednością <math>\exists \vdash *</math> jest prawo
+
{{uwaga|||Badając jedności i kojedności tych sprzężeń, dostajemy zupełny system dedukcyjny języka <math>L</math>, tzn. każde z praw logicznych dla <math>\vdash</math> wynika z tych dwóch sprzężeń powyżej, np. kojednością <math>\exists \vdash *</math> jest prawo:
  
 
<center><math>\psi(l,y)\vdash \exists y.\psi(l,y).</math></center>
 
<center><math>\psi(l,y)\vdash \exists y.\psi(l,y).</math></center>
Linia 117: Linia 116:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:''' <div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:''' <div class="mw-collapsible-content" style="display:none">
  
Musimy udowodnić, że
+
Musimy udowodnić, że:
  
 
<center><math>\bigvee{}^\downarrow I\leq x\iff I\subseteq  \downarrow x</math></center>
 
<center><math>\bigvee{}^\downarrow I\leq x\iff I\subseteq  \downarrow x</math></center>
  
dla dowolnego elementu <math>x\in P</math> i ideału <math>I\in \mathcal{I}(P)</math>. Jeśli <math>\bigvee{}^\downarrow I\leq  x</math>, to oczywiście <math>i\leq x</math> dla każdego  <math>i\in I</math>, a co za tym idzie, <math>i\in \downarrow  x</math>. to dowodzi <math>I\subseteq \downarrow x</math>.  Odwrotnie, jeśli ta ostatnia inkluzja zachodzi, to <math>x</math>  jest ograniczeniem górnym <math>I</math>, więc jest powyżej jego  supremum, tj. <math>\bigvee{}^\downarrow I\leq x</math> (zwróćmy  uwagę, że to supremum istnieje, bo <math>P</math> jest dcpo).  
+
dla dowolnego elementu <math>x\in P</math> i ideału <math>I\in \mathcal{I}(P)</math>. Jeśli <math>\bigvee{}^\downarrow I\leq  x</math>, to oczywiście <math>i\leq x</math> dla każdego  <math>i\in I</math>, a co za tym idzie, <math>i\in \downarrow  x</math>. To dowodzi <math>I\subseteq \downarrow x</math>.  Odwrotnie, jeśli ta ostatnia inkluzja zachodzi, to <math>x</math>  jest ograniczeniem górnym <math>I</math>, więc jest powyżej jego  supremum, tj. <math>\bigvee{}^\downarrow I\leq x</math> (zwróćmy  uwagę, że to supremum istnieje, bo <math>P</math> jest dcpo).  
 
</div></div>
 
</div></div>
  
Linia 131: Linia 130:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none">
  
Tak, ale wtedy i tylko wtedy, kiedy <math>P</math> jest posetem ciągłym (definicji ciągłości szukaj [[Teoria_kategorii_dla_informatyków/Wykład_12:_Teoria_dziedzin_I#wyklad12|Wykładzie 12]]).
+
Tak, ale wtedy i tylko wtedy, kiedy <math>P</math> jest posetem ciągłym (definicji ciągłości szukaj [[Teoria_kategorii_dla_informatyków/Wykład_12:_Teoria_dziedzin_I#wyklad12|Wykładzie 12]].).
 
</div></div>
 
</div></div>
  

Aktualna wersja na dzień 11:48, 27 lis 2006

==Zadanie 9.1==

Znaleźć lewe sprzężenie dla funktora zapominania , o ile istnieje.

Wskazówka:
Rozwiązanie:

==Zadanie 9.2==

Udowodnij, że produkt jest prawym sprzężeniem przekątnej, a koprodukt - lewym sprzężeniem.

Wskazówka:
Rozwiązanie:


==Zadanie 9.3==

Znaleźć lewe i prawe sprzężenie do funktora diagonalnego typu , gdzie jest dowolną kategorią, zaś - dyskretną kategorią jednoobiektową.

Wskazówka:
Rozwiązanie:


Szereg kolejnych zadań dotyczy sprzężeń między częściowymi porządkami.

==Zadanie 9.4==

Wykaż, że topologiczna operacja wnętrza jest prawym sprzężeniem do inkluzji zbiorów otwartych w podzbiory .

Wskazówka:
Rozwiązanie:


==Zadanie 9.5==

Udowodnij, że operacje obrazu i przeciwobrazu funkcji są sprzężeniami na zbiorach potęgowych.

Rozwiązanie:


==Zadanie 9.6==

Niech będzie językiem pierwszego rzędu. Dla listy różnych zmiennych definiujemy jako zbiór tych formuł języka , których wszystkie zmienne wolne znajdują się na liście (oczywiście nie wszystkie zmienne muszą występować w formule ). Para jest preporządkiem względem syntaktycznej relacji dedukcji . Niech . Wówczas , jest funktorem, ponieważ w trywialnie implikuje w . Udowodnić, że kwantyfikator ogólny jest prawym sprzężeniem do , tj. . Jakie jest twierdzenie dualne?

Rozwiązanie:


==Zadanie 9.7==

Niech będzie dcpo, jak definiujemy to w Wykładzie 12. Wykazać, że domknięcie dolne jest prawym sprzężeniem do operacji supremum skierowanego .

Rozwiązanie:


==Zadanie 9.8==

Czy operacja , jak zdefiniowana w Zadaniu 9.7 ma lewe sprzężenie?

Wskazówka:
Rozwiązanie: