ExpandCollapseNext Index

\(\DeclareMathOperator{\obj}{obj}\ \DeclareMathOperator{\arr}{arr}\ \DeclareMathOperator{\dom}{dom}\ \DeclareMathOperator{\cod}{cod}\)

+ 1.1 Categories

+ 1.1.1 Definition

A category \(K\) is a collection of objects \[O = \obj K\] and arrows \[A = \arr K\] with the following data:

  1. Each arrow \(f\in A\) has a specified domain object \(\dom f = D\in O\) and codomain object \(\cod f = C\in O\) which is noted by stating \[f:D\rightarrow C\]
  2. if \(f:A\rightarrow B\) and \(g:B\rightarrow C\) then there is a designated composite arrow \[h:A\rightarrow C = f \cdot g = g \circ f\]
  3. Given an object \(A\) there is a designated identity arrow \[1_A:A\rightarrow A\]
Satisfying the following laws:
  1. Identity Law: If \(f:A\rightarrow B\) then \[f \cdot 1_B = f\] and \[ 1_A \cdot f = f\]
  2. Associative Law: If \(f:A\rightarrow B\), \(g:B\rightarrow C\) and \(h:C\rightarrow D\) then \[ f\cdot (g \cdot h) = (f \cdot g) \cdot h : A \rightarrow D \]
Note that \(g \circ f = f \cdot g\), the LHS is the usual forward composition but the RHS reverse composition is much better for category theory, since it follows arrows from source to destination. It is also the most familiar to those used to OO notation.

+ 1.1.2 Example: Sets

The easiest example is the category \(\bf Set\) of all sets and all functions between them.

A smaller example is any collection of sets, together with a set of functions on them closed under composition (and including identities for each set of course).

+ 1.1.3 Example: Types

Related to sets, the category \(\bf Type\) of all types in a decent programming language and functions between them. You can think of a type as a set of values, and a function as the semantics of the an encoding of a function in the language. Don't confuse the categorical arrow, however, with the encoding: two distinct encodings of a function are equal is they have the same semantics.

+ 1.2 Subcategories

A subcategory \(S\) of a category \(K\) is any subset of objects and arrows which is itself a category. In particular each object must have its identity arrow, and be closed under composition.

+ 1.2.1 Example: Discrete category

A category with only identity arrows.

+ 1.2.2 Example

Let the objects be all sets and draw and arrow from \(A\) to \(B\) if \(A\) is a subset of or equal to \(B\). This is a category, and a subcategory of \(\bf Set\), however without the equality there would be no identity arrows, so proper subset relations don't form a category.

+ 1.2.3 Category generated by a graph

For any directed graph \(G\) take the vertices as objects and the edges as arrows together with an arrow from every vertex to itself designated the identity for that vertex. Then we can take the joining of paths as composition, and the result is called the category generated by the graph.

Note in this example, arrows are not necessarily functions, nor are the objects sets or types.

+ 1.2.4 Example: Strings

A category generated from one graph with one (irrelevant) object and arrows labelled with letters \(\Sigma\), plus one unlabelled arrow which is the identity, is the category of words in those letters, with arrow composition being string concatenation. Usually written \(\Sigma^*\).

Any finite automaton, both deterministic and non-deterministic, generates a subcateory of strings, since it just a graph, and it follows regular expressions also form a category.