Test GR3: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
{tw}{Twierdzenie}[section]
{fa}[tw]{Fakt}
{AZbioruPustego}{Aksjomat Zbioru Pustego}
{APary}{Aksjomat Pary}
{ASumy}{Aksjomat Sumy}


{}{0pt}
Poniższe zdania twierdzące mogą być albo prawdziwe (oznaczone jako
{}{0pt}
"+"), albo fałszywe (oznaczane "-"). Zbiór wszystkich pytań
{}{0in}
podzielono na 15 części, odpowiadających kolejnym modułom.
{}{-0.5in}
{}{6.3in}
{}{9in}


{cwicz}[section]
; Pyt.1
{obra}[section]
:
{hint}
:; -
::  Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które
spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności,
dziedzin i kodziedzin morfizmów.


{thm}{Twierdzenie}[section]
:; +
{defn}[thm]{Definicja}
::  Dowolna kategoria może być interpretowana jako pewnien specjalny graf
skierowany.


{Zadanie}[thm]{Zadanie}
:; +
{Uwaga}[thm]{Uwaga}
::  Dowolna kategoria może być interpretowana jako pewna
{Przykład}[thm]{Przykład}
algebra.
{Rozwiązanie}[thm]{Rozwiązanie}
{Hint}[thm]{Hint}


{equation}{section}
:; +
::  Kategoria może być jednocześnie mała i lokalnie mała.


{kuba_preamble1}
:; -
{kuba_preamble2}
::  Kategoria może być jednocześnie mała i duża.


0mm
:; +
2ex
::  Kategoria może być jednocześnie lokalnie mała i duża.


{lem}[thm]{ Lemat  }
:; -
{mtw}[tw]{Meta twierdzenie}
::  Kategoria <math>\displaystyle \mathbf{C}</math>, w której dla każdego obiektu <math>\displaystyle A\in
\mathbf{C}_0</math> istnieje dokładnie jeden morfizm typu <math>\displaystyle A\to A</math>
nazywamy konkretną.


{Cwiczenie}[thm]{Ćwiczenie}
:; +
::  Kategoria <math>\displaystyle \mathbf{C}</math>, w której dla każdego obiektu <math>\displaystyle A\in
\mathbf{C}_0</math> istnieje dokładnie jeden morfizm typu <math>\displaystyle A\to A</math>
nazywamy dyskretną.


''' Logika i teoria mnogości'''
:; -
::  Kategoria <math>\displaystyle \mathbf{C}</math>, w której dla każdego obiektu <math>\displaystyle A\in
\mathbf{C}_0</math> istnieje dokładnie jeden morfizm typu <math>\displaystyle A\to A</math>
nazywamy monoidem.


'''Wykład 5'''
:; -
::  Kategoria <math>\displaystyle \mathbf{C}</math>, w której dla każdego obiektu <math>\displaystyle A\in
\mathbf{C}_0</math> istnieje dokładnie jeden morfizm typu <math>\displaystyle A\to A</math>
nazywamy posetem.


Zawartość wykładu: Para uporządkowana, iloczyn kartezjański, relacje, relacje
:; -
równoważności, rozkłady zbiorów, domykanie relacji, rozdział dla dociekliwych.
::  Nie istnieje kategoria, w której jest <math>\displaystyle 5</math> obiektów i <math>\displaystyle 6</math>
morfizmów.


==Para uporządkowana==
:; +
::  Nie istnieje kategoria, w której jest <math>\displaystyle 6</math> obiektów i <math>\displaystyle 5</math>
morfizmów.


Bardzo często będziemy chcieli mieć do czynienia ze zbiorem, który niesie w sobie
:; -
informacje o dwóch innych zbiorach, informacje tak udatnie zakodowaną aby można było
::  Nie istnieje kategoria, w której wszystkie obiekty są
odzyskać z niej każdą z jego składowych. Do tego celu wprowadzimy zbiór nazywany
izomorficzne.
''parą uporządkowaną'' dwóch innych zbiorów.


Niech <math>x</math> oraz <math>y</math> będą
:; -
zbiorami. Przez parę uporządkowaną <math>(x,y)</math> rozumiemy zbiór
::  Nie istnieje kategoria, w której wszystkie morfizmy mają tę samą kodziedzinę.


<center><math>\left\{ \left\{x\right\}\, \left\{x,y\right\}\\right\}\\]
:; +
::  Kategoria <math>\displaystyle \mathbf{Rel}</math> jest lokalnie mała i duża.


\enddefn
:; -
::  Liczby naturalne <math>\displaystyle (\mathbb{N},\leq)</math> są kategorią
dyskretną.


Parę uporządkowaną można zdefiniować inaczej na wiele sposobów. Chodzi jednak o to
:; -
aby ze zbioru który jest parą można było odzyskać jednoznacznie każdą z jego
::  Kategoria <math>\displaystyle \mathbf{Cat}</math> jest lokalnie mała.
składowych. Tak więc moglibyśmy zaakceptować każdą inną inną definicję pod warunkiem,
że będzie spełnione następujące twierdzenie:


{{twierdzenie|[Uzupelnij]||
:; +
::  Kategorie dyskretne są lokalnie małe.


Dla dowolnych zbiorów </math>a,b,c,d<math> zachodzi:
:; +
::  Kategorie konkretne są lokalnie małe.


</math></center>(a,b) <nowiki>=</nowiki> (c,d)   a<nowiki>=</nowiki>c {0.1mm}  b<nowiki>=</nowiki> d<center><math>
:; +
::  Grupa <math>\displaystyle (G,\circ,e)</math> to kategoria z jednym obiektem.


}}
:; -
::  <math>\displaystyle \mathbf{Grp}</math> to kategoria, w której wszystkie obiekty
są izomorficzne.


{{dowod|[Uzupelnij]||
:; +
::  Dowolne dwa izomorficzne obiekty w <math>\displaystyle \mathbf{Set}</math> są równoliczne.


Dowód przeprowadzimy tylko ze strony lewej do prawej bo w
:; +
odwrotnym kierunku jest to fakt oczywisty.
::  Preporządek jest z definicji taką kategorią, w której między
Niech zatem dwie pary </math>(a,b)<math> i </math>(c,d)<math> będą równe. Ponieważ
dowolnymi dwoma obiektami istnieje co najwyżej jeden morfizm.
</math>a  (a,b)<math> więc    </math>a  (c,d)<math>. Mamy zatem
</math>a<nowiki>=</nowiki> c lub  <math>\left\{a\right\}\ = \left\{c,d\right\}\$. W pierwszym
przypadku </math>a<nowiki>=</nowiki>c<math> ale w drugim również jest tak, mamy bowiem, że
</math>c  a. Pierwszą część twierdzenia mamy za sobą bo już wiemy,
że pierwsze współrzędne równych par są równe.


<center><math>(a,b) = (a,d) </math></center>
:; +
::  Preporządek jest kategorią lokalnie małą.


Następnie przeprowadzamy dowód przez przypadki. Jeżeli jest tak,
:; -
że <math>a=b</math> to <math>(a,b)=\left\{\left\{a\right\}\\right\}\$. Zatem </math>a<br>right<nowiki>=</nowiki>
:: Preporządek to taka kategoria, w której nie istnieją dwa różne
aa,d<br>right co daje, że <math>\left\{a,d\right\}\=\left\{a\right\}\$ a zatem
obiekty izomorficzne.
</math>d<nowiki>=</nowiki>a<math>. W przeciwnym przypadku gdy </math>a b<math> mamy, że </math>a,b
aa,d<br>right. Daje to dwie możliwości albo
<math>\left\{a,b\right\}\ = \left\{a\right\}\$ co nie może mieć miejsca bo mielibyśmy, że </math>a<nowiki>=</nowiki>b<math>,
albo zaś
</math>a,b<nowiki>=</nowiki> a,d. To drugie prowadzi do naszej tezy <math>b=d</math>.
}}


Dla każdej pary <math>x=(a,b)</math> udowodnij, że
:; +
::  Preporządek jest częściowym porządkiem wtedy i tylko wtedy, gdy każde
dwa obiekty izomorficzne są sobie równe.


<center><math>\bigcap \bigcap x= a.
:; +
</math></center>
::  Rachunek lambda jako kategoria jest lokalnie mała.


'''Rozwiązanie: '''Rozważymy dwa przypadki.
:; -
::  <math>\displaystyle \mathbf{Set}</math> jest obiektem <math>\displaystyle \mathbf{Cat}</math>.


# Jeśli <math>a=b</math> to <math>x=\{\{a\}\}</math> i wtedy <math>\bigcap \bigcap x= a</math>.
:; +
::  W każdej kategorii niepustej istnieją izomorfizmy.
; Pyt.2
:
:; +
::  Monomorfizmem w <math>\displaystyle \mathbf{Set}</math> jest każda funkcja injektywna.


# Jeśli <math>a\neq b</math> to <math>x=\{\{a\},\{a,b\}\}</math> a więc
:; -
::  Monomorfizmem w <math>\displaystyle \mathbf{Mon}</math> jest każda funkcja injektywna.


<center><math>\bigcap x= \bigcap \{\{a\},\{a,b\}\}=  \{a\} \cap \{a,b\}= \{a\}
:; +
</math></center>
::  Monomorfizmem w posecie <math>\displaystyle (P,\leq)</math> jest każda ze strzałek.


skąd otrzymujemy
:; +
::  Monomorfizmem w dowolnej kategorii <math>\displaystyle \mathbf{C}</math> jest każdy epimorfizm w
<math>\displaystyle \mathbf{C}^{op}</math>.


<center><math>\bigcap \bigcap x=a
:; +
</math></center>
::  W kategoriach dyskretnych monomorfizmy są izomorfizmami.


Udowodnij, że dla dowolnej pary uporządkowanej <math>x</math> zbiór
:; +
::  W kategoriach dyskretnych monomorfizmy są epimorfizmami.


<center><math>\bigcap \bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset))
:; +
</math></center>
::  Istnieją kategrie konkretne, w których każdy epimorfizm
jest surjekcją.


jest pusty gdy współrzędne par są różne, a w przeciwnym przypadku jest
:; -
zbiorem jednoelementowym zawierającym współrzędną pary <math>x</math>.
::  Istnieją kategrie konkretne, w których żaden epimorfizm
nie jest surjekcją.


'''Rozwiązanie: '''Jeśli <math>x</math> jest parą to istnieją zbiory <math>a,b</math> takie, że <math>x=(a,b)</math>.
:; +
::  Istnieją kategorie konkretne, w których pewne epimorfizmy
nie są surjekcjami.


# Przypuśćmy, że <math>a\neq b</math>. Wtedy <math>x= \{\{a\}, \{a,b\}\}</math> i <math>\mathcal{P}(x)=
:; +
\{\emptyset, \{\{a\}\}, \{\{a,b\}\},x \}</math>. Ponieważ <math>\mathcal{P}(\emptyset)=\{\emptyset\}</math>
::  Epimorfizm to pojęcie dualne do monomorfizmu.
to <math>\mathcal{P}(x) \setminus \mathcal{P}(\emptyset) =\{ \{\{a\}\}, \{\{a,b\}\},x \}</math> a wtedy


<center><math>\bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset)) = \emptyset
:; +
</math></center>
::  Izomorfizm to pojęcie samodualne (tj. dualne do samego
siebie).


gdyż przecinany zbiór zawiera elementy rozłączne <math>\{\{a\}\}, \{\{a,b\}\}</math>. Wobec
:; -
tego również
::  Monomorfizm to pojęcie samodualne.


<center><math>\bigcap \bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset)) = \emptyset
:; +
</math></center>
::  W <math>\displaystyle \mathbf{Top}</math> epimorfizmami są ciągłe surjekcje.


# W przypadku, gdy <math>a=b</math> otrzymujemy <math>x=\{\{a\}\}</math> a więc <math>\mathcal{P}(x)=\{\emptyset ,\{\{a\}\}\}</math> i wtedy <math>\mathcal{P}(x) \setminus \mathcal{P}(\emptyset) =\{ \{\{a\}\} \}</math> skąd otrzymujemy
:; -
::  W kategorii przestrzeni topologicznych Hausdorffa i
funkcji ciągłych epimorfizmy to dokładnie ciągłe surjekcje.


<center><math>\bigcap \bigcap ( \kPs(x) \setminus \mathcal{P}(\emptyset)) = \{a\}
:; +
</math></center>
::  W preporządku sekcje są izomorfizmami.


Pokaż, że z każdej pary <math>x</math> można otrzymać jej drugą współrzędną posługując się
:; +
jedynie parą <math>x</math>, mnogościowymi operacjami <math>\bigcup, \bigcap, \cup,\cap,\setminus,\kPs</math> oraz stałą <math>\emptyset</math>.
::  W preporządku pojęcia: sekcji, izomorfizmu, retrakcji,
monomorfizmu, epimorfizmu pokrywają się.


'''Wskazówka:  '''
:; +
::  Funktory wierne zachowują sekcje.


# Rozważ najpierw pary różnych elementów.
:; +
::  Retrakcje w <math>\displaystyle \mathbf{Set}</math> to dokładnie epimorfizmy.


# Wykorzystaj zbiór z Ćwiczenia [[##ex:paraPS|Uzupelnic ex:paraPS|]]
:; -
::  Jeśli funktor nie jest wierny, to nie musi zachowywać
retrakcji.


'''Rozwiązanie: '''Rozważmy najpierw przypadek gdy para ma różne elementy. Zobaczymy, że dla  każdej takiej pary <math>x=(a,b)</math> mamy
:; -
::  Każda sekcja jest monomorfizmem i epimorfizmem.


<center><math>
:; +
\bigcup (\bigcup x \setminus \bigcap x) =b.
::  Każda sekcja jest monomorfizmem.
</math></center>


Ponieważ <math>a\neq b</math> to <math>x=\{\{a\}, \{a,b\}\}</math> i wtedy
:; +
::  W kategorii dyskretnej każda sekcja jest epimorfizmem.


<center><math>\bigcup (\bigcup x \setminus \bigcap x)= \bigcup (\{a,b\} \setminus \{a\})=
:; -
\bigcup \{b\}= b.
::  Każdy wierny funktor odzwierciedla sekcje i retrakcje.
</math></center>


Zobaczmy teraz jak proponowany wzór działa na parach o równych współrzędnych. Jeśli
:; +
<math>x=(a,a)</math> to <math>x =\{\{a\}\}</math> i wtedy
::  W <math>\displaystyle \mathbf{Cat}</math> istnieją epimorfizmy, które nie są
surjekcjami.


<center><math>\bigcup (\bigcup x \setminus \bigcap x)= \bigcup (\{a\} \setminus \{a\})= \bigcup
:; +
\emptyset= \emptyset.
::  W <math>\displaystyle \mathbf{Cat}</math> istnieją epimorfizmy, które nie są
</math></center>
retrakcjami.


