Teoria kategorii dla informatyków/Ćwiczenia 1: Teoria kategorii jako abstrakcyjna teoria funkcji: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
Linia 1: Linia 1:
 
==Zadanie 1.1== {{kotwica|mod1:zad1|}}
 
==Zadanie 1.1== {{kotwica|mod1:zad1|}}
  
Udowodnij, że dla dwóch funkcji <math>f\colon A\to B</math> oraz <math>g\colon B\to A</math> jeśli <math>f\circ g = 1_B</math> oraz <math>g\circ f =  1_A</math>, to funkcja <math>f</math> jest bijekcją.
+
Udowodnij, że dla dwóch funkcji <math>f\colon A\to B</math> oraz <math>g\colon B\to A</math>, jeśli <math>f\circ g = 1_B</math> oraz <math>g\circ f =  1_A</math>, to funkcja <math>f</math> jest bijekcją.
  
 
<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">
Pokażemy najpierw, że <math>f</math> jest funkcją  różnowartościową. Przypuśćmy, że <math>f(x)= f(y)</math> dla pewnych elementów <math>x,y\in A</math>. Wówczas <math>x = 1_A(x) = (g\circ f)(x) =  g(f(x)) = g(f(y)) = (g\circ f)(y) = 1_A(y) = y</math>. Ponadto, dla  dowolnego <math>z\in B</math> element <math>g(z)</math> jest jedynym takim elementem, że <math>f(g(z)) = z</math>, co w szczególności oznacza, że <math>f</math> jest surjekcją. Wnioskujemy więc, że <math>f</math> jest różnowartościową surjekcją, czyli  bijekcją.
+
Pokażemy najpierw, że <math>f</math> jest funkcją  różnowartościową. Przypuśćmy, że <math>f(x)= f(y)</math> dla pewnych elementów <math>x,y\in A</math>. Wówczas <math>x = 1_A(x) = (g\circ f)(x) =  g(f(x)) = g(f(y)) = (g\circ f)(y) = 1_A(y) = y</math>. Ponadto, dla  dowolnego <math>z\in B</math>, element <math>g(z)</math> jest jedynym takim elementem, że <math>f(g(z)) = z</math>, co w szczególności oznacza, że <math>f</math> jest surjekcją. Wnioskujemy więc, że <math>f</math> jest różnowartościową surjekcją, czyli  bijekcją.
 
</div>
 
</div>
 
</div>
 
