Seminár 1: Úvod do teórie kategórií

Kategória - \(C(O, A, \circ)\):

• \(O\) - kolekcia objektov
• \(A\) - kolekcia arrows - morfizmy medzi objektami z \(O\)
• \(\circ\) - binárne skladanie morfizmov
  • musí platiť asociativita - \((h \circ g) \circ f = h \circ (g \circ f) = h \circ g \circ f\)
  • identita \(id\) je voči operátoru neutrálna aj zľava aj sprava, nech \(f : a \to b\) potom \(f \circ id_a = id_b \circ f = f\)
• \(id\) / \(1\) - identické morfizmy pre všetky objekty (\(id_a\) - identický morfizmus pre \(a \in 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 \in C\) je \(Hom(a, b)\) množina
• Riedka (thin): pre všetky objekty \(a, b \in C\) platí \(|Hom(a, b)| \in \{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 \(\iff \forall b \in O_C \ldotp\exists! m \in A_C \ldotp m: a \rightarrow 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 \(\iff \forall b \in O_C \ldotp\exists! m \in A_C \ldotp m : b \rightarrow 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 \(C^{op}\) - 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 \to b \in C\) je monomorfizmus \(\iff\)

  \(\forall x \in C \ldotp \forall g, h : x \to a \in C \ldotp \{ f \circ g = f \circ h \implies g = h \}\)

  • v Set je morfizmus \(f\) mono \(\iff\) funkcia \(f\) je injektívna

• epimorfizmus (epi) (duálny k monomorfizmu)

  • \(f : a \to b \in C\) je epimorfizmus \(\iff\)

  \(\forall x \in C \ldotp \forall g, h : b \to x \in C \ldotp \{ g \circ f = h \circ f \implies g = h \}\)

  • v Set je morfizmus \(f\) epi \(\iff\) funkcia \(f\) je surjektívna

• izomorfizmus

  \(f : a \to b \in C\) je izomorfizmus \(\iff\)

  \(\exists g : b \to a \in C \ldotp \{ g \circ f = id_a \land f \circ g = id_b \}\)

• endomorfizmus

  \(f : a \to 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 \(\le\)
• 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í”

Zdroje:

Milewski, B., 2022. Category Theory for Programmers: The Preface (Part One: 1-4). [online] Bartosz Milewski’s Programming Cafe. Available at: https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ [Accessed 3 March 2022].

Buurlage, J-W, 2022. Categories and Haskell (Chapter 1). [online] Github. Available at: https://github.com/jwbuurlage/category-theory-programmers/ [Accessed 3 March 2022].