Musimy więc jeszcze trochę popracować. Wykorzystajmy  ćwiczenie [[##ex:paraPS|Uzupelnic ex:paraPS|]],
:; -
niech nowy wzór będzie postaci
:: Każdy funktor zachowuje monomorfizmy.


<center><math>\bigcup (\bigcup x \setminus \bigcap x) \cup \bigcap \bigcap \bigcap (\mathcal{P}(x)
:; -
\setminus \mathcal{P}(\emptyset)).
::  Każdy funktor pełny zachowuje izomorfizmy.
</math></center>


Dla par o różnych elementach dodana część wzoru jest zbiorem pustym, więc ta sytuacja
:; +
jest analogiczna do [[##eq:cwiczeniePara2wsp1|Uzupelnic eq:cwiczeniePara2wsp1|]], skąd otrzymujemy że tak
::  Homfunktory kowariantne zachowują i odzwierciedlają monomorfizmy.
zdefiniowany zbiór jest równy <math>b</math>.


Dla par o równych elementach, pierwsza część zbioru jest zbiorem pustym. W ćwiczeniu
:; -
[[##ex:paraPS|Uzupelnic ex:paraPS|]] pokazaliśmy że w takim przypadku mamy <math>\bigcap \bigcap (\mathcal{P}(x)
:: Mono retrakcja jest identycznością.
\setminus \mathcal{P}(\emptyset))=\{b\}</math> jeśli <math>b</math> jest współrzędną pary <math>x</math>. Wobec tego


<center><math>\bigcup (\bigcup x \setminus \bigcap x) \cup \bigcap \bigcap \bigcap (\mathcal{P}(x)
:; +
\setminus \mathcal{P}(\emptyset))= \emptyset \cup \bigcap\{b\}=b.
::  Mono retrakcja jest izomorfizmem.
</math></center>


==Iloczyn kartezjański==
:; -
::  Retrakt dziedziny ciągłej jest algebraiczny.


Zanim wprowadzimy definicję zbioru wszystkich par uporządkowanych
:; +
elementów dwóch zbiorów (zwanego dalej iloczynem kartezjańskim)
:: Retrakt dziedziny algebraicznej jest algebraiczny.
należy nam się krótka dyskusja. Otóż niech <math>x\in X</math> oraz <math>y \in Y</math>.
Łatwo zauważyć, że zarówno
<math>\left\{x,y\right\}\$ jak i </math>x są podzbiorami <math>X \cup Y</math>.
Zatem
<math>\left\{x,y\right\}\ \in \mathcal{P} (X \cup Y)</math> oraz <math>\left\{x\right\}\ \in \mathcal{P} (X \cup Y)</math>.
Więc <math>\left\{\left\{x\right\}\,\left\{x,y\right\}\\right\}\ \subseteq \mathcal{P} (X \cup Y)</math> co daje,
że <math>(x,y) \in \mathcal{P} (\mathcal{P} (X \cup Y))</math>.


Istnienie i konstrukcja iloczynu
:; +
kartezjańskiego zostało dokładnie omówione w dodatkowym
:: W parze e-p zanurzenie <math>\displaystyle e</math> jest injekcją.
rozdziale [[##konstukcja_marcina|Uzupelnic konstukcja_marcina|]] znajdującym się na końcu.
Proponuje przestudiowanie dodatkowego
rozdziału dopiero po zapoznaniu się z rozdziałami wcześniejszymi
pomimo braku precyzji w następnej definicji.


Niech <math>x,y</math> będą zbiorami. Iloczynem kartezjańskim (produktem)
:; -
<math>x \times y</math> nazywamy zbiór
::  W parze e-p projekcja jest injekcją.


<center><math>\left\{z\in \mathcal{P}( \mathcal{P}( x \cup y)): \exists_{a \in x} \exists_{b \in y}
:; +
\;\; (a,b) =z\right\}\
::  W <math>\displaystyle \mathbf{Rel}</math> obiektem początkowym jest relacja
</math></center>
pusta.


Będziemy używać specjalnej notacji <math>x^2</math> na zbiór <math>x \times x</math>.
:; +
::  W <math>\displaystyle \mathbf{Grp}</math> obiektem początkowym jest każdy obiekt
końcowy


Pokaż następujące elementarne własności iloczynu kartezjańskiego:
:; +
::  W <math>\displaystyle \mathbf{Pos}</math> nie istnieje obiekt, który jest
jednocześnie początkowy i końcowy.


<center><math>\alignedx \times \emptyset    & = & \emptyset \\
:; +
x \times (y \cup z)    & = & (x \times y) \cup  (x \times z) \\
:: Każde dwa obiekty początkowe w dowolnej kategorii są
x \times (y \cap z)    & = &  (x \times y) \cap  (x \times z) \\
izomorficzne.
x \times (y \setminus z)    & = &  (x \times y) \setminus  (x \times z)
\endaligned</math></center>


'''Rozwiązanie: '''Z definicji iloczynu kartezjańskiego, oraz twierdzenia [[##para-up_tw|Uzupelnic para-up_tw|]] łatwo wynika
:; -
następujący fakt, który wykorzystamy w dowodach. Dla dowolnych zbiorów <math>a,b,x,y</math>
::  <math>\displaystyle \mathbf{Cat}</math> nie ma obiektu początkowego.
zachodzi


<center><math>(a,b)\in x \times y \Leftrightarrow (a\in x \wedge b\in y).
:; -
</math></center>
::  Każda kategoria dyskretna jest obiektem końcowym w
<math>\displaystyle \mathbf{Cat}</math>.


# 
:; +
x    <nowiki>=</nowiki><br>
:: Istnieją małe kategorie, w których nie ma obiektów
z {P}({P}(x z)): _{a x} _{b } (a,b)<nowiki>=</nowiki>z<nowiki>=</nowiki><br>
początkowych, ani końcowych.
z {P}({P}(x  z)): _{a x} _{b}[ (b  )  (a,b)<nowiki>=</nowiki>z]


Ponieważ <math>b\in \emptyset</math> jest zawsze fałszem to powyższy zbiór jest pusty.
:; +
::  Jeśli w danej kategorii pewien obiekt początkowy i pewien obiekt końcowy
są izomorficzne, to kategoria ta posiada tylko jeden morfizm.


# Ponieważ obydwa zbiory są zbiorami par więc wykażemy że dowolna para należy do jednego
:; +
wtedy i tylko wtedy gdy należy do drugiego. Weźmy dowolną parę <math>(a,b)</math> wtedy
::  Funkcja następnik <math>\displaystyle \mathrm{succ}\colon \mathbb{N}\to
\mathbb{N}</math> jest uogólnionym elementem <math>\displaystyle \mathbb{N}</math>.


(a,b) x  (y  z) <br>
:; +
a  x  b (y z) <br>
:: Każdy element jest uogólnonym elementem, ale nie
a x  (b y  b z) <br>
odwrotnie.
(a x  b y)  (a x  b z) <br>
(a,b)  x y  (a,b) x  z <br>
(a,b)  x  y  x  z.


# Analogicznie do poprzedniego punktu, weźmy dowolną parę <math>(a,b)</math>, wtedy
:; +
::  W odcinku <math>\displaystyle ((0,1),\leq)</math> (jako kategorii) istnieje kontinuum elementów.


(a,b) x  (y  z) <br>
:; +
a  x  b (y z) <br>
:: W odcinku <math>\displaystyle ([0,1],\leq)</math> istnieje kontinuum elementów.
a x  (b y  b z) <br>
(a x  b y) (a x  b z) <br>
(a,b)  x  y  (a,b) x  z <br>
(a,b)  x  y  x  z.


# Analogicznie do poprzednich punktów, weźmy dowolną parę <math>(a,b)</math>, wtedy
:; -
::  W odcinku <math>\displaystyle ((0,1),\leq)</math> istnieje kontinuum elementów
uogólnionych.


(a,b)  (x  y)  (x  z)  <br>
:; +
a x b y  (a x  b z) <br>
:: Każdy element, którego kodziedziną jest obiekt końcowy
b y  (a x  (a x  b z)) <br>
jest identycznością.
b y  [(a x  a x)  (a x  b z)] <br>
b y  (a x  b z) <br>
a x  (b y  z) <br>
(a,b)  x  (y  z)


Produkt kartezjański <math>\times</math> jest monotoniczny ze względu na każdą współrzędną
:; +
osobno to znaczy:
::  Każdy element, którego kodziedziną jest obiekt początkowy
jest identycznością obiektu początkowego.


<center><math>\alignedx \subset y  & \hspace*{0.1mm} \Rightarrow  &  (x \times z) \subset  (y \times z) \\
:; +
x \subset y & \hspace*{0.1mm} \Rightarrow  &  (z \times x) \subset  (z \times y)
:: Każdy element jest monomorfizmem.
\endaligned</math></center>


'''Rozwiązanie: '''Ćwiczenie jest elementarne.
:; +
::  Każdy element jest sekcją.


# Niech <math>x,y</math> będą dowolnymi zbiorami takimi, że <math>x\subset y</math>. Wtedy dla dowolnej pary <math>(a,b)</math> mamy
:; -
::  Każdy element jest retrakcją.


(a,b) x z <br>
:; -
a x b  z <br>
:: Każdy element jest izomorfizmem.
a y  b  z <br>
(a,b) y z.


Stąd <math>(x \times z) \subset (y \times z)</math>.
:; -
:: Złożenie elementów jest elementem.
; Pyt.3
:
:; +
::  Aksjomaty kategorii są samodualne.


# Dla dowolnych zbiorów <math>x\subset y</math> mamy <math>x \cup y =y</math>. Z poprzedniego
:; -
ćwiczenia otrzymujemy
::  Pojęcie retrakcji jest samodualne.


<center><math>z \times y =z \times (x\cup y) = (z \times x)\cup(z \times y) \supset (z \times x).
:; -
</math></center>
:: Pojęcie obiektu końcowego jest samodualne.


(Metoda z poprzedniego punktu podziała równie dobrze.)
:; +
::  Pojęcie izomorfizmu jest samodualne.


Sprawdź, czy dla dowolnych zbiorów <math>A,B,C</math>, prawdziwa jest następująca implikacja
:; -
::  Niech <math>\displaystyle \mathbf{C}</math> będzie kategorią z produktami. Niech
<math>\displaystyle A,B,C,D\in \mathbf{C}_0</math> i <math>\displaystyle f,g\in \mathbf{C}_1</math>. Jeśli <math>\displaystyle A\times
B\cong C\times D</math>, to <math>\displaystyle A\cong C</math> i <math>\displaystyle B\cong D</math>.


<center><math>A\times B = A\times C \Rightarrow B=C
:; -
</math></center>
::  Niech <math>\displaystyle \mathbf{C}</math> będzie kategorią z produktami. Niech
<math>\displaystyle A,B,C,D\in \mathbf{C}_0</math> i <math>\displaystyle f,g\in \mathbf{C}_1</math>. Jeśli <math>\displaystyle A\times
B\cong B\times A</math>, to <math>\displaystyle A\cong B</math>.


'''Rozwiązanie: '''Nie. Na przykład gdy <math>A=\emptyset</math> to dla dowolnych zbiorów <math>B,C</math> mamy
:; +
::  Niech <math>\displaystyle \mathbf{C}</math> będzie kategorią z produktami. Niech
<math>\displaystyle A,B,C,D\in \mathbf{C}_0</math> i <math>\displaystyle f,g\in \mathbf{C}_1</math>. Jeśli <math>\displaystyle A\times
\mathbf{1}\cong \mathbf{1}</math>, to <math>\displaystyle A\cong \mathbf{1}</math>.


<center><math>\emptyset \times B =\emptyset = \emptyset \times C.
:; +
</math></center>
::  Jeśli <math>\displaystyle f,g</math> są sekcjami, to <math>\displaystyle f\times g</math> też.


Biorąc różne zbiory <math>B,C</math> otrzymamy kontrprzykład dla badanej implikacji.
:; +
::  Jeśli <math>\displaystyle f,g</math> są retrakcjami, to <math>\displaystyle f\times g</math> też.


==Relacje==
:; +
::  Jeśli <math>\displaystyle f,g</math> są izomorfizmami, to <math>\displaystyle f\times g</math> też.


Relacją nazywamy każdy podzbiór iloczynu <math>x
:; -
\times y</math>  
::  Jeśli <math>\displaystyle f,g</math> są monomorfizmami, to <math>\displaystyle f\times g</math> też.


===Operacje na relacjach:===
:; +
::  Lambda rachunek jest kategorią z produktami.


Niech <math>R \subset A \times B</math> oraz <math>S \subset B \times C</math>.
:; +
::  Każdy zbiór jest koproduktem pewnych dwóch innych zbiorów
w <math>\displaystyle \mathbf{Set}</math>.


<math>S \circ R  :=  \left\{(x,z)\in A \times C : \exists_{y\in B}
:; +
(x,y)\in R \hspace*{0.1mm} \wedge  (y,z)\in S \right\}\$
::  W posecie <math>\displaystyle (P,\leq)</math> każdy produkt <math>\displaystyle a\times b</math> dla <math>\displaystyle a,b\in P</math>
(o ile istnieje) jest ekwalizatorem wtedy i tylko wtedy, gdy
<math>\displaystyle a=b</math>.


\bigskip
:; -
::  Każdy ekwalizator jest epimorfizmem.


</math>R^{-1} :<nowiki>=</nowiki> (y,x) B  A :  (x,y) R
:; -
::  W kategorii z pulbakami zawsze istnieją obiekty początkowe.


<math>R_L := \left\{x\in A : \exists_{y\in B} \;\; (x,y) \in R\right\}\$
:; +
:: W kategorii z pulbakami i obiektem końcowym zawsze istnieją ekwalizatory.


</math>R_P :<nowiki>=</nowiki> y B : _{x A}  (x,y) R
:; -
::  Każda sekcja jest ekwalizatorem.


Niech relacja  <math> R \subset A \times B,  S \subset B \times C</math> oraz
:; +
<math>T \subset C \times D</math>. Pokazać elementarne własności operacji na relacjach:
:: Pulbak epimorfizmu jest epimorfizmem.


<center><math>\alignedT \circ ( S \circ R ) & = & (T \circ S)\circ R \\
:; +
(S \circ R )^{-1}    & = & R^{-1} \circ S^{-1} \\
:: Pulbak izomorfizmu jest izomorfizmem.
R                    & \subset & R_L \times R_P \\
(S \circ R)_L        & \subset & R_L \\
(S \circ R)_P        & \subset & S_P \\
(R^{-1} )_L          & = & R_P
\endaligned</math></center>


'''Rozwiązanie: '''Ćwiczenie jest elementarne.
:; +
::  Każda kategoria z koproduktami i koekwalizatorami posiada
pushouty.


#  
:; -
(x,z) T  ( S  R ) <br>
:: Każda kategoria z obiektem początkowym i koekwalizatorami
_{u} [(x,u) ( S R )  (u,z) T]<br>
posiada obiekt końcowy.
_{u} [_{v}( (x,v)  R (v,u)  S)  (u,z) T]<br>
   
_{u} _{v}[ (x,v)  R (v,u)  S  (u,z) T]<br>
; Pyt.4
_{v} _{u}[ (x,v)  R ((v,u)  S (u,z) T)]<br>
:
_{v} [ (x,v)  R _{u}((v,u)  S  (u,z) T)]<br>
   
_{v} [ (x,v)  R (v,z) T  S]<br>
:; +
(x,z)  (T  S)  R <br>
:: Zbiory skończone i funkcje tworzą kategorię kartezjańsko
zamkniętą.


# 
:; -
(x,z) (S  R )^{-1}  <br>
:: Przestrzenie topologiczne i funkcje ciągłe tworzą
(z,x)  S R  <br>
kategorię kartezjańsko zamkniętą.
_{y} [(z,y) R  (y,x) S]  <br>
_{y} [(y,z)  R^{-1}  (x,y) S^{-1}]  <br>
(x,z)  R^{-1}  S^{-1} <br>


#  
:; +
(x,z) R  <br>
:: Lambda rachunek (z dodanym elementem końcowym) jest kategorią kartezjańsko zamkniętą.
_{y} (x,u)  R  _{v} (v,y) R <br>
x R_L  y R_P  <br>
(x,y)  R_L  R_P


# 
:; -
x  (S  R)_L    <br>
:: Algebry Boole'a jako kategorie są kozupełne.
_{z} (x,z) S R <br>
_{z} _{y} [(x,y) R  (y,z) S ]  <br>
_{z} _{y} (x,y) R  <br>
_{y} (x,y) R  <br>
x R_L


# Dowód <math>(S \circ R)_P \subset S_P </math> jest analogiczny do poprzedniego.
:; +
:: Algebry Boole'a są dystrybutywne.


# 
:; +
x (R^{-1} )_L  <br>
:: Algebry Heytinga jako kategorie są kartezjańsko zamknięte.
_{y} (x,y) R^{-1} <br>
_{y} (y,x) R <br>
x R_P


Niech relacja <math> R \subset B \times C,  S \subset B \times C</math> oraz
:; -
<math>T \subset A \times  B</math>. Pokaż własności:
:: Grupy abelowe i homomorfizmy grup są kartezjańsko
zamknięte.


<center><math>\aligned(R \cup  S )^{-1} & = & R^{-1} \cup S^{-1} \\
:; -
(R \cap  S )^{-1} & = & R^{-1} \cap S^{-1} \\
:: Kategorie dyskretne są kartezjańsko zamknięte.
(R^{-1})^{-1}    & = & R \\
(R \cup  S ) \circ T & = &  (R \circ T) \cup (S  \circ T)\\
(R \cap  S ) \circ T & \subset &  (R \circ T) \cap (S  \circ T)
\endaligned</math></center>


'''Rozwiązanie: '''Ćwiczenie jest elementarne.
:; +
W poniższych punktach (1-4) pokażemy, że dowolna para należy do zbioru po lewej
::  Algebra Heytinga jest algebrą Boole'a wtedy i tylko
stronie odpowiedniej równości wtedy i tylko wtedy gdy należy do prawej. W punkcie 5,
wtedy, gdy każdy element posiada element przeciwny.
pokazujemy jedynie implikację w prawą stronę, gdyż mamy udowodnić inkluzję.


# 
:; -
(x,y) (R S)^{-1}  <br>
:: Kategoria dziedzin ciągłych i funkcji ciągłych w sensie
(y,x) (R S)  <br>
Scotta jest kartezjańsko zamknięta.
(y,x) R  (y,x)  S <br>
(x,y) R^{-1}  (x,y)  S^{-1}  <br>
(x,y) R^{-1}  S^{-1}


# Dowód drugiej równości jest analogiczny do dowodu pierwszej, wystarczy użyć <math>\cap</math> w miejsce <math>\cup</math> oraz <math>\wedge</math> w miejsce <math>\vee</math>.
:; +
::  Dla dowolnej topologii krata zbiorów otwartych jest
algebrą Heytinga.


# 
:; -
(x,y) (R^{-1})^{-1}  <br>
::  Dla dowolnej topologii krata zbiorów otwartych jest
(y,x) R^{-1}  <br>
algebrą Boole'a.
(x,y) R


# 
:; +
(x,z) (R  S )  T  <br>
:: Zbiory otwarte, regularne w dowolnej topologii tworzą
_y [(x,y)  T  (y,z) (R  S )] <br>
algebrę Boole'a.
_y [(x,y)  T  ((y,z) R  (y,z) S ))] <br>
_y [((x,y)  T  (y,z) R)  ((x,y)  T  (y,z) S ))] <br>
[_y ((x,y)  T  (y,z) R)]  [_y ((x,y)  T  (y,z) S )] <br>
(x,z) (R T)  (x,z) (S  T)  <br>
(x,z)  (R  T)  (S  T)


# 
:; -
(x,z) (R  S )  T  <br>
:: Każda algebra Boole'a jest izomorficzna ze zbiorem
_y [(x,y)  T  (y,z) (R  S )] <br>
podzbiorów pewnego zbioru.
_y [(x,y)  T  ((y,z) R  (y,z) S ))] <br>
_y [((x,y)  T  (y,z) R)  ((x,y)  T  (y,z) S ))] <br>
[_y ((x,y)  T  (y,z) R)]  [_y ((x,y)  T  (y,z) S )] <br>
(x,z) (R  T)  (x,z) (S T)  <br>
(x,z)  (R  T)  (S  T)


Podaj przykład relacji dla których poniższa równość nie jest prawdziwa.
:; +
::  Monomorfizmy o wspólnej kodziedzinie uporządkujmy
relacją "faktoryzacji", tj. <math>\displaystyle f\leq g</math> wtw, gdy istnieje <math>\displaystyle h</math> tak,
że <math>\displaystyle g\circ h =f</math>. Zdefiniujmy relację równoważności <math>\displaystyle R</math> między
monomorfizmami o wspólnej kodziedzinie jako: <math>\displaystyle f\equiv g</math> wtw, gdy
<math>\displaystyle f\leq g</math> i <math>\displaystyle g\leq f</math>. Uporządkujmy zbiór klas abstrakcji tej
relacji jako: <math>\displaystyle [f]\sqsubseteq [g]</math> wtw, gdy <math>\displaystyle f\leq g</math>. Czy ten
częściowy porządek jest algebrą Heytinga?


<center><math>(R \cap  S ) \circ T =  (R \circ T) \cap (S  \circ T)
:; +
</math></center>
::  Kategoria funkcji między zbiorami <math>\displaystyle \mathbf{Set}^{\to}</math> jest kartezjańsko zamknięta.


'''Rozwiązanie: '''Niech <math>R=\{(1,3)\}, S= \{(2,3)\}, T=\{(0,1),(0,2)\}</math> wtedy
:; -
::  Kategoria porządków liniowych i funkcji monotonicznych
jest kartezjańsko zamknięta.


# <math>R\cap S=\emptyset</math> więc      <math>(R\cap S)\circ T=\emptyset</math>.
:; -
::  W kategorii kartezjańsko zamkniętej <math>\displaystyle \mathbf{C}</math> funktor podnoszenia do potęgi <math>\displaystyle [A,-]</math> zachowuje
koprodukty (tutaj <math>\displaystyle A\in \mathbf{C}_0</math>).


# <math>T\circ R =\{(0,3)\}</math> i <math>T \circ S=\{0,3\}</math> a więc
:; +
<math>(R \circ T) \cap (S  \circ T) =\{0,3\}</math>
::  W kategorii kartezjańsko zamkniętej <math>\displaystyle \mathbf{C}</math> funktor podnoszenia do potęgi <math>\displaystyle [A,-]</math> zachowuje
obiekt końcowy (tutaj <math>\displaystyle A\in \mathbf{C}_0</math>).
; Pyt.5
:
:; +
::  Funktory tego samego typu wraz z ich transformacjami
naturalnymi tworzą kategorię.


Udowodnij, że zbiór <math>A</math> jest relacją wtedy i tylko wtedy gdy
:; +
::  <math>\displaystyle \mathbf{Top}</math> jest konkretna.


<center><math>A \subset (\bigcup \bigcup A) \times  (\bigcup \bigcup A)
:; +
</math></center>
::  <math>\displaystyle \mathbf{Rel}</math> jest konkretna.


'''Rozwiązanie: '''Pokażemy najpierw, że dla każdej relacji <math>R</math> mamy
:; +
::  Funktor <math>\displaystyle \mathrm{List}\colon \mathbf{Set}\to\mathbf{Mon}</math>
zachowuje koprodukty.


<center><math>
:; -
\bigcup \bigcup R = R_L \cup R_P.
::  Funktor <math>\displaystyle \mathrm{List}\colon \mathbf{Set}\to\mathbf{Mon}</math>
</math></center>
zachowuje obiekt końcowy.


Zaczniemy od inkluzji <math>\subset</math>.Weźmy dowolny element <math>x \in \bigcup \bigcup R</math> wtedy
:; +
musi istnieć element <math>y\in \bigcup R</math> taki że <math>x\in y</math>. Skoro <math>y\in \bigcup R</math> to
::  Funktor <math>\displaystyle \mathrm{List}\colon \mathbf{Set}\to\mathbf{Mon}</math> zachowuje obiekt początkowy.
musi istnieć para <math>(a,b) \in R</math> taka, że <math>y\in (a,b)</math>. Wobec tego z definicji pary
uporządkowanej <math>y=\{a\}</math> lub <math>y=\{a,b\}</math>. Ponieważ <math>x\in y</math> to <math>x=a</math> i wtedy <math>x\in
R_L</math> lub <math>x=b</math> i wtedy <math>x\in R_P</math>. Wobec tego <math>x\in R_L \cup R_P</math>.


Pokażemy teraz prawdziwość inkluzji <math>\supset</math> w równaniu [[##eq:cwiczenieBCBC|Uzupelnic eq:cwiczenieBCBC|]].
:; -
Weźmy dowolny element <math>a\in R_L</math> wtedy istnieje element <math>b\in R_P</math> taki, że <math>(a,b)\in
:: Funktor zapominania <math>\displaystyle \mathbf{Top}\to\mathbf{Set}</math> jest
R</math>, a więc <math>\{(a,b)\} \subset R</math>. Stąd otrzymujemy
pełny.


<center><math>\bigcup \bigcup \{(a,b)\} \subset \bigcup \bigcup R.
:; -
</math></center>
::  Kontrawariantny funktor potęgowy jest pełny.


Ponieważ  <math>\bigcup \bigcup \{(a,b)\}= \bigcup \{\{a\},\{a,b\}\} = \{a,b\}</math> to
:; +
otrzymujemy <math>\{a,b\} \subset R</math>, a więc <math>a\in R</math>. Analogiczne rozumowanie można
:: Każda rama jest algebrą Heytinga.
przeprowadzić dla elementu <math>b\in R_P</math>. Zakończyliśmy więc dowód równości
[[##eq:cwiczenieBCBC|Uzupelnic eq:cwiczenieBCBC|]].


W temacie ćwiczenia implikacja w lewą stronę jest oczywista. Jeśli <math>A</math> jest zbiorem
:; +
to <math>\bigcup \bigcup A</math> jest zbiorem i <math>A</math> jest podzbiorem iloczynu kartezjańskiego
::  Operacja przypisująca danej przestrzeni topologicznej jej
dwóch zbiorów więc musi być relacją. Dla implikacji w prawą stronę załóżmy, że <math>A</math>
zbiory otwarte może być rozszerzona do funktora kontrawariantnego.
jest relacją wtedy


<center><math>A \subset A_L \times A_P \subset (A_L \cup A_P) \times (A_L \cup A_P) =    (\bigcup \bigcup A) \times (    \bigcup \bigcup A)
:; -
</math></center>
::  Kontrawariantny funktor potęgowy jest zawsze wierny.


== Relacje równoważności ==
:; +
::  Transformacja naturalna dwóch funktorów, której komponentami są
izomorfizmy jest izomorfizmem w pewnej kategorii funktorów.


W tym podrozdziale poznamy ważną klasę (zbiór) relacji zwaną klasą
:; +
relacji równoważności(w innych podręcznikach mogą się państwo spotkać z nazwą relacja
::  Istnieją dwa funktory, których złożenie jest
abstrakcji). Relacje takie będą służyły do definiowania pojęć abstrakcyjnych o czym
transformacją identycznościową w <math>\displaystyle \mathbf{Set}</math>, ale które nie są
przekonamy się w wielu miejscach tego i innych wykładów. Bardzo dobrym ćwiczeniem
izomorficzne.
pokazującym abstrakcyjne metody definiowania pojęć będzie wykład <math>8</math> w którym
zaprzęgniemy relacje abstrakcji do definiowania liczb.


Rozpoczynamy rozdział od koniecznej definicji.
:; -
::  Operacja, która przestrzeni wektorowej <math>\displaystyle V</math> przypisuje
jej przestrzeń podwójnie dualną <math>\displaystyle V^{**}</math> jest naturalnym
izomorfizmem.


Dla zbioru <math>X</math> definiujemy relację <math>1_X \subset X \times X</math>
:; +
jako <math>\left\{ z \in X \times X : \exists_{x\in X} \;\; (x,x)=z  \right\}\$.
::  Operacja, która przestrzeni wektorowej <math>\displaystyle V</math> przypisuje
\enddefn
jej przestrzeń podwójnie dualną <math>\displaystyle V^{**}</math> jest naturalnym
izomorfizmem, o ile <math>\displaystyle V</math> jest skończenie wymiarowa.


\begindefn
:; +
Relację </math>R  X X<math> nazywamy relacją równoważnością o
:: Kowariantny homfunktor zachowuje produkty dowolnej mocy.
polu </math>X<math> jeżeli:


* zawiera relacje </math>1_X <math> (zwrotność </math>R<math>)
:; -
::  Dla dowolonych zbiorów <math>\displaystyle X,Y</math> istnieje następująca
bijekcja:<br>
<math>\displaystyle \mathcal{P}(X\times Y)\cong \mathcal{P}(X)\times \mathcal{P}(Y)</math>.


* </math>R^{-1} R<math> (symetria </math>R<math>)
:; -
::  Operacja <math>\displaystyle F\colon \mathbf{C}\times \mathbf{D}\to
\mathbf{E}</math> jest bifunktorem wtedy i tylko wtedy, gdy dla
dowolnych obiektów <math>\displaystyle C\in \mathbf{C}_0</math>, <math>\displaystyle D\in \mathbf{D}_0</math>
operacje <math>\displaystyle F(C,-)\colon \mathbf{D}\to \mathbf{E}</math> oraz
<math>\displaystyle F(-,D)\colon \mathbf{C}\to\mathbf{E}</math> są funktorami.


* </math>R R  R<math> (przechodniość </math>R<math>)
:; -
:: Inkluzja <math>\displaystyle \mathbf{Grp}\to\mathbf{Cat}</math> zachowuje
eksponenty.
; Pyt.6
:
:; -
::  Każde dwie równoważne kategorie są izomorficzne.


\enddefn
:; +
::  Każde dwie izomorficzne kategorie są równoważne.


\beginCwiczenie
:; -
Pokazać, że definicje zwrotności, symetryczności i przechodniości relacji o polu </math>X<math>
::  Każde dwie dualne kategorie są izomorficzne.
są odpowiednio równoważne następującym własnościom:


* </math>_{ x X} (x,x)  R<math>
:; -
::  Funktor jest równoważnością wtedy i tylko wtedy, gdy jest
pełny i wierny.


* </math>_{ x,y X} (x,y)  R  (y,x)  R<math>
:; +
:: Jeśli preporządek jest równoważny porządkowi, to jest
porządkiem.


* </math>_{ x,y,z X} (x,y) R  (y,z)  R (x,z) R<math>
:; +
:: Istnieją dwa preporządki równoważne, które nie są
izomorficzne.


\textbf{Rozwiązanie: }Ćwiczenie jest elementarne.
:; +
\endCwiczenie
::  Kategoria zbiorów i funkcji jest dualna do kategorii
zupełnych algebr Boole'a i homomorfizmów.


\begindefn Niech </math>R<math> będzie relacją równoważności o
:; -
polu </math>X<math>. Klasą równoważności elementu </math>x X<math> jest zbiór
:: Kategoria zbiorów skończonych i funkcji jest dualna do kategorii
algebr Boole'a.


</math></center>[x]_R :<nowiki>=</nowiki> y  X : (x,y) R<center><math>
:; -
::  Każda atomowa algebra Boole'a jest izomorficzna ze zbiorem
podzbiorów pewnego zbioru.


\enddefn  
:; -
:: Każda zupełna algebra Boole'a jest izomorficzna ze
zbiorem podzbiorów pewnego zbioru.


\begindefn Zbiór klas równoważności relacji </math>R<math> będący elementem zbioru </math>{P}
:; +
( {P} (X  X))<math> oznaczamy przez </math>X/R<math>. \enddefn 
:: Jeśli algebra Boole'a jest izomorficzna ze zbiorem
podzbiorów pewnego zbioru, to jest zupełna.


{{twierdzenie|[Uzupelnij]||
:; -
::  Każda zupełna algebra Boole'a jest atomowa.


Niech </math>R<math> będzie relacją równoważności o polu </math>X<math>. Następujące warunki są równoważne
:; +
::  Każda skończona algebra Boole'a jest zupełna.


# </math>[x]_R [y]_R  <math>
:; -
:: Każda atomowa algebra Boole'a jest skończona.


# </math>[x]_R <nowiki>=</nowiki> [y]_R<math>
:; +
::  Każda skończona algebra Boole'a jest atomowa.


# </math>(x,y) R<math>
:; +
:: Każda rama jest kratą dystrybutywną.


}}
:; +
::  Jeśli <math>\displaystyle L</math> jest kratą dystrybutywną, to <math>\displaystyle L^{op}</math> też.


{{dowod|[Uzupelnij]||
:; +
::  W dowolnej kracie <math>\displaystyle L</math> dopełnienie filtra pierwszego jest
ideałem.


Pokażemy, że </math>(1) (2)<math>. Niech wspólny element dwóch klas </math>[x]_R<math> oraz
:; +
</math>[y]_R<math> nazywa się </math>z<math>. Ze względu na pełną symetrię tezy wystarczy pokazać, że
:: Każdy ultrafiltr w algebrze Boole'a jest pierwszy.
</math>[x]_R  [y]_R<math>. Niech zatem </math>p [x]_R<math>. Mamy więc </math>(x,p)  R<math>. Z
założenia jest również
</math>(y,z)  R<math> oraz </math>(x,z)  R<math>. Z symetrii otrzymujemy </math>(z,x)
R<math>.
Zatem </math>(y,z)  R<math> i </math>(z,x)  R<math> i </math>(x,p)  R<math>.
Natychmiast z przechodniości otrzymujemy, że </math>(y,p)  R<math>.\\
Pokażemy, że </math>(2) (3)<math>. Ze zwrotności mamy, że
</math>y [y]_R<math> co z założenia </math>(2)<math> daje </math>y [x]_R<math> a to tłumaczy
się na </math>(x,y)  R<math>.
Pokażemy, że </math>(3) (1)<math>.
Wystarczy pokazać, że wspólnym elementem klas </math>[x]_R<math> oraz </math>[y]_R<math>
jest </math>y<math>. Dla pierwszej z nich wynika to z założenia </math>(3)<math> a dla
drugiej ze zwrotności </math>R<math>.
}}


W następnym twierdzeniu zobaczymy jak rodzina relacji
:; -
równoważności jest odporna na przecinanie. Pokażemy mianowicie, że przecięcie
::  Każdy filtr pierwszy w kracie dystrybutywnej jest
dowolnej liczby relacji równoważności jest nadal relacją równoważności.
ultrafiltrem.


{{twierdzenie|[Uzupelnij]||
:; +
Niech będzie pewną rodziną
:: Filtr otoczeń otwartych dowolnego punktu w przestrzeni
(zbiorem) relacji równoważności o tym samym polu </math>X<math>. Mamy że:
topologicznej jest filtrem właściwym.


# jest relacją równoważności o polu </math>X<math>.
:; +
:: Filtr otoczeń otwartych dowolnego punktu w przestrzeni
topologicznej jest filtrem zupełnie pierwszym.


# </math>[x]_{  } <nowiki>=</nowiki> [x]_R : R
:; +
:: Filtr otoczeń otwartych dowolnego punktu w przestrzeni
topologicznej jest filtrem pierwszym.


}}
:; -
::  W dowolnej kracie <math>\displaystyle L</math>, jeśli <math>\displaystyle F</math> jest filtrem, zaś <math>\displaystyle I</math>
ideałem, oraz <math>\displaystyle F\cap I=\emptyset</math>, wtedy istnieje filtr pierwszy
<math>\displaystyle F'</math> taki, że <math>\displaystyle F'\supseteq F</math> i <math>\displaystyle F'\cap I=\emptyset</math>.


{{dowod|[Uzupelnij]||
:; +
::  W kratach dystrybutywnych ultrafiltry są pierwsze.


<math>(1)</math> Zwrotność <math>\bigcap \kappa </math> jest oczywista ponieważ <math>1_X </math> zawiera
:; -
się w każdej relacji rodziny <math>\kappa </math>. Symetria. Weźmy <math>(x,y)\in
::  W kratach dystrybutywnych filtry pierwsze są maksymalne.
\bigcap \kappa </math>. Dla każdej relacji <math>R\in\kappa</math> jest <math>(x,y)\in R
</math>. Z symetrii każdej <math>R</math> jest więc <math>(y,x)\in R </math> co daje <math>(y,x)\in
\bigcap \kappa </math>. Przechodniość. Niech <math>(x,y)\in \bigcap \kappa </math>
oraz <math>(y,z)\in \bigcap \kappa </math>. Dla każdej relacji <math>R\in\kappa</math>
jest więc <math>(x,y)\in R</math> i <math>(y,z)\in R</math>. Z przechodniości każdej
relacji <math>R</math> mamy, że <math>(x,z) \in R</math> co daje <math>(x,z)\in \bigcap \kappa
</math>.<br>
<math>(2)</math> Niech <math>y \in [x]_{ \bigcap \kappa }</math>. Mamy zatem, że
<math>(x,y) \in \bigcap \kappa</math> co daje <math>(x,y)\in R</math> dla każdej
relacji <math>R\in\kappa</math>. To zaś daje, że <math>y \in [x]_R</math> dla każdej <math>R \in \kappa</math> co
jest równoważne z <math>y\in\bigcap \left\{[x]_R : R\in \kappa\right\}\$.
}}


W szczególności przecięcie wszystkich relacji
:; +
równoważności o polu </math>X<math> daje </math>1_X<math>. Jest ona najsilniejszą
:: Każda przestrzeń realna jest <math>\displaystyle T_0</math>.
relacją równoważności. Najsłabszą jest </math>X^2<math>.


===Rozkłady zbiorów===
:; -
::  Każda przestrzeń <math>\displaystyle T_0</math> jest realna.


\begindefn
:; -
Niech </math>X <math>. Rodzinę
:: Każda przestrzeń <math>\displaystyle T_1</math> jest realna.
</math>r  {P} ( {P} (X))<math> nazywamy rozkładem zbioru </math>X<math> gdy


# </math>_{C r}  C  <math>
:; -
:: Przestrzenie realne są przestrzeniami Hausdorffa.


# </math> r <nowiki>=</nowiki>X<math>
:; +
::  Dziedziny ciągłe w topologii Scotta są realne.


# </math>(C r {0.1mm}  D  r {0.1mm}  C  D ){0.1mm}  C D <nowiki>=</nowiki><math>
:; +
:: W porządku specjalizacji przestrzeni realnej istnieją
suprema wszystkich zbiorów skierowanych.


\enddefn 
:; -
::  Funktor <math>\displaystyle \Omega\colon \mathbf{Top}\to\mathbf{Frm}^{op}</math>
jest prawym sprzężeniem do funktora
<math>\displaystyle \mathrm{pt}\colon\mathbf{Frm}^{op}\to\mathbf{Top}</math>.


{{lemat|[Uzupelnij]||
:; +
Dla relacji równoważności </math>R<math> o polu </math>X<math> zbiór </math>X/R<math> jest rozkładem
::  Dla dowolnej topologii <math>\displaystyle X</math> przestrzeń
</math>X<math>. }}
<math>\displaystyle \mathrm{pt}(\Omega(X))</math> jest przestrzenią <math>\displaystyle T_0</math>.


{{dowod|[Uzupelnij]||
:; +
::  Dla dowolnej topologii realnej <math>\displaystyle X</math> przestrzeń
<math>\displaystyle \mathrm{pt}(\Omega(X))</math> jest homeomorficzna z <math>\displaystyle X</math>.


</math>(1)<math> Każda klasa jest niepusta bo zawiera element, który ją
:; -
wyznacza.
::  Dla dowolnej topologii <math>\displaystyle X</math> przestrzeń
</math>(2) X/R  X<math> bo każda klasa jest podzbiorem
<math>\displaystyle \mathrm{pt}(\Omega(X))</math> jest przestrzenią Hausdorffa.
</math>X<math>. Odwrotnie każdy </math>x  [x]_R  X/R<math>.
</math>(3)<math> Dwie klasy gdy są rożne muszą być rozłączne co udowodniliśmy
w twierdzeniu [[##thm:rownowaznosc|Uzupelnic thm:rownowaznosc|]].


}}
:; +
::  Jeśli krata <math>\displaystyle L</math> jest przestrzenną ramą, to topologia
<math>\displaystyle \mathrm{pt}(L)</math> jest realna.
; Pyt.7
:
:; +
::  Dla dowolnej kategorii <math>\displaystyle \mathbf{C}</math> kategoria
<math>\displaystyle [\mathbf{C}^{op},\mathbf{Set}]</math> jest kartezjańsko zamknięta,
zupełna i kozupełna.


\begindefn Niech </math>r<math> będzie rozkładem zbioru </math>X<math>. Definiujemy relacje </math>R_r
:; +
X  X<math> następująco:
:: Funktor Yonedy zachowuje izomorfizmy.


</math></center>(x,y) R_r  wtw  _{C r}  x  C  {0.1mm}    y C
:; +
<center><math>
:: Funktor Yonedy odzwierciedla retrakcje.


\enddefn  
:; +
:: Funktor Yonedy jest reprezentowalny.


{{lemat|[Uzupelnij]||
:; -
Dla rozkładu </math>r {P} ( {P}
:: Każde dwa funktory reprezentowalne są izomorficzne.
(X))<math> relacja </math>R_r<math> jest:


# równoważnością
:; +
::  Kontrawariantny funktor potęgowy jest reprezentowalny.


# </math>X/{R_r} <nowiki>=</nowiki> r<math>
:; -
::  Para <math>\displaystyle (\mathbb{N},+),0)</math> jest reprezentacją funktora
zapominania <math>\displaystyle U\colon\mathbf{Mon}\to\mathbf{Set}</math>.


}}
:; +
::  Każde dwie reprezentacje funktora <math>\displaystyle F\colon
\mathbf{C}^{op}</math> (gdzie <math>\displaystyle \mathbf{C}</math> jest dowolną lokalnie małą
kategorią) są izomorficzne.


{{dowod|[Uzupelnij]||
:; -
::  Każdy funktor typu <math>\displaystyle \mathbf{C}^{op}\to \mathbf{Set}</math> dla
lokalnie małej kategorii <math>\displaystyle \mathbf{C}</math> jest reprezentowalny.


</math>(1)<math> Relacja </math>R_r<math> jest zwrotna każdy bowiem </math>x X<math> musi leżeć w pewnym zbiorze
:; +
</math>C<math> rozkładu </math>r<math>. Symetria </math>R_r<math> nie wymaga dowodu. Przechodniość </math>R_r<math>. Niech </math>(x,y)
::  Jeśli <math>\displaystyle \mathcal{Y}(A)(X)\cong\mathcal{Y}(A)(Y)</math>, to
R_r<math> i </math>(y,z) R_r<math>. Istnieją zatem dwa zbiory </math>C<math> i </math>D<math> rozkładu </math>r<math> takie,
<math>\displaystyle X\cong Y</math> dla dowolnych obiektów <math>\displaystyle X,Y</math> lokalnie małej kategorii
że </math>x,y  C<math> oraz </math>y,z  D<math>. Przecięcie </math>C<math> i </math>D<math> jest więc niepuste zatem
<math>\displaystyle \mathbf{C}</math>.
</math>C<nowiki>=</nowiki>D<math> co daje tezę </math>(x,z)  R_r<math>.\\
</math>(2)<math> Inkluzja w prawo . Niech </math>C  X/{R_r}<math>. Klasa
</math>C<math> jest zatem wyznaczona przez pewien element </math>x<math> taki, że </math>C<nowiki>=</nowiki> [x]_{R_r}<math>.
Niech </math>D r<math> będzie zbiorem rozkładu </math>r<math> do którego należy </math>x<math>.
Łatwo wykazać, że </math>C<nowiki>=</nowiki>D<math>. Inkluzja w lewo .
Niech </math>C r<math>. </math>C<math> jest niepusty wiec istnieje </math>x  C<math>. Klasa
</math>[x]_{R_r} <nowiki>=</nowiki>C<math>.
}}


\beginCwiczenie
:; +
Niech </math>X<math> będzie niepustym zbiorem, oraz niech </math>Y X<math>. Zdefiniujemy relację </math>R  {P}(X)  {P}(X)<math> następująco:
::  Jeśli <math>\displaystyle \mathcal{Y}(X)(A)\cong\mathcal{Y}(Y)(A)</math>, to
dla dowolnych zbiorów </math>A,B  X<math> mamy
<math>\displaystyle X\cong Y</math> dla dowolnych obiektów <math>\displaystyle X,Y</math> lokalnie małej kategorii
<math>\displaystyle \mathbf{C}</math>.
; Pyt.8
:
:; +
::  Obiekt końcowy jest stożkiem nad pustym diagramem.


</math></center>(A,B) R  A{.}{} B Y.
:; +
<center><math>
:: Obiekt końcowy jest granicą pustego diagramu.


(</math>{.}{}<math> oznacza różnicę symetryczną zbiorów, czyli </math>A{.}{} B <nowiki>=</nowiki> (A B)
:; -
(B A)<math>) Udowodnij, że relacja </math>R<math> jest relacją równoważności.  
:: Obiekt początkowy jest granicą pustego diagramu.


\textbf{Wskazówka:  }
:; +
Najtrudniej jest pokazać przechodniość. Udowodnij, że </math>A {.}{} C     (B{.}{} C)  (A{.}{} B)<math>. Dobrym punktem wyjścia
::  Dowolny diagram w kategorii zupełniej <math>\displaystyle \mathbf{C}</math>
jest naszkicowanie wszystkich przecięć zbiorów </math>A,B,C<math>.
posiada granicę.


\textbf{Rozwiązanie: }Pokażemy po kolei zwrotność, przechodniość i symetryczność.
:; +
::  Istnieje kategoria kozupełna <math>\displaystyle \mathbf{C}</math>, w której nie ma
obiektu końcowego.


# Dla każdego </math>A X<math> mamy </math>A{.}{} A<nowiki>=</nowiki>  Y<math>, a więc relacja </math>R<math> jest zwrotna.
:; +
::  Produkt jest granicą diagramu nad kategorią dyskretną
(tzn. produkt w <math>\displaystyle \mathbf{C}</math> jest granicą funktora
<math>\displaystyle \mathbf{J}\to\mathbf{C}</math>, gdzie <math>\displaystyle \mathbf{J}</math> jest kategorią
dyskretną.


# Ponieważ dla dowolnych zbiorów </math>A{.}{} B<nowiki>=</nowiki> B{.}{} A<math> to </math>(A,B) R<math> wtedy i tylko wtedy gdy </math>(B,A) R<math>. Wobec tego relacja </math>R<math> jest symetryczna.
:; +
::  Istnieje kategoria, w której koprodukt w <math>\displaystyle \mathbf{Set}</math> jest
produktem.


# Weźmy zbiory </math>A,B,C X<math>, takie że </math>(A,B), (B,C)  R<math>. Wtedy
:; -
\beginalign*
:: Ekwalizator jest granicą diagramu, którego dziedziną jest
A \frac{.}{} C= (A\setminus C)  \cup (C\setminus A) =\\
kategoria, w której są dokładnie <math>\displaystyle 2</math> strzałki.
(((A\cap B) \cup (A\setminus B))\setminus C)  \cup    (((C\cap B) \cup (C\setminus B))\setminus A) =\\
((A\cap B)\setminus C) \cup ((A\setminus B)\setminus C) \cup
((C\cap B)\setminus A) \cup ((C\setminus B)\setminus A) \subset\\
(B\setminus C) \cup (A\setminus B) \cup (B\setminus A) \cup (C\setminus B)=\\
(B\frac{.}{} C) \cup (A\frac{.}{} B).
\endalign*
Ponieważ z definicji relacji </math>R<math> mamy  </math>(B{.}{} C)  Y<math> oraz</math> (A{.}{} B) Y<math> to ich suma też jest podzbiorem </math>Y<math>
i konsekwencji również </math>A{.}{} C  Y<math>. Oznacza to, że </math>(A,C) R<math>, a więc relacja </math>R<math> jest przechodnia.


\endCwiczenie
:; +
::  Ekwalizator jest granicą diagramu, którego dziedziną jest
kategoria, w której są dokładnie <math>\displaystyle 4</math> strzałki.


\beginCwiczenie
:; +
Udowodnij, że dla relacji równoważności </math>R,S<math> na zbiorze </math>X<math>, relacja </math>R S<math> jest relacją równoważności
::  Ekwalizator jest granicą diagramu, którego dziedziną jest
wtedy i tylko wtedy gdy
kategoria, w której są dokładnie <math>\displaystyle 2</math> strzałki równoległe.


</math></center>
:; -
_{x X}( [x]_R [x]_S  [x]_R  [x]_S).
:: Jeśli w danej kategorii istnieją wszystkie pulbaki i co
<center><math>
najmniej jeden obiekt końcowy, to w tej kategorii istnieją
wszystkie granice.


Podaj przykłady relacji równoważności </math>R,S<math> takich, że </math>R S<math> jest relacją
:; +
równoważności oraz </math>R S<math> i </math>S R<math>.  
::  Jeśli w danej kategorii istnieją wszystkie pulbaki i co
najmniej jeden obiekt końcowy, to w tej kategorii istnieją
wszystkie granice skończone.


\textbf{Wskazówka:  }
:; +
Przyjrzyj się dokładnie rodzinie zbiorów </math>A<nowiki>=</nowiki>[x]_R  [x]_S : x X<math>.
::  Jeśli w posecie <math>\displaystyle (P,\leq)</math> istnieją wszystkie granice, to
poset dualny <math>\displaystyle (P,\geq)</math> jest kratą zupełną.


\textbf{Rozwiązanie: }Zaczniemy od pokazania, że formuła </math>[[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]]<math> implikuje, że relacja
:; -
</math>R S<math> jest relacją równoważności. Pokażemy, że rodzina </math>A<nowiki>=</nowiki>[x]_R [x]_S :
::  Jeśli w posecie <math>\displaystyle (P,\leq)</math> istnieją wszystkie granice, to
x X<math> tworzy rozkład zbioru </math>X<math>. Oczywiście, dla każdego elementu </math>x X<math> mamy
poset dualny <math>\displaystyle (P,\geq)</math> jest algebrą Heytinga.
</math>[x]_R  [x]_S  <math> oraz </math>x [x]_R  [x]_S<math>. Wystarczy więc
pokazać, że zbiory w rodzinie </math>A<math> są rozłączne. Weźmy dowolne dwa elementy rodziny
</math>A<math> i przypuśćmy, że ich przecięcie jest niepuste. Niech to będą zbiory odpowiadające
elementom </math>x,y X<math> a więc </math>[x]_R  [x]_S<math> oraz </math>[y]_R  [y]_S<math>. Skoro te
zbiory mają niepuste przecięcie to istnieje </math>z ([x]_R  [x]_S) ([y]_R
[y]_S)<math>. Ponieważ </math>z [x]_R  [x]_S<math> to </math>z [x]_R  z  [x]_S<math> co jest
równoważne </math>x [z]_R  x  [z]_S<math>. Podobne rozumowanie dla </math>z<math> daje </math>y
[z]_R  y  [z]_S<math>. Wobec czego dostajemy </math>x,y  [z]_R  [z]_S<math> ponieważ
jednak zgodnie z formułą [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] jedna z tych klas jest nadzbiorem
drugiej, to </math>x,y  [z]_R<math> lub  </math>x,y  [z]_S<math>. W przypadku, gdy </math>[z]_R
[z]_S<math> dostajemy również z [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] </math>[z]_R<nowiki>=</nowiki>[x]_R [x]_S<math> oraz
</math>[z]_R<nowiki>=</nowiki>[y]_R [y]_S<math> wobec czego otrzymujemy </math>[x]_R  [x]_S <nowiki>=</nowiki>[z]_R<nowiki>=</nowiki>[y]_R
[y]_S<math>. Drugi przypadek jest analogiczny. Wobec czego rodzina </math>A<math> jest rozkładem
zbioru </math>X<math>. Wystarczy teraz przekonać się że </math>(a,b) R S<math> wtedy i tylko wtedy,
gdy </math>a  [b]_R  [b]_S<math>, aby udowodnić, że jest to rzeczywiście rozkład
generowany przez relację </math>R S<math>. Weźmy dowolne </math>a,b  X<math> wtedy
\beginalign*
(a,b)\in R\cup S \Leftrightarrow (a,b)\in R \vee (a,b)\in S \Leftrightarrow a\in[b]_R \vee a\in [b]_S \Leftrightarrow a \in [b]_R \cup [b]_S.
\endalign*


Pokażemy teraz, że jeśli </math>R S<math> jest relacją równoważności to musi być spełniona
:; +
formuła [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]]. Dla dowodu nie wprost przypuśćmy, że nie jest
::  Każda mała kozupełna kategoria jest preporządkiem.
spełniona. Oznacza to, że istnieje element </math>x X<math> dla którego </math>[x]_R
[x]_S<math> oraz </math>[x]_R [x]_S<math>. Wobec tego istnieje </math>y [x]_R
[x]_S<math> oraz </math>z  [x]_S  [x]_R<math>. Oznacza to, że </math>(y,x) R S<math>
oraz </math>(x,z) S R<math>. Skoro </math>R S<math> jest relacją równoważności to </math>(z,y)
R S<math>. Przypuśćmy, że </math>(z,y) R<math>. Wtedy </math>(z,y),(y,x) R<math> wobec czego
</math>(z,x) R<math> co jest sprzeczne z tym że </math>(x,z) S R<math> ponieważ relacja </math>R<math>
jest symetryczna. Analogiczną sprzeczność otrzymujemy dla </math>(z,x) S<math>. Obie
możliwości prowadzą do sprzeczności, a więc formuła [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] musi być
spełniona.


Na koniec podajemy przykład relacji równoważności, równoważności </math>R,S<math> takich, że
:; +
</math>R S<math> jest relacją równoważności oraz </math>R S<math> i </math>S R<math>. Polem
:: Każda mała zupełna kategoria jest preporządkiem.
relacji będzie zbiór </math>X<nowiki>=</nowiki>0,1,2,3<math>. Relacje </math>R,S<math> określimy poprzez wyznaczane
przez nie rozkłady odpowiednio </math>r,s<math>:
\beginalign*
r=\{\{0\},\{1\}, \{2,3\}\}\\
s=\{\{0,1\}, \{2\},\{3\}\}.
\endalign*
Łatwo sprawdzić, że </math>R S<math> i </math>S R<math>, gdyż </math>(2,3) R S<math>
oraz </math>(0,1) S R<math>. Z rozkładów </math>r,s<math> łatwo wynika, że formuła
[[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] jest prawdziwa dla tych relacji, wobec czego </math>R S<math> jest
relacją równoważności. Wyznaczany przez nią rozkład to </math>0,1,2,3<math>.
\endCwiczenie
===Domykanie relacji===


W praktyce matematycznej często potrzebne jest rozważanie domknięć
:; -
relacji ze względu na wiele przeróżnych własności. W podrozdziale tym dokonamy
:: Każda lokalnie mała kozupełna kategoria jest preporządkiem.
charakteryzacji domknięć. Pokażemy między innymi kiedy takie domykanie jest możliwe.


\begindefn
:; -
::  Każda lokalnie mała zupełna kategoria jest preporządkiem.


Niech  będzie rodziną relacji o polu
:; -
</math>X<math>, czyli niech </math> {P} ( {P} (X^2))<math>.
:: Kategoria zbiorów skończonych i funkcji jest zupełna.
Rodzina  jest zamknięta na przecięcia gdy


# </math>X^2  <math>
:; +
::  Kategoria <math>\displaystyle \mathbf{Dcpo}</math> jest zupełna.


# jeżeli </math>  ' <math> to  </math>
:; +
'  <math>
:: Jeśli kategoria <math>\displaystyle \mathbf{C}</math> posiada pulbaki i obiekt
końcowy, to posiada też produkty.


\enddefn 
:; -
::  Jeśli kategoria <math>\displaystyle \mathbf{C}</math> posiada pulbaki i obiekt
końcowy, to posiada też koprodukty.


Poniżej podamy definicję domknięcia relacji w pewnej klasie (zbiorze) relacji.
:; +
Definiujemy intuicyjnie najmniejszą relacje zawierającą daną należącą do klasy.
:: Funktor Yonedy jest ciągły.


\begindefn
:; -
Relacja </math>S  X^2<math> jest domknięciem relacji </math>R  X^2<math> w klasie (zbiorze)
::  Funktor Yonedy zachowuje dowolne kogranice.
relacji  gdy:
; Pyt.9
:
:; +
::  Funktor podnoszenia do potęgi <math>\displaystyle [X,-]\colon
\mathbf{C}\to\mathbf{C}</math>, <math>\displaystyle X\in\mathbf{C}_0</math> w kartezjańsko
zamkniętej kategorii <math>\displaystyle \mathbf{C}</math> jest prawym sprzężeniem.


# </math>R S<math>
:; +
:: Istnieją funktory posiadające zarówno lewe, jak i prawe
sprzężenia.


# </math>S <math>
:; -
:: Funktor, który posiada lewe sprzężenie nie może posiadać
prawego sprzężenia.


# dla każdej relacji </math>T<math> jeżeli </math>R T<math> oraz </math>T  <math> to </math>S  T<math>
:; -
:: Funktory zapominania zawsze posiadają lewe sprzężenie.


\enddefn  
:; -
:: Funktory wolne są prawym sprzężeniem do funktorów
zapominania.


{{lemat|[Uzupelnij]||
:; +
::  Funktor <math>\displaystyle \mathrm{List}\colon \mathbf{Set}\to\mathbf{Mon}</math>
jest funktorem wolnym.


Domknięcie relacji (w dowolnej klasie) jeżeli istnieje to jest jedyne. }}
:; -
::  Nie istnieje lewe sprzężenie funktora zapominania
<math>\displaystyle \mathbf{Top}\to\mathbf{Set}</math>.


{{dowod|[Uzupelnij]||
:; -
::  Operacja przeciwobrazu funkcji jest lewym sprzężeniem operacji
obrazu funkcji.


Gdyby istniały dwa domknięcia pewnej relacji to ze względu na warunek </math>(3)<math> wzajemnie
:; +
by się zawierały.
::  Koprodukt jest lewym sprzężeniem lewego sprzężenia
}}
produktu.


{{twierdzenie|[Uzupelnij]||
:; -
Następujące warunki są równoważne:
::  Każdy funktor będący lewym sprzężeniem jest wierny.


# Klasa relacji jest domknięta na przecięcia.
:; -
:: Operacja brania wnętrza zbioru w przestrzeni
topologicznej <math>\displaystyle X</math> jest lewym sprzężeniem inkluzji zbiorów
otwartych w podzbiory <math>\displaystyle X</math>.
; Pyt.10
:
:; +
::  Jeśli funktor jest równoważnością kategorii, to posiada
lewe i prawe sprzężenie.


# Każda relacja ma domknięcie w klasie relacji .
:; +
::  Jeśli każdy komponent kojedności sprzężenia jest
retrakcją, to prawe sprzężenie jest funktorem wiernym.


}}
:; -
::  Jeśli każdy komponent kojedności sprzężenia jest
epimorfizmem, to prawe sprzężenie jest funktorem pełnym.


{{dowod|[Uzupelnij]||
:; +
::  Jeśli prawe sprzężenie jest funktorem pełnym i wiernym, to
kojedność sprzężenia jest izomorfizmem.


</math>(1)  (2)<math>. Niech </math>R<math> będzie relacją. Utwórzmy zbiór relacji </math> '<math>
:; -
jako </math> S{P} (X^2) : R S {0.1mm}  S . Takie <math>\alpha '</math> nie jest
::  Jeśli prawe sprzężenie jest funktorem pełnym i wiernym, to
puste bowiem relacja totalna <math>X^2</math> należy do <math>\alpha '</math>. Pokażmy, że <math>\bigcap \alpha
jedność sprzężenia jest izomorfizmem.
'</math> jest domknięciem <math>R</math> w <math>\alpha</math>. Istotnie <math>R\subset \bigcap \alpha '</math>. Z założenia
mamy też <math>\bigcap \alpha ' \in \alpha</math>. Minimalność <math>\bigcap \alpha '</math> stwierdzamy
przez: niech <math>R \subset S'</math> takie że <math>S' \in \alpha</math>. Takie <math>S'</math> musi leżeć w
zbiorze <math>\alpha '</math> jest
więc <math>\bigcap \alpha ' \subset S' </math>.<br>
<math>(2) \rightarrow (1)</math>. Po pierwsze <math>X^2</math> leży w zbiorze <math>\alpha</math> bo wystarczy domknąć
<math>X^2</math>. Niech <math>\alpha '</math> będzie niepustym podzbiorem <math>\alpha</math>. Niech <math>S_0</math> będzie
domknięciem <math>\bigcap \alpha '</math> w <math>\alpha</math>. Wiemy, że dla dowolnej relacji <math>S'</math>  o ile
<math>\bigcap \alpha ' \subset S'</math> i <math>S'\in \alpha</math> to <math>S_0 \subset S'</math>. Połóżmy za <math>S'</math>
dowolny element z <math>\alpha '</math>. Założenia implikacji pozostają automatycznie spełnione,
jest więc tak, że <math>S_0 \subset S'</math> dla dowolnej <math>S'</math> wyjętej z <math>\alpha '</math>. W takim
razie <math>S_0 \subset \bigcap \alpha '</math>. Ponieważ mamy też <math>  \bigcap \alpha '\subset
S_0</math> bo <math>S_0</math> było domknięciem jest więc <math>\bigcap \alpha '= S_0</math> a to oznacza, że
<math>S_0 \in \alpha</math>.
}}


Pokazać jak wyglądają domknięcia w klasie relacji,
:; +
zwrotnych, symetrycznych i przechodnich.
::  Prawe sprzężenia zachowują granice, zaś lewe - kogranice.


Pokazać stosując twierdzenie [[##thm:domkniecie|Uzupelnic thm:domkniecie|]], że nie istnieje domknięcie spójne
:; -
ani antysymetryczne. (Relacja <math>R</math> jest spójna gdy <math>\forall x,y (x,y) \in R \hspace*{0.1mm} \vee
:: Lewe sprzężenia zachowują granice, zaś prawe - kogranice.
(y,x)\in R</math>. Relacja <math>R</math> jest antysymetryczna gdy z faktu, że <math>(x,y) \in R</math> oraz
<math>(y,x) \in R</math> da się pokazać, że <math>x=y</math>)


'''Rozwiązanie: '''Ćwiczenie jest elementarne.
:; +
::  Istnieją prawe sprzężenia, które zachowują kogranice oraz
lewe sprzężenia, które zachowują granice.


# Pokażemy, że dla każdej relacji <math>R\in X^2</math> jej domknięcie w klasie relacji zwrotnych na <math>X</math> to <math>R\cup 1_X</math>.
:; -
Pokażemy po kolei, że spełnia warunki domknięcia.
::  Jeśli funktor zachowuje granice, to ma lewe sprzężenie.


## <math>R \subset R \cup 1_X</math>
:; +
::  Jeśli funktor między posetami zachowuje granice, to ma
lewe sprzężenie.


## <math>1_X \subset R \cup 1_X</math>, a więc jest zwrotna
:; +
::  Każda funkcja monotoniczna między kratami zupełnymi, posiadająca lewe
sprzężenie, zachowuje dowolne infima.


## weźmy dowolną zwrotną relację <math>T\supset R</math>. Ponieważ <math>T</math> jest zwrotna to <math>T\supset 1_X</math>, a więc <math>T\supset R \cup 1_X</math>.
:; +
::  Prawe sprzężenie między posetami jest surjekcją wtedy i
tylko wtedy, gdy jego lewe sprzężenie jest injekcją.


# Pokażemy, że dla każdej relacji <math>R\in X^2</math> jej domknięcie w klasie relacji symetrycznych na <math>X</math> to <math>R\cup R^{-1}</math>.
:; -
Pokażemy po kolei, że spełnia warunki domknięcia.
::  Prawe sprzężenie między posetami jest injekcją wtedy i
tylko wtedy, gdy jego lewe sprzężenie jest surjekcją.


## <math>R \subset R \cup R^{-1}</math>
:; +
::  Każde dwa prawe sprzężenia danego funktora są
izomorficzne.


## <math>(R \cup R^{-1})^{-1} = R^{-1} \cup (R^{-1})^{-1}= R^{-1} \cup R= R \cup R^{-1} </math>, a więc jest symetryczna
:; +
::  Każdy homomorfizm krat zupełnych posiada lewe i prawe
sprzężenie.


## weźmy dowolną symetryczną relację <math>T\supset R</math>. Ponieważ <math>T</math> jest symetryczna to
:; -
<math>T \supset T^{-1}</math>. Skoro <math>T \supset R</math> to <math>T^{-1} \supset R^{-1}</math>. Ponieważ <math>T \supset T^{-1}</math> to <math>T\supset R\cup R^{-1}</math>.
::  Każdy homomorfizm ram posiada lewe i prawe sprzężenie.


# Posługując się intuicyjnym pojęciem liczb naturalnych przedstawimy szkic konstrukcji przechodniego domknięcia,
:; -
pomimo że konstrukcja ta wyprzedza prezentowany materiał. Dla dowolnej liczby <math>n\in N \setminus\{0\}</math> przez <math>R^n</math>
:: Każdy homomorfizm algebr Boole'a posiada lewe i prawe
będziemy oznaczać <math>n</math>-krotne złożenie relacji <math>R</math> z sobą (czyli <math>R^1=R</math> oraz <math>R^{n+1}= R^n \circ R</math> dla <math>n>1</math>).
sprzężenie.
Zdefiniujmy rodzinę <math>\mathcal{R}</math> jako zbiór wszystkich skończonych wielokrotnych złożeń
relacji <math>R</math> z sobą, czyli <math>\mathcal{R}=\{r\subset X^2 : \exists_{n\in N} (n\neq 0
\wedge R^n=r)\}</math>. Do formalnego zdefiniowania rodziny <math>\mathcal{R}</math> potrzebne są pojęcia
liczb naturalnych, funkcji oraz definiowania przez indukcje, które zostaną
przedstawione w następnych rozdziałach. Pokażemy teraz, że domknięcie relacji <math>R</math> w
klasie relacji przechodnich na <math>X</math> to relacja <math>\bigcup \mathcal{R}</math>.
Pokażemy po kolei, że spełnia warunki domknięcia.


## <math>R=R^1 \subset \bigcup \mathcal{R}</math>
:; +
::  Każdy homomorfizm zupełnych algebr Boole'a posiada prawe
i lewe sprzężenie.


## Aby pokazać, że relacja <math>\bigcup \mathcal{R}</math> jest przechodnia weźmy dowolne dwie pary <math>(a,b),(b,c) \in \mathcal{R}</math>.
:; -
Wtedy muszą istnieć liczby <math>n,m \in N</math> takie, że <math>(a,b)\in R^n</math> oraz <math>(b,c)\in R^m</math>. Wobec tego <math>(a,c)\in R^m \circ R^n</math>.
::  W parze e-p między posetami, projekcja jest lewym
Z łączności składania relacji wynika, że <math>R^m \circ R^n= R^{m+n}</math>. Wobec tego <math>(a,c)\in R^{m+n} \subset \bigcup \mathcal{R}</math>.
sprzężeniem zanurzenia.


## Weźmy dowolną przechodnią relację <math>T</math> taką, że <math>R\subset T</math> pokażemy indukcyjnie, że dla każdego
:; +
<math>n\in N\setminus \{0\}</math> mamy <math>R^n\subset T</math>.
::  W parze e-p między posetami, zanurzenie zachowuje dowolne
suprema.


### Baza indukcji. Dla <math>n=1</math> mamy <math>R^1=R</math> a więc z założenia <math>R^1\subset T</math>.
:; +
::  W parze e-p między posetami, zanurzenie i projekcja
wzajemnie się wyznaczają.
; Pyt.11
:
:; +
::  Każde sprzężenie <math>\displaystyle F\dashv G</math> indukuje monadę
<math>\displaystyle (GF,\eta,G\eta_F)</math>.


### Krok indukcyjny. Weźmy dowolne <math>n\in N\setminus \{0,1\}</math> i przypuśćmy, że dla każdego <math>0<m<n</math>
:; +
zachodzi <math>R^m\subset T</math>. Weźmy dowolną parę <math>(a,c)\in R^n</math>. Ponieważ <math>n>1</math> to <math>R^n= R^{n-1} \circ R</math>.
::  Każde sprzężenie <math>\displaystyle F\dashv G</math> indukuje komonadę
Oznacza to, że istnieje element <math>b\in X</math> taki, że <math>(a,b)\in R</math> oraz <math>(b,c)\in R^{n-1}</math>. Z założenia
<math>\displaystyle (FG,\varepsilon,F\eta_G)</math>.
indukcyjnego wynika, że <math>(a,b)\in T</math> oraz <math>(b,c)\in T</math>. Ponieważ <math>T</math> jest przechodnia to <math>(a,c)\in T</math>.
Wobec dowolności wyboru pary <math>(a,c)</math> otrzymujemy <math>R^n \subset T</math>.


Skoro dla każdego <math>n\in N\setminus \{0\}</math> mamy <math>R^n \subset T</math> to również <math>\bigcup \mathcal{R} \subset T</math>.
:; -
::  Dowolna monada jest monadą indukowaną przez dokładnie
jedno sprzężenie.


Pokażemy teraz że istnieje zbiór <math>X</math> taki, że klasa relacji spójnych na zbiorze <math>X</math> i
:; +
klasa relacji symetrycznych na zbiorze <math>X</math> nie są domknięte na przecięcia. W obliczu
::  Dowolna monada jest monadą indukowaną przez sprzężenie.
twierdzenia [[##thm:domkniecie|Uzupelnic thm:domkniecie|]] będzie to oznaczało, że nie wszystkie relacje mają
domknięcia w tych klasach. Niech <math>X=\{0,1\}</math>.


# Relacje <math>\{(0,1),(0,0),(1,1)\}, \{(1,0),(0,0),(1,1)\}</math> są spójne na <math>X</math>, a ich
:; +
przecięcie czyli zbiór <math>\{(0,0),(1,1)\}</math> nie jest.
::  Każda monada na preporządku jest operacją idempotentną.


# Relacja <math>X^2</math> nie jest antysymetryczna, a więc klasa relacji antysymetrycznych na <math>X</math>
:; -
nie jest domknięta na przecięcia.
::  Funktor zapominania <math>\displaystyle \mathbf{Mon}\to\mathbf{Set}</math> jest
częścią sprzężenia, którego algebry monady indukowanej tworzą
kategorię równoważną z <math>\displaystyle \mathbf{Set}</math>.


Dla relacji <math>R</math> niech <math>R^\alpha</math>, <math>R^\beta</math>, <math>R^\gamma</math> oznaczają odpowiednio
:; +
zwrotne, symetryczne, przechodnie domknięcie relacji <math>R</math>. Czy
::  Funktor zapominania <math>\displaystyle \mathbf{Mon}\to\mathbf{Set}</math> jest
prawdą jest że:
częścią sprzężenia, którego algebry monady indukowanej tworzą
kategorię równoważną z <math>\displaystyle \mathbf{Mon}</math>.


# dla dowolnej relacji <math>R</math> relacja
:; +
<math>((R^\alpha)^\beta)^\gamma</math> jest relacją równoważności
::  Zwarte przestrzenie Hausdorffa i funkcje ciągłę tworzą kategorię algebraiczną.


# dla dowolnej relacji <math>R</math> zachodzi
:; -
::  Zupełne algebry Boole'a i homomorfizmy tych algebr tworzą
kategorię algebraiczną.


<center><math>((R^\alpha)^\beta)^\gamma =((R^\gamma)^\beta)^\alpha
:; +
</math></center>
::  Kategoria grup jest równoważna kategorii algebr dla
pewnej monady.


W każdym z powyższych przypadków proszę podać dowód lub
:; +
kontrprzykład.
::  Suma mnogościowa <math>\displaystyle \bigcup</math> jest mnożeniem pewnej monady.


'''Rozwiązanie: '''
:; +
::  Operacja dodawania nowego elementu najmniejszego do
częściowego porządku indukuje monadę nad <math>\displaystyle \mathbf{Pos}</math>.
; Pyt.12
:
:; -
::  Każda dziedzina ciągła posiada bazę przeliczalną.


# Zaczniemy od pokazania, że dowolne domknięcie relacji zwrotnej jest zwrotne. Rozważamy relacje na zbiorze <math>X</math>. Z definicji zwrotności mamy
:; -
<math>R</math> jest zwrotna wtedy i tylko wtedy gdy <math>R\supset 1_X</math>. W definicji domknięcia [[##defn:domkniecie|Uzupelnic defn:domkniecie|]] punkt pierwszy mówi, że jeśli <math>S</math> jest
:: Każdy element bazy dziedziny ciągłej jest zwarty.
domknięciem to <math>S\supset R</math>. Wobec tego konieczne jest aby <math>S\supset 1_X</math>. Zwróćmy uwagę, że powyższy argument działa dla dowolnych klas rodzin relacji
domkniętych na przecięcia. Stąd otrzymujemy, że symetryczne domknięcie relacji zwrotnej jest zwrotne,
i przechodnie domknięcie relacji zwrotnej jest zwrotne. Ponieważ relacja <math>R^\alpha</math> jest zwrotna, to również zwrotna musi być <math>((R^\alpha)^\beta)^\gamma</math>.
Pokażemy teraz, że przechodnie domknięcie relacji symetrycznej jest symetryczne. Wykorzystamy charakteryzację domknięcia przechodniego z ćwiczenia
[[##ex:charakteryzacjeDomkniec|Uzupelnic ex:charakteryzacjeDomkniec|]]. Można łatwo pokazać indukcyjnie, że dla dowolnego <math>n\inN\setminus\{0\}</math> mamy <math>(R^n)^{-1}=(R^{-1})^n</math>.
Dla relacji symetrycznych dostajemy więc <math>(R^n)^{-1}=R^n</math>. Wobec tego mamy


<center><math>(\bigcup\{R^n:n\in N \setminus \{0\}\})^{-1} = \bigcup\{(R^n)^{-1}:n\in N \setminus \{0\}\}=
:; +
\bigcup\{R^n:n\in N \setminus \{0\}\}
:: Każda baza posetu algebraicznego zawiera wszystkie
</math></center>
elementy zwarte.


a więc przechodnie domknięcie relacji symetrycznej jest symetryczne. Oznacza to, że
:; +
relacja <math>((R^\alpha)^\beta)^\gamma</math> jest symetryczna. Wcześniej pokazaliśmy, że jest
::  Każdy poset skończony jest algebraiczny.
zwrotna. Ponieważ jest przechodnim domknięciem to jest też przechodnia. Wobec tego
jest relacją równoważności.


# Pokażemy relację <math>R</math> dla której relacja <math>((R^\gamma)^\beta)^\alpha</math> nie jest przechodnia. Ponieważ relacja <math>((R^\alpha)^\beta)^\gamma</math>
:; +
jest przechodnia, będzie to oznaczało że te relacje są różne. Niech <math>X=\{0,1,2\}</math> oraz <math>R=\{(0,2),(1,2)\}</math>. Relacja <math>R</math> jest przechodnia
::  Każdy poset skończony jest dcpo.
więc <math>R^\gamma=R</math> jej symetryczne domknięcie to <math>(R^\gamma)^\beta=\{(0,2),(2,0),(1,2),(2,1)\}</math>. I po zwrotnym domknięciu otrzymujemy
<math>((R^\gamma)^\beta)^\alpha=\{(0,2),(2,0),(1,2),(2,1),(0,0),(1,1),(2,2)\}</math>. Łatwo zauważyć, że otrzymana relacja nie jest przechodnia,
gdyż <math>(0,2),(2,1)\in ((R^\gamma)^\beta)^\alpha</math> podczas gdy <math>(0,1)\notin ((R^\gamma)^\beta)^\alpha</math>.


==Iloczyn kartezjański i podobne konstrukcje (''rozdział dla
:; +
dociekliwych)''==
::  Każda krata skończona jest dcpo.


W definicji [[##iloczyn_kartezjanski|Uzupelnic iloczyn_kartezjanski|]] zaprezentowanej w rozdziale
:; -
[[##section_iloczyn_kartezjanski|Uzupelnic section_iloczyn_kartezjanski|]] jest pewna nieścisłość. Konstrukcja iloczynu
::  Relacja aproksymacji na dowolnym posecie jest
kartezjańskiego odwołuje się do aksjomatu wyróżniania w wersji nieuprawomocnionej.
interpolatywna.
Konstrukcja którą zobaczą państwo w tym rozdziale usuwa tą poprzednią niedogodność.


{{twierdzenie|[Uzupelnij]||
:; +
::  Relacja aproksymacji na dowolnej dziedzinie Scotta jest
interpolatywna.


Dla dowolnych dwóch zbiorów <math>x</math> i <math>y</math> istnieje zbiór <math>x\times y</math> zawierający
:; -
wszystkie pary postaci <math>(w,z)</math> gdzie <math>w\in x</math> i <math>z\in y</math>.
::  Liczby naturalne są dcpo.
}}


{{dowod|[Uzupelnij]||
:; +
::  Liczby naturalne są posetem algebraicznym i bc-zupełnym.


Ustalmy dwa dowolne zbiory <math>x</math> i <math>y</math>. Jeśli <math>x=\emptyset</math> lub <math>y=\emptyset</math> to
:; +
<math>x\times y = \emptyset</math> istnieje na podstawie aksjomatu zbioru pustego. W przeciwnym
::  Każda rama jest dcpo.
przypadku <math>x\cup y</math> jest zbiorem jednoelementowym <math>\{z\}</math> to <math>x\times
y=\{\{\{z\}\}\}</math> istnieje na podstawie aksjomatu pary. W dalszej częsci dowodu
zakładamy że zbiory <math>x</math> i <math>y</math> są niepuste i że <math>x\cup y</math> ma więcej niż jeden element.
Na podstawie aksjomatu zbioru potęgowego, aksjomatu unii i aksjomatu wycinania
następujące zbiory istnieją:


A &<nowiki>=</nowiki>z{P}(x)|  w z <nowiki>=</nowiki>w, <br>
:; -
B &<nowiki>=</nowiki>z{P}(x y)|  w  v (w  v  z<nowiki>=</nowiki>v,w),<br>
:: Każda krata dystrybutywna jest dcpo.
C &<nowiki>=</nowiki>z{P}({P}(y))| v z<nowiki>=</nowiki>v<nowiki>=</nowiki>(v,v).


Nasze założenia gwarantują, że żaden z powyższych zbiorów nie jest pusty. Kontynuując
:; +
możemy stworzyć
::  Istnieje poset nieskończony, którego każdy element, który
nie jest maksymalny, jest zwarty.


D_0 &<nowiki>=</nowiki>z{P}(A B)|  w v w v
:; -
z<nowiki>=</nowiki>w,w,v<nowiki>=</nowiki>(w,v),
:: Zbiory domknięte w sensie Scotta na dowolnym posecie są domknięte ze względu
na dowolne suprema.


w którym to zbiorze mamy pewność, że <math>w</math> jest elementem <math>x</math>. Kontynuujemy definiując
:; +
::  Zbiory domknięte w sensie Scotta na dowolnym posecie skończonym są domknięte ze względu
na dowolne suprema.


D_0' &<nowiki>=</nowiki>z{P}(D_0 C)|  w  v w v
:; +
z<nowiki>=</nowiki>(w,v),(v,v),
::  Stożki górne w posecie <math>\displaystyle P</math> (tj. zbiory typu <math>\displaystyle \uparrow x</math> dla <math>\displaystyle x\in
P</math>) są zwarte w topologii Scotta.


gdzie mamy pewność, że <math>w</math> jest elementem <math>x</math>, a <math>v</math> elementem <math>y</math>, oraz
:; +
::  Każdy stożek dolny <math>\displaystyle \downarrow x</math> w dziedzinie ciągłej <math>\displaystyle P</math> wraz z
porządkiem z <math>\displaystyle P</math> obciętym do <math>\displaystyle \downarrow x</math> jest dziedziną ciągłą.


D_0" &<nowiki>=</nowiki>z{P}(D_0 C)|  w v w v
:; +
z<nowiki>=</nowiki>(w,v),(w,w ),
:: Topologia Scotta na dowolnym porządku jest <math>\displaystyle T_0</math>.


gdzie mamy pewność, że <math>w\in A\cap B</math>. Kończąc
:; +
::  Istnieją częściowe porządki dowolnej mocy, dla których
topologia Scotta jest <math>\displaystyle T_1</math>.


x y &<nowiki>=</nowiki>z D_0' |  w  v w v
:; +
z<nowiki>=</nowiki>(w,v) z D_0" | w z<nowiki>=</nowiki>(w,w).
:: Topologia Scotta na porządku jest <math>\displaystyle T_1</math> wtedy i tylko
wtedy, gdy częściowy porządek redukuje się do równości.


}}
:; +
::  Topologia Scotta na posecie posiadającym element
najmniejszy jest zwarta.


{{twierdzenie|[Uzupelnij]||
:; +
::  Topologia Scotta na dowolnej dziedzinie ciągłej jest
realna.


Jeśli <math>x,y</math> i <math>z</math> są zbiorami i <math>z\subseteq x\times y</math> to zbiorem jest również ogół
:; -
<math>v</math> takich, że istnieje <math>w</math> spełniające <math>(v,w)\in z</math>. Zbiór takich <math>v</math> oznaczamy
::  Topologia Scotta na dowolnym dcpo jest realna.
przez <math>\pi_1(z)</math> i nazywamy projekcją na pierwszą współrzędną.
}}


{{dowod|[Uzupelnij]||
:; +
::  Funkcja ciągła w sensie Scotta jest monotoniczna.


Zbiór <math>\pi_1(z)</math> istnieje na podstawie aksjomatów ZF i jest równy:
:; -
::  Każda funkcja ciągła w sensie Scotta na dowolnym posecie posiada punkt stały.


<center><math>\pi_1(z) = \bigcup\{w\in\bigcup z\,|\, \exists u\; w=\{u\}\}.
:; -
</math></center>
::  Każda funkcja ciągła w sensie Scotta na posecie
posiadającym element najmniejszy posiada punkt stały.


}}
:; +
::  Każda funkcja ciągła w sensie Scotta na dcpo
posiadającym element najmniejszy posiada najmniejszy punkt stały.


W tej chwili jesteśmy gotowi dowieść własność zapowiedzianą w Wykład. AKS Dla
:; +
dowolnej formuły <math>\varphi'</math> nie posiadającej zmiennych wolnych innych niż <math>z'</math> i
::  Każda funkcja monotoniczna na dcpo
<math>x_1'</math> następująca formuła jest prawdą
posiadającym element najmniejszy posiada punkt stały.


<center><math>\forall x_1' \forall x' \exists y' \forall z'\; z'\in y' \iff (z'\in x' \land
:; +
\varphi').
::  Porządek specjalizacji topologii Scotta na dziedzinie
</math></center>
ciągłej pokrywa się z porządkiem tejże dziedziny.


Aby dowieść tą własność ustalmy dowolną formułę <math>\varphi'</math> i dowolny zbiór <math>x_1'</math>.
:; +
Stosujemy aksjomat wyróżniania do <math>x=x\times \{x_1'\}</math>&nbsp;(który istnieje na mocy
::  Funkcje ciągłe w sensie Scotta zachowują suprema zbiorów
Twierdzenia&nbsp;[[##tw:produktistnieje|Uzupelnic tw:produktistnieje|]]) i do formuły
skierowanych.
; Pyt.13
:
:; -
:: LISP jest językiem imperatywnym.


<center><math>\exists z' \exists x_1'\; z=(z',x_1')\land\varphi'
:; +
</math></center>
::  FORTRAN jest językiem imperatywnym.


otrzymując zbiór <math>y</math>. Wymagany zbiór <math>y'</math> istnieje na mocy
:; +
Twierdzenia&nbsp;[[##tw:pierwszaproj|Uzupelnic tw:pierwszaproj|]] i jest równy <math>\pi_1(y)</math>.
:: <math>\displaystyle \mathbf{Dcpo}</math> jest kategorią zupełną i kartezjańsko
zamkniętą.


Przykładem zastosowania powyższego twierdzenia może być otrzymanie drugiej projekcji
:; -
z iloczynu kartezjańskiego. Aby otrzymać <math>\pi_2(z)</math> stosujemy powyższe twierdzenie do
::  Kategoria dziedzin ciągłych i funkcji ciągłych w sensie
<math>x_1'=z</math>, <math>x=\bigcup\bigcup{z}</math> i wyrażenia <math>\varphi'</math> mówiącego <math>\exists w\;
Scotta jest zupełna.
(w,z')\in x_1'</math>.
 
:; -
::  Kategoria dziedzin ciągłych i funkcji ciągłych w sensie
Scotta jest kartezjańsko zamknięta.
 
:; -
::  Kategoria dziedzin algebraicznych i funkcji ciągłych w sensie
Scotta jest kartezjańsko zamknięta.
 
:; -
::  Jeśli <math>\displaystyle D</math> jest dziedziną ciągłą i <math>\displaystyle E</math> jest dziedziną
bc-zupełną, to <math>\displaystyle [D,E]</math> jest dziedziną bc-zupełną.
 
:; +
::  Jeśli <math>\displaystyle D</math> jest dziedziną ciągłą i <math>\displaystyle E</math> jest dziedziną
bc-zupełną, to <math>\displaystyle [D,E]</math> jest dcpo.
 
:; +
::  Operator <math>\displaystyle \mathrm{fix}\colon [P,P]\to P</math> przypisujący
funkcji ciągłej w sensie Scotta na dcpo posiadającym element
najmniejszy jej punkt stały jest ciągły w sensie Scotta.
 
:; +
::  Operator <math>\displaystyle \mathrm{fix}\colon [P,P]\to P</math> przypisujący
funkcji ciągłej w sensie Scotta na dowolnej kracie zupełnej jej
punkt stały jest ciągły w sensie Scotta.
 
:; +
::  Pętle <math>\displaystyle \mathtt{while}</math> w semantyce denotacyjnej
modelujemy używając operatora punktu stałego.
; Pyt.14
:
:; +
::  <math>\displaystyle \mathbf{Dcpo}^{EP}_{\bot}</math> jest <math>\displaystyle \omega</math>-kategorią.
 
:; +
::  <math>\displaystyle \mathbf{Dcpo}</math> jest <math>\displaystyle \omega</math>-kategorią.
 
:; +
::  <math>\displaystyle \mathbf{Set}</math> jest <math>\displaystyle \omega</math>-kategorią.
 
:; -
::  Funktor między kategoriami dziedzin jest ciągły, jeśli
jest funkcją ciągłą w sensie Scotta.
 
:; -
::  W <math>\displaystyle \mathbf{Set}</math> równanie <math>\displaystyle D\cong [D,D]</math> dla <math>\displaystyle D\in \mathbf{Set}_0</math> nie ma żadnego
rozwiązania.
 
:; +
::  W <math>\displaystyle \mathrm{Dcpo}</math> istnieje nieskończenie wiele rozwiązań
równania <math>\displaystyle D\cong [D,D]</math>.
 
:; -
::  Istnienie kategorii, w której rekursywne równania typu <math>\displaystyle D\cong [D,D]</math>
mają rozwiązania, jest wykorzystywane w semantyce operacyjnej
nietypowanego rachunku lambda.
 
:; +
::  Istnienie kategorii, w której rekursywne równania typu <math>\displaystyle D\cong [D,D]</math>
mają rozwiązania, jest wykorzystywane w semantyce denotacyjnej
nietypowanego rachunku lambda.
 
:; +
::  Przekątna <math>\displaystyle \Delta\colon
\mathbf{Dcpo}\to\mathbf{Dcpo}\times\mathbf{Dcpo}</math> jest funktorem
ciągłym i lokalnie ciągłym.
 
:; +
::  <math>\displaystyle \mathbf{Dcpo}</math> jest kategorią zupełną i kozupełną.
 
:; -
::  Każdy endomorfizm w <math>\displaystyle \mathbf{Dcpo}</math> posiada najmniejszy
punkt stały.
 
:; -
::  Dowolny endofunktor na <math>\displaystyle \omega</math>-kategorii posiada punkt
stały.
 
:; +
::  Każdy ciągłe endofunktor na <math>\displaystyle \omega</math>-kategorii posiada
punkt stały.
 
:; -
::  W <math>\displaystyle \mathbf{Set}</math> istnieją nietrywialne rozwiązania
rówania <math>\displaystyle X\cong X+X</math>.
 
:; -
::  Liczby naturalne <math>\displaystyle \omega</math> są rozwiązaniem równania
<math>\displaystyle X\cong\mathbf{1}\oplus X</math> w kategorii <math>\displaystyle \mathbf{Dcpo}</math>.
 
:; -
::  Liczby naturalne <math>\displaystyle \omega</math> są rozwiązaniem równania
<math>\displaystyle X\cong X_{\bot}</math> w katetgorii <math>\displaystyle \mathbf{Dcpo}</math>.
 
:; -
::  Leniwe liczby naturalne są rozwiązaniem równania <math>\displaystyle X\cong
X\oplus X</math> w kategorii <math>\displaystyle \mathbf{Dcpo}</math>.
 
:; +
::  Podzbiory liczb naturanych <math>\displaystyle \mathcal{P}\omega</math>
uporządkowane względem inkluzji spełniają rówanie
<math>\displaystyle \mathcal{P}\omega\cong [\mathcal{P}\omega,\mathcal{P}\omega]</math> w
kategorii <math>\displaystyle \mathbf{Dcpo}</math>.
 
:; +
::  Model zbioru Cantora <math>\displaystyle \Sigma^{\infty}</math> jest rozwiązaniem
pewnego rekursywnego równania w kategorii <math>\displaystyle \mathbf{Dcpo}</math>.
; Pyt.15
:
:; -
::  Koalgebrą funktora <math>\displaystyle T\colon \mathbf{Set}\to\mathbf{Set}</math>
jest każda para <math>\displaystyle (X,a\colon TX\to X)</math>.
 
:; +
::  Algebry początkowe endofunktorów w <math>\displaystyle \mathbf{Set}</math> są
jedyne z dokładnością do izomrfizmu.
 
:; +
::  Istnieje kategoria, w której para
<math>\displaystyle (\mathbb{N},[0,s]\colon \mathbf{1}+\mathbb{N}\to\mathbb{N})</math> jest
obiektem końcowym.
 
:; +
::  Nieskończone listy nad alfabetem <math>\displaystyle A</math> są koalgebrą końcową
pewnego endofunktora na <math>\displaystyle \mathbf{Set}</math>.
 
:; -
::  Nieskończone listy nad alfabetem <math>\displaystyle A</math> są koalgebrą
początkową pewnego endofunktora na <math>\displaystyle \mathbf{Set}</math>.
 
:; -
::  Każda bisymulacja jest bipodobieństwem, ale nie
odwrotnie.
 
:; -
::  Dwie nieskończone listy będące w relacji bisymulacji
muszą być sobie równe.
 
:; +
::  Dwie bipodobne nieskończone listy są sobie równe.
 
:; -
::  Istnieje bipodobieństwo, które nie jest bisymulacją.
 
:; +
::  Koindukcja jest metodą dowodzenia własności list
nieskończonych.
 
:; -
::  Metoda dowodzenia przez koindukcję opiera się na
własności uniwersalnej algebr początkowych endofunktorów w
<math>\displaystyle \mathbf{Set}</math>.
 
:; -
::  Relacja odwrotna do bisymulacji jest bipodobieństwem.
 
:; -
::  <math>\displaystyle T</math>-koalgebry dla ustalonego funktora <math>\displaystyle T\colon \mathbf{Set}\to\mathbf{Set}</math> wraz z homomorfizmami
tworzą kategorię małą.
 
:; -
::  Graf homomorfizmu dwóch dowolnych koalgebr jest
bipodobieństwem.
 
:; +
::  Graf homomorfizmu dwóch dowolnych koalgebr jest
bisymulacją.
 
:; +
::  Istnieją endofunktory w <math>\displaystyle \mathbf{Set}</math>, dla których
kategoria algebr nie posiada obiektu początkowego.
 
:; -
::  Dla każdego endofunktora <math>\displaystyle T</math> w <math>\displaystyle \mathbf{Set}</math> kategoria
<math>\displaystyle T</math>-koalgebr posiada obiekt końcowy.
 
:; +
::  Zasada indukcji matematycznej na liczabch naturalnych
jest równoważna faktowi, że liczby naturalne wraz z elementem zero
i funkcją następnika tworzą algebrę początkową endofunktora
<math>\displaystyle \mathbf{1}+(-)</math> w <math>\displaystyle \mathbf{Set}</math>.
 
:; +
::  Każda <math>\displaystyle T</math>-algebra początkowa jest izomorfizmem.
 
:; +
::  Każda <math>\displaystyle T</math>-koalgebra końcowa jest izomorfizmem.

Wersja z 18:41, 13 wrz 2006

Poniższe zdania twierdzące mogą być albo prawdziwe (oznaczone jako "+"), albo fałszywe (oznaczane "-"). Zbiór wszystkich pytań podzielono na 15 części, odpowiadających kolejnym modułom.

Pyt.1
-
Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które

spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności, dziedzin i kodziedzin morfizmów.

+
Dowolna kategoria może być interpretowana jako pewnien specjalny graf

skierowany.

+
Dowolna kategoria może być interpretowana jako pewna

algebra.

+
Kategoria może być jednocześnie mała i lokalnie mała.
-
Kategoria może być jednocześnie mała i duża.
+
Kategoria może być jednocześnie lokalnie mała i duża.
-
Kategoria 𝐂, w której dla każdego obiektu A∈𝐂0 istnieje dokładnie jeden morfizm typu A→A

nazywamy konkretną.

+
Kategoria 𝐂, w której dla każdego obiektu A∈𝐂0 istnieje dokładnie jeden morfizm typu A→A

nazywamy dyskretną.

-
Kategoria 𝐂, w której dla każdego obiektu A∈𝐂0 istnieje dokładnie jeden morfizm typu A→A

nazywamy monoidem.

-
Kategoria 𝐂, w której dla każdego obiektu A∈𝐂0 istnieje dokładnie jeden morfizm typu A→A

nazywamy posetem.

-
Nie istnieje kategoria, w której jest 5 obiektów i 6

morfizmów.

+
Nie istnieje kategoria, w której jest 6 obiektów i 5

morfizmów.

-
Nie istnieje kategoria, w której wszystkie obiekty są

izomorficzne.

-
Nie istnieje kategoria, w której wszystkie morfizmy mają tę samą kodziedzinę.
+
Kategoria 𝐑𝐞𝐥 jest lokalnie mała i duża.
-
Liczby naturalne (ℕ,≤) są kategorią

dyskretną.

-
Kategoria 𝐂𝐚𝐭 jest lokalnie mała.
+
Kategorie dyskretne są lokalnie małe.
+
Kategorie konkretne są lokalnie małe.
+
Grupa (G,∘,e) to kategoria z jednym obiektem.
-
𝐆𝐫𝐩 to kategoria, w której wszystkie obiekty

są izomorficzne.

+
Dowolne dwa izomorficzne obiekty w 𝐒𝐞𝐭 są równoliczne.
+
Preporządek jest z definicji taką kategorią, w której między

dowolnymi dwoma obiektami istnieje co najwyżej jeden morfizm.

+
Preporządek jest kategorią lokalnie małą.
-
Preporządek to taka kategoria, w której nie istnieją dwa różne

obiekty izomorficzne.

+
Preporządek jest częściowym porządkiem wtedy i tylko wtedy, gdy każde

dwa obiekty izomorficzne są sobie równe.

+
Rachunek lambda jako kategoria jest lokalnie mała.
-
𝐒𝐞𝐭 jest obiektem 𝐂𝐚𝐭.
+
W każdej kategorii niepustej istnieją izomorfizmy.
Pyt.2
+
Monomorfizmem w 𝐒𝐞𝐭 jest każda funkcja injektywna.
-
Monomorfizmem w 𝐌𝐨𝐧 jest każda funkcja injektywna.
+
Monomorfizmem w posecie (P,≤) jest każda ze strzałek.
+
Monomorfizmem w dowolnej kategorii 𝐂 jest każdy epimorfizm w

𝐂op.

+
W kategoriach dyskretnych monomorfizmy są izomorfizmami.
+
W kategoriach dyskretnych monomorfizmy są epimorfizmami.
+
Istnieją kategrie konkretne, w których każdy epimorfizm

jest surjekcją.

-
Istnieją kategrie konkretne, w których żaden epimorfizm

nie jest surjekcją.

+
Istnieją kategorie konkretne, w których pewne epimorfizmy

nie są surjekcjami.

+
Epimorfizm to pojęcie dualne do monomorfizmu.
+
Izomorfizm to pojęcie samodualne (tj. dualne do samego

siebie).

-
Monomorfizm to pojęcie samodualne.
+
W 𝐓𝐨𝐩 epimorfizmami są ciągłe surjekcje.
-
W kategorii przestrzeni topologicznych Hausdorffa i

funkcji ciągłych epimorfizmy to dokładnie ciągłe surjekcje.

+
W preporządku sekcje są izomorfizmami.
+
W preporządku pojęcia: sekcji, izomorfizmu, retrakcji,

monomorfizmu, epimorfizmu pokrywają się.

+
Funktory wierne zachowują sekcje.
+
Retrakcje w 𝐒𝐞𝐭 to dokładnie epimorfizmy.
-
Jeśli funktor nie jest wierny, to nie musi zachowywać

retrakcji.

-
Każda sekcja jest monomorfizmem i epimorfizmem.
+
Każda sekcja jest monomorfizmem.
+
W kategorii dyskretnej każda sekcja jest epimorfizmem.
-
Każdy wierny funktor odzwierciedla sekcje i retrakcje.
+
W 𝐂𝐚𝐭 istnieją epimorfizmy, które nie są

surjekcjami.

+
W 𝐂𝐚𝐭 istnieją epimorfizmy, które nie są

retrakcjami.

-
Każdy funktor zachowuje monomorfizmy.
-
Każdy funktor pełny zachowuje izomorfizmy.
+
Homfunktory kowariantne zachowują i odzwierciedlają monomorfizmy.
-
Mono retrakcja jest identycznością.
+
Mono retrakcja jest izomorfizmem.
-
Retrakt dziedziny ciągłej jest algebraiczny.
+
Retrakt dziedziny algebraicznej jest algebraiczny.
+
W parze e-p zanurzenie e jest injekcją.
-
W parze e-p projekcja jest injekcją.
+
W 𝐑𝐞𝐥 obiektem początkowym jest relacja

pusta.

+
W 𝐆𝐫𝐩 obiektem początkowym jest każdy obiekt

końcowy

+
W 𝐏𝐨𝐬 nie istnieje obiekt, który jest

jednocześnie początkowy i końcowy.

+
Każde dwa obiekty początkowe w dowolnej kategorii są

izomorficzne.

-
𝐂𝐚𝐭 nie ma obiektu początkowego.
-
Każda kategoria dyskretna jest obiektem końcowym w

𝐂𝐚𝐭.

+
Istnieją małe kategorie, w których nie ma obiektów

początkowych, ani końcowych.

+
Jeśli w danej kategorii pewien obiekt początkowy i pewien obiekt końcowy

są izomorficzne, to kategoria ta posiada tylko jeden morfizm.

+
Funkcja następnik succ:ℕ→ℕ jest uogólnionym elementem ℕ.
+
Każdy element jest uogólnonym elementem, ale nie

odwrotnie.

+
W odcinku ((0,1),≤) (jako kategorii) istnieje kontinuum elementów.
+
W odcinku ([0,1],≤) istnieje kontinuum elementów.
-
W odcinku ((0,1),≤) istnieje kontinuum elementów

uogólnionych.

+
Każdy element, którego kodziedziną jest obiekt końcowy

jest identycznością.

+
Każdy element, którego kodziedziną jest obiekt początkowy

jest identycznością obiektu początkowego.

+
Każdy element jest monomorfizmem.
+
Każdy element jest sekcją.
-
Każdy element jest retrakcją.
-
Każdy element jest izomorfizmem.
-
Złożenie elementów jest elementem.
Pyt.3
+
Aksjomaty kategorii są samodualne.
-
Pojęcie retrakcji jest samodualne.
-
Pojęcie obiektu końcowego jest samodualne.
+
Pojęcie izomorfizmu jest samodualne.
-
Niech 𝐂 będzie kategorią z produktami. Niech

A,B,C,D∈𝐂0 i f,g∈𝐂1. Jeśli A×B≅C×D, to A≅C i B≅D.

-
Niech 𝐂 będzie kategorią z produktami. Niech

A,B,C,D∈𝐂0 i f,g∈𝐂1. Jeśli A×B≅B×A, to A≅B.

+
Niech 𝐂 będzie kategorią z produktami. Niech

A,B,C,D∈𝐂0 i f,g∈𝐂1. Jeśli A×𝟏≅𝟏, to A≅𝟏.

+
Jeśli f,g są sekcjami, to f×g też.
+
Jeśli f,g są retrakcjami, to f×g też.
+
Jeśli f,g są izomorfizmami, to f×g też.
-
Jeśli f,g są monomorfizmami, to f×g też.
+
Lambda rachunek jest kategorią z produktami.
+
Każdy zbiór jest koproduktem pewnych dwóch innych zbiorów

w 𝐒𝐞𝐭.

+
W posecie (P,≤) każdy produkt a×b dla a,b∈P

(o ile istnieje) jest ekwalizatorem wtedy i tylko wtedy, gdy a=b.

-
Każdy ekwalizator jest epimorfizmem.
-
W kategorii z pulbakami zawsze istnieją obiekty początkowe.
+
W kategorii z pulbakami i obiektem końcowym zawsze istnieją ekwalizatory.
-
Każda sekcja jest ekwalizatorem.
+
Pulbak epimorfizmu jest epimorfizmem.
+
Pulbak izomorfizmu jest izomorfizmem.
+
Każda kategoria z koproduktami i koekwalizatorami posiada

pushouty.

-
Każda kategoria z obiektem początkowym i koekwalizatorami

posiada obiekt końcowy.

Pyt.4
+
Zbiory skończone i funkcje tworzą kategorię kartezjańsko

zamkniętą.

-
Przestrzenie topologiczne i funkcje ciągłe tworzą

kategorię kartezjańsko zamkniętą.

+
Lambda rachunek (z dodanym elementem końcowym) jest kategorią kartezjańsko zamkniętą.
-
Algebry Boole'a jako kategorie są kozupełne.
+
Algebry Boole'a są dystrybutywne.
+
Algebry Heytinga jako kategorie są kartezjańsko zamknięte.
-
Grupy abelowe i homomorfizmy grup są kartezjańsko

zamknięte.

-
Kategorie dyskretne są kartezjańsko zamknięte.
+
Algebra Heytinga jest algebrą Boole'a wtedy i tylko

wtedy, gdy każdy element posiada element przeciwny.

-
Kategoria dziedzin ciągłych i funkcji ciągłych w sensie

Scotta jest kartezjańsko zamknięta.

+
Dla dowolnej topologii krata zbiorów otwartych jest

algebrą Heytinga.

-
Dla dowolnej topologii krata zbiorów otwartych jest

algebrą Boole'a.

+
Zbiory otwarte, regularne w dowolnej topologii tworzą

algebrę Boole'a.

-
Każda algebra Boole'a jest izomorficzna ze zbiorem

podzbiorów pewnego zbioru.

+
Monomorfizmy o wspólnej kodziedzinie uporządkujmy

relacją "faktoryzacji", tj. f≤g wtw, gdy istnieje h tak, że g∘h=f. Zdefiniujmy relację równoważności R między monomorfizmami o wspólnej kodziedzinie jako: f≡g wtw, gdy f≤g i g≤f. Uporządkujmy zbiór klas abstrakcji tej relacji jako: [f]⊑[g] wtw, gdy f≤g. Czy ten częściowy porządek jest algebrą Heytinga?

+
Kategoria funkcji między zbiorami 𝐒𝐞𝐭→ jest kartezjańsko zamknięta.
-
Kategoria porządków liniowych i funkcji monotonicznych

jest kartezjańsko zamknięta.

-
W kategorii kartezjańsko zamkniętej 𝐂 funktor podnoszenia do potęgi [A,−] zachowuje

koprodukty (tutaj A∈𝐂0).

+
W kategorii kartezjańsko zamkniętej 𝐂 funktor podnoszenia do potęgi [A,−] zachowuje

obiekt końcowy (tutaj A∈𝐂0).

Pyt.5
+
Funktory tego samego typu wraz z ich transformacjami

naturalnymi tworzą kategorię.

+
𝐓𝐨𝐩 jest konkretna.
+
𝐑𝐞𝐥 jest konkretna.
+
Funktor List:𝐒𝐞𝐭→𝐌𝐨𝐧

zachowuje koprodukty.

-
Funktor List:𝐒𝐞𝐭→𝐌𝐨𝐧

zachowuje obiekt końcowy.

+
Funktor List:𝐒𝐞𝐭→𝐌𝐨𝐧 zachowuje obiekt początkowy.
-
Funktor zapominania 𝐓𝐨𝐩→𝐒𝐞𝐭 jest

pełny.

-
Kontrawariantny funktor potęgowy jest pełny.
+
Każda rama jest algebrą Heytinga.
+
Operacja przypisująca danej przestrzeni topologicznej jej

zbiory otwarte może być rozszerzona do funktora kontrawariantnego.

-
Kontrawariantny funktor potęgowy jest zawsze wierny.
+
Transformacja naturalna dwóch funktorów, której komponentami są

izomorfizmy jest izomorfizmem w pewnej kategorii funktorów.

+
Istnieją dwa funktory, których złożenie jest

transformacją identycznościową w 𝐒𝐞𝐭, ale które nie są izomorficzne.

-
Operacja, która przestrzeni wektorowej V przypisuje

jej przestrzeń podwójnie dualną V** jest naturalnym izomorfizmem.

+
Operacja, która przestrzeni wektorowej V przypisuje

jej przestrzeń podwójnie dualną V** jest naturalnym izomorfizmem, o ile V jest skończenie wymiarowa.

+
Kowariantny homfunktor zachowuje produkty dowolnej mocy.
-
Dla dowolonych zbiorów X,Y istnieje następująca

bijekcja:
𝒫(X×Y)≅𝒫(X)×𝒫(Y).

-
Operacja F:𝐂×𝐃→𝐄 jest bifunktorem wtedy i tylko wtedy, gdy dla

dowolnych obiektów C∈𝐂0, D∈𝐃0 operacje F(C,−):𝐃→𝐄 oraz F(−,D):𝐂→𝐄 są funktorami.

-
Inkluzja 𝐆𝐫𝐩→𝐂𝐚𝐭 zachowuje

eksponenty.

Pyt.6
-
Każde dwie równoważne kategorie są izomorficzne.
+
Każde dwie izomorficzne kategorie są równoważne.
-
Każde dwie dualne kategorie są izomorficzne.
-
Funktor jest równoważnością wtedy i tylko wtedy, gdy jest

pełny i wierny.

+
Jeśli preporządek jest równoważny porządkowi, to jest

porządkiem.

+
Istnieją dwa preporządki równoważne, które nie są

izomorficzne.

+
Kategoria zbiorów i funkcji jest dualna do kategorii

zupełnych algebr Boole'a i homomorfizmów.

-
Kategoria zbiorów skończonych i funkcji jest dualna do kategorii

algebr Boole'a.

-
Każda atomowa algebra Boole'a jest izomorficzna ze zbiorem

podzbiorów pewnego zbioru.

-
Każda zupełna algebra Boole'a jest izomorficzna ze

zbiorem podzbiorów pewnego zbioru.

+
Jeśli algebra Boole'a jest izomorficzna ze zbiorem

podzbiorów pewnego zbioru, to jest zupełna.

-
Każda zupełna algebra Boole'a jest atomowa.
+
Każda skończona algebra Boole'a jest zupełna.
-
Każda atomowa algebra Boole'a jest skończona.
+
Każda skończona algebra Boole'a jest atomowa.
+
Każda rama jest kratą dystrybutywną.
+
Jeśli L jest kratą dystrybutywną, to Lop też.
+
W dowolnej kracie L dopełnienie filtra pierwszego jest

ideałem.

+
Każdy ultrafiltr w algebrze Boole'a jest pierwszy.
-
Każdy filtr pierwszy w kracie dystrybutywnej jest

ultrafiltrem.

+
Filtr otoczeń otwartych dowolnego punktu w przestrzeni

topologicznej jest filtrem właściwym.

+
Filtr otoczeń otwartych dowolnego punktu w przestrzeni

topologicznej jest filtrem zupełnie pierwszym.

+
Filtr otoczeń otwartych dowolnego punktu w przestrzeni

topologicznej jest filtrem pierwszym.

-
W dowolnej kracie L, jeśli F jest filtrem, zaś I

ideałem, oraz F∩I=∅, wtedy istnieje filtr pierwszy F′ taki, że F′⊇F i F′∩I=∅.

+
W kratach dystrybutywnych ultrafiltry są pierwsze.
-
W kratach dystrybutywnych filtry pierwsze są maksymalne.
+
Każda przestrzeń realna jest T0.
-
Każda przestrzeń T0 jest realna.
-
Każda przestrzeń T1 jest realna.
-
Przestrzenie realne są przestrzeniami Hausdorffa.
+
Dziedziny ciągłe w topologii Scotta są realne.
+
W porządku specjalizacji przestrzeni realnej istnieją

suprema wszystkich zbiorów skierowanych.

-
Funktor Ω:𝐓𝐨𝐩→𝐅𝐫𝐦op

jest prawym sprzężeniem do funktora pt:𝐅𝐫𝐦op→𝐓𝐨𝐩.

+
Dla dowolnej topologii X przestrzeń

pt(Ω(X)) jest przestrzenią T0.

+
Dla dowolnej topologii realnej X przestrzeń

pt(Ω(X)) jest homeomorficzna z X.

-
Dla dowolnej topologii X przestrzeń

pt(Ω(X)) jest przestrzenią Hausdorffa.

+
Jeśli krata L jest przestrzenną ramą, to topologia

pt(L) jest realna.

Pyt.7
+
Dla dowolnej kategorii 𝐂 kategoria

[𝐂op,𝐒𝐞𝐭] jest kartezjańsko zamknięta, zupełna i kozupełna.

+
Funktor Yonedy zachowuje izomorfizmy.
+
Funktor Yonedy odzwierciedla retrakcje.
+
Funktor Yonedy jest reprezentowalny.
-
Każde dwa funktory reprezentowalne są izomorficzne.
+
Kontrawariantny funktor potęgowy jest reprezentowalny.
-
Para (ℕ,+),0) jest reprezentacją funktora

zapominania U:𝐌𝐨𝐧→𝐒𝐞𝐭.

+
Każde dwie reprezentacje funktora F:𝐂op (gdzie 𝐂 jest dowolną lokalnie małą

kategorią) są izomorficzne.

-
Każdy funktor typu 𝐂op→𝐒𝐞𝐭 dla

lokalnie małej kategorii 𝐂 jest reprezentowalny.

+
Jeśli 𝒴(A)(X)≅𝒴(A)(Y), to

X≅Y dla dowolnych obiektów X,Y lokalnie małej kategorii 𝐂.

+
Jeśli 𝒴(X)(A)≅𝒴(Y)(A), to

X≅Y dla dowolnych obiektów X,Y lokalnie małej kategorii 𝐂.

Pyt.8
+
Obiekt końcowy jest stożkiem nad pustym diagramem.
+
Obiekt końcowy jest granicą pustego diagramu.
-
Obiekt początkowy jest granicą pustego diagramu.
+
Dowolny diagram w kategorii zupełniej 𝐂

posiada granicę.

+
Istnieje kategoria kozupełna 𝐂, w której nie ma

obiektu końcowego.

+
Produkt jest granicą diagramu nad kategorią dyskretną

(tzn. produkt w 𝐂 jest granicą funktora 𝐉→𝐂, gdzie 𝐉 jest kategorią dyskretną.

+
Istnieje kategoria, w której koprodukt w 𝐒𝐞𝐭 jest

produktem.

-
Ekwalizator jest granicą diagramu, którego dziedziną jest

kategoria, w której są dokładnie 2 strzałki.

+
Ekwalizator jest granicą diagramu, którego dziedziną jest

kategoria, w której są dokładnie 4 strzałki.

+
Ekwalizator jest granicą diagramu, którego dziedziną jest

kategoria, w której są dokładnie 2 strzałki równoległe.

-
Jeśli w danej kategorii istnieją wszystkie pulbaki i co

najmniej jeden obiekt końcowy, to w tej kategorii istnieją wszystkie granice.

+
Jeśli w danej kategorii istnieją wszystkie pulbaki i co

najmniej jeden obiekt końcowy, to w tej kategorii istnieją wszystkie granice skończone.

+
Jeśli w posecie (P,≤) istnieją wszystkie granice, to

poset dualny (P,≥) jest kratą zupełną.

-
Jeśli w posecie (P,≤) istnieją wszystkie granice, to

poset dualny (P,≥) jest algebrą Heytinga.

+
Każda mała kozupełna kategoria jest preporządkiem.
+
Każda mała zupełna kategoria jest preporządkiem.
-
Każda lokalnie mała kozupełna kategoria jest preporządkiem.
-
Każda lokalnie mała zupełna kategoria jest preporządkiem.
-
Kategoria zbiorów skończonych i funkcji jest zupełna.
+
Kategoria 𝐃𝐜𝐩𝐨 jest zupełna.
+
Jeśli kategoria 𝐂 posiada pulbaki i obiekt

końcowy, to posiada też produkty.

-
Jeśli kategoria 𝐂 posiada pulbaki i obiekt

końcowy, to posiada też koprodukty.

+
Funktor Yonedy jest ciągły.
-
Funktor Yonedy zachowuje dowolne kogranice.
Pyt.9
+
Funktor podnoszenia do potęgi [X,−]:𝐂→𝐂, X∈𝐂0 w kartezjańsko

zamkniętej kategorii 𝐂 jest prawym sprzężeniem.

+
Istnieją funktory posiadające zarówno lewe, jak i prawe

sprzężenia.

-
Funktor, który posiada lewe sprzężenie nie może posiadać

prawego sprzężenia.

-
Funktory zapominania zawsze posiadają lewe sprzężenie.
-
Funktory wolne są prawym sprzężeniem do funktorów

zapominania.

+
Funktor List:𝐒𝐞𝐭→𝐌𝐨𝐧

jest funktorem wolnym.

-
Nie istnieje lewe sprzężenie funktora zapominania

𝐓𝐨𝐩→𝐒𝐞𝐭.

-
Operacja przeciwobrazu funkcji jest lewym sprzężeniem operacji

obrazu funkcji.

+
Koprodukt jest lewym sprzężeniem lewego sprzężenia

produktu.

-
Każdy funktor będący lewym sprzężeniem jest wierny.
-
Operacja brania wnętrza zbioru w przestrzeni

topologicznej X jest lewym sprzężeniem inkluzji zbiorów otwartych w podzbiory X.

Pyt.10
+
Jeśli funktor jest równoważnością kategorii, to posiada

lewe i prawe sprzężenie.

+
Jeśli każdy komponent kojedności sprzężenia jest

retrakcją, to prawe sprzężenie jest funktorem wiernym.

-
Jeśli każdy komponent kojedności sprzężenia jest

epimorfizmem, to prawe sprzężenie jest funktorem pełnym.

+
Jeśli prawe sprzężenie jest funktorem pełnym i wiernym, to

kojedność sprzężenia jest izomorfizmem.

-
Jeśli prawe sprzężenie jest funktorem pełnym i wiernym, to

jedność sprzężenia jest izomorfizmem.

+
Prawe sprzężenia zachowują granice, zaś lewe - kogranice.
-
Lewe sprzężenia zachowują granice, zaś prawe - kogranice.
+
Istnieją prawe sprzężenia, które zachowują kogranice oraz

lewe sprzężenia, które zachowują granice.

-
Jeśli funktor zachowuje granice, to ma lewe sprzężenie.
+
Jeśli funktor między posetami zachowuje granice, to ma

lewe sprzężenie.

+
Każda funkcja monotoniczna między kratami zupełnymi, posiadająca lewe

sprzężenie, zachowuje dowolne infima.

+
Prawe sprzężenie między posetami jest surjekcją wtedy i

tylko wtedy, gdy jego lewe sprzężenie jest injekcją.

-
Prawe sprzężenie między posetami jest injekcją wtedy i

tylko wtedy, gdy jego lewe sprzężenie jest surjekcją.

+
Każde dwa prawe sprzężenia danego funktora są

izomorficzne.

+
Każdy homomorfizm krat zupełnych posiada lewe i prawe

sprzężenie.

-
Każdy homomorfizm ram posiada lewe i prawe sprzężenie.
-
Każdy homomorfizm algebr Boole'a posiada lewe i prawe

sprzężenie.

+
Każdy homomorfizm zupełnych algebr Boole'a posiada prawe

i lewe sprzężenie.

-
W parze e-p między posetami, projekcja jest lewym

sprzężeniem zanurzenia.

+
W parze e-p między posetami, zanurzenie zachowuje dowolne

suprema.

+
W parze e-p między posetami, zanurzenie i projekcja

wzajemnie się wyznaczają.

Pyt.11
+
Każde sprzężenie F⊣G indukuje monadę

(GF,η,GηF).

+
Każde sprzężenie F⊣G indukuje komonadę

(FG,ε,FηG).

-
Dowolna monada jest monadą indukowaną przez dokładnie

jedno sprzężenie.

+
Dowolna monada jest monadą indukowaną przez sprzężenie.
+
Każda monada na preporządku jest operacją idempotentną.
-
Funktor zapominania 𝐌𝐨𝐧→𝐒𝐞𝐭 jest

częścią sprzężenia, którego algebry monady indukowanej tworzą kategorię równoważną z 𝐒𝐞𝐭.

+
Funktor zapominania 𝐌𝐨𝐧→𝐒𝐞𝐭 jest

częścią sprzężenia, którego algebry monady indukowanej tworzą kategorię równoważną z 𝐌𝐨𝐧.

+
Zwarte przestrzenie Hausdorffa i funkcje ciągłę tworzą kategorię algebraiczną.
-
Zupełne algebry Boole'a i homomorfizmy tych algebr tworzą

kategorię algebraiczną.

+
Kategoria grup jest równoważna kategorii algebr dla

pewnej monady.

+
Suma mnogościowa ⋃ jest mnożeniem pewnej monady.
+
Operacja dodawania nowego elementu najmniejszego do

częściowego porządku indukuje monadę nad 𝐏𝐨𝐬.

Pyt.12
-
Każda dziedzina ciągła posiada bazę przeliczalną.
-
Każdy element bazy dziedziny ciągłej jest zwarty.
+
Każda baza posetu algebraicznego zawiera wszystkie

elementy zwarte.

+
Każdy poset skończony jest algebraiczny.
+
Każdy poset skończony jest dcpo.
+
Każda krata skończona jest dcpo.
-
Relacja aproksymacji na dowolnym posecie jest

interpolatywna.

+
Relacja aproksymacji na dowolnej dziedzinie Scotta jest

interpolatywna.

-
Liczby naturalne są dcpo.
+
Liczby naturalne są posetem algebraicznym i bc-zupełnym.
+
Każda rama jest dcpo.
-
Każda krata dystrybutywna jest dcpo.
+
Istnieje poset nieskończony, którego każdy element, który

nie jest maksymalny, jest zwarty.

-
Zbiory domknięte w sensie Scotta na dowolnym posecie są domknięte ze względu

na dowolne suprema.

+
Zbiory domknięte w sensie Scotta na dowolnym posecie skończonym są domknięte ze względu

na dowolne suprema.

+
Stożki górne w posecie P (tj. zbiory typu ↑x dla x∈P) są zwarte w topologii Scotta.
+
Każdy stożek dolny ↓x w dziedzinie ciągłej P wraz z

porządkiem z P obciętym do ↓x jest dziedziną ciągłą.

+
Topologia Scotta na dowolnym porządku jest T0.
+
Istnieją częściowe porządki dowolnej mocy, dla których

topologia Scotta jest T1.

+
Topologia Scotta na porządku jest T1 wtedy i tylko

wtedy, gdy częściowy porządek redukuje się do równości.

+
Topologia Scotta na posecie posiadającym element

najmniejszy jest zwarta.

+
Topologia Scotta na dowolnej dziedzinie ciągłej jest

realna.

-
Topologia Scotta na dowolnym dcpo jest realna.
+
Funkcja ciągła w sensie Scotta jest monotoniczna.
-
Każda funkcja ciągła w sensie Scotta na dowolnym posecie posiada punkt stały.
-
Każda funkcja ciągła w sensie Scotta na posecie

posiadającym element najmniejszy posiada punkt stały.

+
Każda funkcja ciągła w sensie Scotta na dcpo

posiadającym element najmniejszy posiada najmniejszy punkt stały.

+
Każda funkcja monotoniczna na dcpo

posiadającym element najmniejszy posiada punkt stały.

+
Porządek specjalizacji topologii Scotta na dziedzinie

ciągłej pokrywa się z porządkiem tejże dziedziny.

+
Funkcje ciągłe w sensie Scotta zachowują suprema zbiorów

skierowanych.

Pyt.13
-
LISP jest językiem imperatywnym.
+
FORTRAN jest językiem imperatywnym.
+
𝐃𝐜𝐩𝐨 jest kategorią zupełną i kartezjańsko

zamkniętą.

-
Kategoria dziedzin ciągłych i funkcji ciągłych w sensie

Scotta jest zupełna.

-
Kategoria dziedzin ciągłych i funkcji ciągłych w sensie

Scotta jest kartezjańsko zamknięta.

-
Kategoria dziedzin algebraicznych i funkcji ciągłych w sensie

Scotta jest kartezjańsko zamknięta.

-
Jeśli D jest dziedziną ciągłą i E jest dziedziną

bc-zupełną, to [D,E] jest dziedziną bc-zupełną.

+
Jeśli D jest dziedziną ciągłą i E jest dziedziną

bc-zupełną, to [D,E] jest dcpo.

+
Operator fix:[P,P]→P przypisujący

funkcji ciągłej w sensie Scotta na dcpo posiadającym element najmniejszy jej punkt stały jest ciągły w sensie Scotta.

+
Operator fix:[P,P]→P przypisujący

funkcji ciągłej w sensie Scotta na dowolnej kracie zupełnej jej punkt stały jest ciągły w sensie Scotta.

+
Pętle while w semantyce denotacyjnej

modelujemy używając operatora punktu stałego.

Pyt.14
+
𝐃𝐜𝐩𝐨⊥EP jest ω-kategorią.
+
𝐃𝐜𝐩𝐨 jest ω-kategorią.
+
𝐒𝐞𝐭 jest ω-kategorią.
-
Funktor między kategoriami dziedzin jest ciągły, jeśli

jest funkcją ciągłą w sensie Scotta.

-
W 𝐒𝐞𝐭 równanie D≅[D,D] dla D∈𝐒𝐞𝐭0 nie ma żadnego

rozwiązania.

+
W Dcpo istnieje nieskończenie wiele rozwiązań

równania D≅[D,D].

-
Istnienie kategorii, w której rekursywne równania typu D≅[D,D]

mają rozwiązania, jest wykorzystywane w semantyce operacyjnej nietypowanego rachunku lambda.

+
Istnienie kategorii, w której rekursywne równania typu D≅[D,D]

mają rozwiązania, jest wykorzystywane w semantyce denotacyjnej nietypowanego rachunku lambda.

+
Przekątna Δ:𝐃𝐜𝐩𝐨→𝐃𝐜𝐩𝐨×𝐃𝐜𝐩𝐨 jest funktorem

ciągłym i lokalnie ciągłym.

+
𝐃𝐜𝐩𝐨 jest kategorią zupełną i kozupełną.
-
Każdy endomorfizm w 𝐃𝐜𝐩𝐨 posiada najmniejszy

punkt stały.

-
Dowolny endofunktor na ω-kategorii posiada punkt

stały.

+
Każdy ciągłe endofunktor na ω-kategorii posiada

punkt stały.

-
W 𝐒𝐞𝐭 istnieją nietrywialne rozwiązania

rówania X≅X+X.

-
Liczby naturalne ω są rozwiązaniem równania

X≅𝟏⊕X w kategorii 𝐃𝐜𝐩𝐨.

-
Liczby naturalne ω są rozwiązaniem równania

X≅X⊥ w katetgorii 𝐃𝐜𝐩𝐨.

-
Leniwe liczby naturalne są rozwiązaniem równania X≅X⊕X w kategorii 𝐃𝐜𝐩𝐨.
+
Podzbiory liczb naturanych 𝒫ω

uporządkowane względem inkluzji spełniają rówanie 𝒫ω≅[𝒫ω,𝒫ω] w kategorii 𝐃𝐜𝐩𝐨.

+
Model zbioru Cantora Σ∞ jest rozwiązaniem

pewnego rekursywnego równania w kategorii 𝐃𝐜𝐩𝐨.

Pyt.15
-
Koalgebrą funktora T:𝐒𝐞𝐭→𝐒𝐞𝐭

jest każda para (X,a:TX→X).

+
Algebry początkowe endofunktorów w 𝐒𝐞𝐭 są

jedyne z dokładnością do izomrfizmu.

+
Istnieje kategoria, w której para

(ℕ,[0,s]:𝟏+ℕ→ℕ) jest obiektem końcowym.

+
Nieskończone listy nad alfabetem A są koalgebrą końcową

pewnego endofunktora na 𝐒𝐞𝐭.

-
Nieskończone listy nad alfabetem A są koalgebrą

początkową pewnego endofunktora na 𝐒𝐞𝐭.

-
Każda bisymulacja jest bipodobieństwem, ale nie

odwrotnie.

-
Dwie nieskończone listy będące w relacji bisymulacji

muszą być sobie równe.

+
Dwie bipodobne nieskończone listy są sobie równe.
-
Istnieje bipodobieństwo, które nie jest bisymulacją.
+
Koindukcja jest metodą dowodzenia własności list

nieskończonych.

-
Metoda dowodzenia przez koindukcję opiera się na

własności uniwersalnej algebr początkowych endofunktorów w 𝐒𝐞𝐭.

-
Relacja odwrotna do bisymulacji jest bipodobieństwem.
-
T-koalgebry dla ustalonego funktora T:𝐒𝐞𝐭→𝐒𝐞𝐭 wraz z homomorfizmami

tworzą kategorię małą.

-
Graf homomorfizmu dwóch dowolnych koalgebr jest

bipodobieństwem.

+
Graf homomorfizmu dwóch dowolnych koalgebr jest

bisymulacją.

+
Istnieją endofunktory w 𝐒𝐞𝐭, dla których

kategoria algebr nie posiada obiektu początkowego.

-
Dla każdego endofunktora T w 𝐒𝐞𝐭 kategoria

T-koalgebr posiada obiekt końcowy.

+
Zasada indukcji matematycznej na liczabch naturalnych

jest równoważna faktowi, że liczby naturalne wraz z elementem zero i funkcją następnika tworzą algebrę początkową endofunktora 𝟏+(−) w 𝐒𝐞𝐭.

+
Każda T-algebra początkowa jest izomorfizmem.
+
Każda T-koalgebra końcowa jest izomorfizmem.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR3&oldid=49776”