</div>
Linia 13: Linia 13:
  
 
<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">
Fakt, że liczby naturalne posiadają wspomnianą w [[Teoria_kategorii_dla_informatyków/Wykład_1:_Teoria_kategorii_jako_abstrakcyjna_teoria_funkcji#mod1:fact:naturalne|Fakcie 1.2]] jest dokładnie twierdzeniem o rekursji. Pozostaje nam zatem udowodnienie implikacji przeciwnej.
+
Fakt, że liczby naturalne posiadają własność wspomnianą w [[Teoria_kategorii_dla_informatyków/Wykład_1:_Teoria_kategorii_jako_abstrakcyjna_teoria_funkcji#mod1:fact:naturalne|Fakcie 1.2]] jest dokładnie twierdzeniem o rekursji. Pozostaje nam zatem udowodnienie implikacji przeciwnej.
 
</div></div>
 
</div></div>
  
Linia 19: Linia 19:
 
Załóżmy zatem, że <math>N</math> jest pewnym zbiorem, który posiada wyróżniony element <math>0\in N</math> i funkcję <math>s\colon N\to N</math> spełniającą warunki zadania. Udowodnimy po kolei następujące zdania (znane jako aksjomaty Peano), które - zgodnie z wykładnią teorii mnogości - w sposób jednoznaczny determinują liczby naturalne spośród innych zbiorów, a co za tym idzie, potwierdzą, że zbiór <math>N</math> jest zbiorem liczb naturalnych: [[grafika:Peano-portret.gif|thumb|right||Giuseppe Peano (1858-1932)<br>[[Biografia Peano|Zobacz biografię]]]]  
 
Załóżmy zatem, że <math>N</math> jest pewnym zbiorem, który posiada wyróżniony element <math>0\in N</math> i funkcję <math>s\colon N\to N</math> spełniającą warunki zadania. Udowodnimy po kolei następujące zdania (znane jako aksjomaty Peano), które - zgodnie z wykładnią teorii mnogości - w sposób jednoznaczny determinują liczby naturalne spośród innych zbiorów, a co za tym idzie, potwierdzą, że zbiór <math>N</math> jest zbiorem liczb naturalnych: [[grafika:Peano-portret.gif|thumb|right||Giuseppe Peano (1858-1932)<br>[[Biografia Peano|Zobacz biografię]]]]  
  
*<math>\exists 0\in N</math>   
+
*<math>\exists 0\in N.</math>   
 
To wiemy z założenia.
 
To wiemy z założenia.
*<math>\forall n\in N \ s(n)\in N</math>   
+
*<math>\forall n\in N \ s(n)\in N.</math>   
 
To wiemy z założenia.  
 
To wiemy z założenia.  
*<math>\forall n\in N \ s(n)\neq 0</math>  
+
*<math>\forall n\in N \ s(n)\neq 0.</math>  
Przypuśćmy przeciwnie, że dla pewnego <math>n\in N</math> mamy <math>s(n)=0</math>. Wtedy kładąc <math>X=\{e,a\}</math> oraz <math>g(e)=g(a)=a</math>, z założenia istnieje funkcja <math>f\colon N\to X</math> taka, że <math>f(0)=e</math> oraz <math>f(s(n))=g(f(n))</math>. A zatem <math>f(s(n))=f(0)=e\neq a = g(f(n))</math>, sprzeczność.
+
Przypuśćmy przeciwnie, że dla pewnego <math>n\in N</math> mamy <math>s(n)=0</math>. Wtedy, kładąc <math>X=\{e,a\}</math> oraz <math>g(e)=g(a)=a</math>, z założenia istnieje funkcja <math>f\colon N\to X</math> taka, że <math>f(0)=e</math> oraz <math>f(s(n))=g(f(n))</math>. A zatem <math>f(s(n))=f(0)=e\neq a = g(f(n))</math>, sprzeczność.
 
*<math>s</math> jest injekcją.  
 
*<math>s</math> jest injekcją.  
 
Przypuśćmy, że <math>s(n) = s(m)</math> dla pewnych <math>n,m\in N</math>. Kładąc <math>X :=  \{0,s(0),s(s(0)), ...\}</math> (jest to podzbiór <math>N</math>) oraz <math>e:=0</math>, wiemy, że istnieje funkcja <math>f\colon N\to X</math> taka, że <math>f(0)=0</math> oraz <math>f(s(n))=s(f(n))</math>. Taka funkcja jest tylko jedna, więc jej zawężenie do <math>X</math> musi być równe funkcji <math>h\colon X\to X</math>, która  spełnia warunki <math>h(0)=0</math> oraz <math>h(s(n))=n</math> dla <math>n\neq 0</math>. Dlatego założenie <math>s(n)=s(m)</math> implikuje <math>n=h(s(n))=h(s(m))=m</math>, co należało pokazać.   
 
Przypuśćmy, że <math>s(n) = s(m)</math> dla pewnych <math>n,m\in N</math>. Kładąc <math>X :=  \{0,s(0),s(s(0)), ...\}</math> (jest to podzbiór <math>N</math>) oraz <math>e:=0</math>, wiemy, że istnieje funkcja <math>f\colon N\to X</math> taka, że <math>f(0)=0</math> oraz <math>f(s(n))=s(f(n))</math>. Taka funkcja jest tylko jedna, więc jej zawężenie do <math>X</math> musi być równe funkcji <math>h\colon X\to X</math>, która  spełnia warunki <math>h(0)=0</math> oraz <math>h(s(n))=n</math> dla <math>n\neq 0</math>. Dlatego założenie <math>s(n)=s(m)</math> implikuje <math>n=h(s(n))=h(s(m))=m</math>, co należało pokazać.   
*<math>\forall A\subseteq N\ ((0\in A\wedge (a\in A\implies s(a)\in  A))\implies A=N)</math>
+
*<math>\forall A\subseteq N\ ((0\in A\wedge (a\in A\implies s(a)\in  A))\implies A=N).</math>
  
 
W tym punkcie przedstawimy najpierw rozumowanie teoriomnogościowe, a potem skorzystamy z okazji, aby ten sam dowód pokazać bardziej w duchu teorii kategorii (stopniowo ten drugi rodzaj dowodów będzie zastępował pierwszy).
 
W tym punkcie przedstawimy najpierw rozumowanie teoriomnogościowe, a potem skorzystamy z okazji, aby ten sam dowód pokazać bardziej w duchu teorii kategorii (stopniowo ten drugi rodzaj dowodów będzie zastępował pierwszy).
Linia 141: Linia 141:
 
Pokażmy najpierw, że złożenie izomorfizmów jest izomorfizmem. Załóżmy, że <math>f\colon A\to B</math> oraz <math>g\colon B\to C</math> są izmorfizmami. Wówczas ich złożenie <math>g\circ f\colon A\to C</math> posiada morfizm odwrotny <math>f^{-1}\circ g^{-1}</math>. Rzeczywiście, <math>(g\circ f)\circ (f^{-1}\circ g^{-1}) = g\circ )f\circ  f^{-1})\circ g^{-1} = g\circ 1_B \circ g^{-1} = g\circ g^{-1} =  1_C</math> i podobnie pokazujemy drugie z równań dla izomorfizmu.  
 
Pokażmy najpierw, że złożenie izomorfizmów jest izomorfizmem. Załóżmy, że <math>f\colon A\to B</math> oraz <math>g\colon B\to C</math> są izmorfizmami. Wówczas ich złożenie <math>g\circ f\colon A\to C</math> posiada morfizm odwrotny <math>f^{-1}\circ g^{-1}</math>. Rzeczywiście, <math>(g\circ f)\circ (f^{-1}\circ g^{-1}) = g\circ )f\circ  f^{-1})\circ g^{-1} = g\circ 1_B \circ g^{-1} = g\circ g^{-1} =  1_C</math> i podobnie pokazujemy drugie z równań dla izomorfizmu.  
  
