Seminár 1: Úvod do teórie kategórií
Kategória - C(O, A, ◦):
• O - kolekcia objektov
• A - kolekcia arrows - morfizmy medzi objektami z O
• ◦ - binárne skladanie morfizmov
– musí platiť asociativita - (h ◦ g) ◦ f = h ◦ (g ◦ f) = h ◦ g ◦ f
– identita id je voči operátoru neutrálna aj zľava aj sprava, nech f : a → b potom f ◦ ida = idb ◦ f = f
• id / 1 - identické morfizmy pre všetky objekty (ida - identický morfizmus pre a ∈ O)
• Hom(a, b) - kolekcia morfizmov z a do b
Kategórie
• Malá: aj O aj A sú množiny
• Veľká: nie malá
• Lokálne malá: pre všetky objekty a, b ∈ C je Hom(a, b) množina
• Riedka (thin): pre všetky objekty a, b ∈ C platí |Hom(a, b)| ∈ {0, 1}
• Voľná (free): kategória generovaná z orientovaného grafu pomocou voľnej konštrukcie (doplnenie identít a zložením hrán pre
každú cestu z u do v existuje hrana reprezentujúca túto cestu)
Špeciálne objekty
• iniciálny objekt
– a je iniciálny objekt ⇐⇒ ∀b ∈ OC. ∃!m ∈ AC. m : a → b
– do každého objektu kategórie vedie unikátna šípka
– v kategórii “typov” (Set) si môžeme predstaviť void, pretože pre každý iný typ T existuje funkcia asburd : void ->
T
– unikátny až na unikátny izomorfizmus
• terminálny objekt (duálny k iniciálnemu objektu)
– a je terminálny objekt ⇐⇒ ∀b ∈ OC. ∃!m ∈ AC. m : b → a
– z každého objektu kategórie vedie unikátna šípka
– v kategórii “typov” si môžeme predstaviť unit, pretože pre každý iný typ existuje funkcia unit : T -> ()
– unikátny až na unikátny izomorfizmus
Opačná kategória Cop
- Kategória s opačnými morfizmami (od C). Môžme hovoriť o duálnych pojmoch (napr. terminálny objekt
je iniciálny v opačnej kategórii, mono je duálne s epi, atď).
Špeciálne morfizmy
• monomorfizmus (mono)
– f : a → b ∈ C je monomorfizmus ⇐⇒
∀x ∈ C. ∀g, h : x → a ∈ C. {f ◦ g = f ◦ h =⇒ g = h}
– v Set je morfizmus f mono ⇐⇒ funkcia f je injektívna
• epimorfizmus (epi) (duálny k monomorfizmu)
– f : a → b ∈ C je epimorfizmus ⇐⇒
∀x ∈ C. ∀g, h : b → x ∈ C. {g ◦ f = h ◦ f =⇒ g = h}
– v Set je morfizmus f epi ⇐⇒ funkcia f je surjektívna
• izomorfizmus
f : a → b ∈ C je izomorfizmus ⇐⇒
∃g : b → a ∈ C. {g ◦ f = ida ∧ f ◦ g = idb}
• endomorfizmus
f : a → a
• automorfizmus
endomorfizmus + izomorfizmus
Príklady kategórií:
• 0 - kategória bez prvkov a morfizmov
• 1 - kategória s práve jedným prvkom a jeho identitou
• 2 - kategória s práve dvoma prvkami, medzi ktorými sú morfizmy
• Set - kategória množín a funkcií
• Grp - kategória grúp a homomorfizmov
• Cat - kategória malých kategórií a funktorov
• Order - kategória usporiadania s ≤
• Voľná kategória - konštrukcia z orientovaného grafu
• Monoid ako kategória - kategória s jedným objektom a endomorfizmami
• Grupa ako kategória - kategória s jedným objektom a automorfizmami
• Hask - “kategória typov v jazyku Haskell a funkcií”
void
int bool
kocicka unit
absurdint absurdbool
absurdunitabsurdkocicka
isEven
unitintkocickaint unitbool
kocickabool
unitkocicka
kocickaunit
Terminálne a iniciálne objekty v Set