Rozwiążemy to samo zadanie graficznie: zauważmy, że fakt, że <math>f</math>  jest izomorfizmem z odwrotnością <math>f^{-1}</math> jest wyrażony przez fakt, że poniższy diagram komutuje:  
+
Rozwiążemy to samo zadanie graficznie: zauważmy, że fakt, <math>f</math>  jest izomorfizmem z odwrotnością <math>f^{-1}</math> jest wyrażony przez fakt, że poniższy diagram komutuje:  
  
 
<center>[[Grafika:Tk_1_25.jpg]]
 
<center>[[Grafika:Tk_1_25.jpg]]
Linia 183: Linia 183:
  
 
<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">
Załóżmy, że <math>f\colon M\to N</math> jest bijektywnym  homomorfizmem z odwrotnością <math>g\colon N\to M</math>. Wystarczy pokazać,  że <math>g</math> jest homomorfizmem, tzn., że <math>g(e_N)=e_M</math> oraz  <math>g(n_1\circ_N n_2) = g(n_1)\circ_M g(n_2)</math> dla dowolnych <math>n_1,  n_2\in N</math>. Wykorzystując fakt, że <math>f</math> - jako homomorfizm -  zachowuje jedynkę, mamy: <math>e_M = g(f(e_M)) = g(e_N)</math>, czyli  pierwszą z szukanych równości. Znów opierając się na własnościach <math>f</math> mamy: <math>g(n_1)\circ_M g(n_2) = g(f(g(n_1)\circ_M g(n_2))) =  g(f(g(n_1))\circ_N f(g(n_2))) = g(n_1\circ_N n_2)</math>, co należało pokazać.  
+
Załóżmy, że <math>f\colon M\to N</math> jest bijektywnym  homomorfizmem z odwrotnością <math>g\colon N\to M</math>. Wystarczy pokazać,  że <math>g</math> jest homomorfizmem, tzn., że <math>g(e_N)=e_M</math> oraz  <math>g(n_1\circ_N n_2) = g(n_1)\circ_M g(n_2)</math> dla dowolnych <math>n_1,  n_2\in N</math>. Wykorzystując fakt, że <math>f</math> - jako homomorfizm -  zachowuje jedynkę, mamy: <math>e_M = g(f(e_M)) = g(e_N)</math>, czyli  pierwszą z szukanych równości. Znów, opierając się na własnościach <math>f</math>, mamy: <math>g(n_1)\circ_M g(n_2) = g(f(g(n_1)\circ_M g(n_2))) =  g(f(g(n_1))\circ_N f(g(n_2))) = g(n_1\circ_N n_2)</math>, co należało pokazać.  
 
</div></div>
 
</div></div>
  
Linia 229: Linia 229:
 
<center><math>\delta(x*y,s) := \delta(x,\delta(y,s))</math>,
 
<center><math>\delta(x*y,s) := \delta(x,\delta(y,s))</math>,
  
<math>\delta(e,s)=s</math>,
+
<math>\delta(e,s)=s</math>
 
</center>
 
</center>
  
Linia 252: Linia 252:
 
**<math>\lambda x.cx = c</math>, o ile <math>x</math> nie występuje w <math>c</math>.  
 
**<math>\lambda x.cx = c</math>, o ile <math>x</math> nie występuje w <math>c</math>.  
  
Definiujemy też relację <math>a\approx b</math> na termach (nazywaną zwyczajowo <math>\beta\eta</math>-równoważnością), jako relację równoważności generowaną przez równania i zamianę nazwy zmiennych związanych: o ile <math>y</math> nie występuje w <math>b</math>, to  
+
Definiujemy też relację <math>a\approx b</math> na termach (nazywaną zwyczajowo <math>\beta\eta</math>-równoważnością), jako relację równoważności generowaną przez równania i zamianę nazwy zmiennych związanych: o ile <math>y</math> nie występuje w <math>b</math>, to:
  
 
<center><math>\lambda x.b = \lambda y.b[y/x].</math></center>
 
<center><math>\lambda x.b = \lambda y.b[y/x].</math></center>
  
Kategorię '''<math>C(\lambda)</math>''' definiujemy teraz jak następuje:
+
Kategorię '''<math>C(\lambda)</math>''' definiujemy teraz, jak następuje:
  
 
*obiekty: typy <math>\lambda</math>-rachunku,
 
*obiekty: typy <math>\lambda</math>-rachunku,
Linia 273: Linia 273:
 
</center>
 
</center>
  
Kategorii '''<math>C(\lambda)</math>''' przyjrzymy się jeszcze uważniej w Wykładach [[Teoria_kategorii_dla_informatyków/Wykład_3:_Zasada dualności_i_proste_konstrukcje_uniwersalne#wyklad3|3]], [[Teoria_kategorii_dla_informatyków/Wykład 4:_Zaawansowane_konstrukcje_uniwersalne#wyklad4|4]].
+
Kategorii '''<math>C(\lambda)</math>''' przyjrzymy się jeszcze uważniej w Wykładach [[Teoria_kategorii_dla_informatyków/Wykład_3:_Zasada dualności_i_proste_konstrukcje_uniwersalne#wyklad3|3]]. i [[Teoria_kategorii_dla_informatyków/Wykład 4:_Zaawansowane_konstrukcje_uniwersalne#wyklad4|4]].
 
</div></div>
 
</div></div>

Aktualna wersja na dzień 09:50, 27 lis 2006

==Zadanie 1.1==

Udowodnij, że dla dwóch funkcji oraz , jeśli oraz , to funkcja jest bijekcją.

Rozwiązanie:

==Zadanie 1.2==

Udowodnij Fakt 1.2.

Wskazówka:
Rozwiązanie:

==Zadanie 1.3==

Znajdź przykład na to, że w kategorii Pos bijekcje nie zawsze są izomorfizmami.

Wskazówka:
Rozwiązanie:

==Zadanie 1.4==

Pokaż, że każda grupa może być traktowana jako kategoria, w której każdy morfizm jest izomorfizmem.

Rozwiązanie:

==Zadanie 1.5==

Dla dowolnej kategorii zaproponuj konstrukcję nowej kategorii, w której – żądamy – obiektami są morfizmy z .

Wskazówka:
Rozwiązanie:

==Zadanie 1.6==

Niech będzie kategorią, zaś jej ustalonym obiektem. Zaproponuj konstrukcję nowej kategorii, której obiektami są wszystkie morfizmy z o kodziedzinie .

Wskazówka:
Rozwiązanie:

==Zadanie 1.7==

Udowodnij, że złożenie izomorfizmów jest izomorfizmem, że morfizm odwrotny do izomorfizmu jest tylko jeden, a także, że identyczności w dowolnej kategorii są izomorfizmami.

Rozwiązanie:

==Zadanie 1.8==

Znajdź kategorię, która ma tę własność, że jeśli dwa obiekty są izomorficzne, to muszą być sobie równe.

Wskazówka:
Rozwiązanie:

==Zadanie 1.9==

Pokaż, że w kategorii Mon izomorfizmy to dokładnie bijektywne homomorfizmy monoidów.

Wskazówka:
Rozwiązanie:

==Zadanie 1.10==

Przekonaj się, że kategorie i funktory tworzą kategorię, którą oznaczamy .

Wskazówka:
Rozwiązanie:

==Zadanie 1.11==

Podaj dwa dalsze przykłady kategorii.

Wskazówka:
Rozwiązanie: