Awodey Category Theory - Chapter 1: Categories

Sep 14, 2014   #category-theory 

This is part of a series of posts of study notes from Awodey’s Category Theory book.

UPDATE: This “series” of posts never happened. For further reading I’d like to recommend:

What is Category Theory?

  • a branch of abstract algebra
  • a way of studying and characterizing different kinds of mathematical structures in terms of their “admissible transformations”
  • Historical development - applications
    • 1945 original paper “General theory of natural equivalences”
    • 40’s applications in algebraic topology
    • 50’s algebraic geometry
    • 60’s logic
    • 70’s computer science, linguistics, cognitive science, philosophy
  • kind of universal mathematical language, like set theory.
  • The notion of a category arose in order to define that of a functor, which arose to define natural transformations $\text{Category} \rightarrow \text{Functor} \rightarrow \text{Natural Transformation} \rightarrow \text{Adjunction}$
  • Functions are everywhere, and everywhere that functions are, there are categories

Functions

  • Given $f: A \rightarrow B, g: B \rightarrow C$ there is a composite function $(g \circ f)(a) = g(f(a)) a \in A $
  • composition is associative: $(h \circ g) \circ f =h \circ (g \circ f)$
  • every set A has an identity function $1_A :A \rightarrow A$ given by $1A(a) = a$
    • acts as “unit” for the operation $\circ$ of composition

Definition of Category:

  • A category consists of the DATA:
    • 1) Objects: A,B,C,…
    • 2) Arrows (or maps): f,g,h,…
    • 3) For each arrow f, there is one object as DOMAIN of f, and one object as CODOMAIN of f.
      f: $A \rightarrow B$ indicates $A = dom(f), B = cod(f)$.
    • 4) For each pair of arrows $ A \overset{\mbox{f}}{\longrightarrow} B \overset{\mbox{g}}{\longrightarrow} C$, there is a COMPOSITE map $A \overset{\mbox{$f \circ g$}}{\longrightarrow} C$.
  • satisfying the following RULES:
    • 1) IDENTITY LAWS:
      If $A \overset{\mbox{f}}{\longrightarrow} B$, then $f \circ 1_A = f = 1_B \circ f$
    • 2) ASSOCIATIVE LAW:
      If $A \overset{\mbox{f}}{\longrightarrow} B \overset{\mbox{g}}{\longrightarrow} C \overset{\mbox{h}}{\longrightarrow} D$, then $(h \circ g) \circ f = h \circ (g \circ f)$
  • a category is anything that satisfies this definition

Examples of categories

  • Sets category of sets and functions
    • $\mathbf {Sets_{fin}}$ of all finite sets and functions between them
  • Categories of structured sets and functions which preserve the structure.
    • E.g. groups and group homomorphisms, vector spaces and linear mappings, real numbers $R$ and continuous functions $R \rightarrow R$…
  • Pos of posets and monotone functions
    • A poset is a set A equipped with a binary relation $a ≤_A b$ with
      • reflexivity: $a ≤_A a$
      • transitivity: if $a ≤_A b$ and $b ≤_A c$, then $a ≤_A c$
      • antisymmetry: if $a ≤_A b$ and $b ≤_A a$, then $a = b$
    • An arrow from a poset A to a poset B is a monotone function
      • $a ≤_A a′$ implies $m(a) ≤_B m(a′)$
      • It is a category since we can show that $1_A : A \rightarrow A$ and $g \circ f : A \rightarrow C$ are monotones
  • Rel category with sets as objects and binary relations as arrows. An arrow $f : A \rightarrow B$ is a subset $f \subseteq A \times B$
    • This is the first example of non concrete category.
      • Concrete categories: their objects are sets, their arrows are certain, possibly structure-preserving functions.
    • identity: $1_A =\{ (a,a) \in A×A \vert a \in A \} \subseteq A×A$.
    • composition: if $ R \subseteq A × B$ and $S \subseteq B \times C$, then $(a,c) \in S \circ R$ iff $ \exists b . (a,b) \in R$ & $ (b,c) \in S$
  • Finite categories
    • 1 category has one object and its identity arrow
    • 2 category has two objects, their identity arrows and exactly one arrow between the objects.
  • Cat the category of all categories and functors. (so meta!)
    • A functor $F:C \rightarrow D$ between categories $C$ and $D$ is a mapping of objects to objects and arrows to arrows so that
      • $F(f :A \rightarrow B)=F(f):F(A) \rightarrow F(B)$
      • $F(g \circ f)=F(g) \circ F(f)$
      • $F(1_A)=1_F(A)$
  • Any preorder P can be regarded as a category by taking the objects to be the elements of P and taking a unique arrow $a \rightarrow b iff a \le b$
    • A preorder is a set P equipped with a binary relation p ≤ q that is
      • reflexive: $a≤a$
      • transitive: if $a≤b$ and $b≤c$ then $a≤c$
  • A poset is a a category.
    • It is a preorder, with the additional condition of antisymmetry: $if a ≤ b$ and $b ≤ a$, then $a = b$.
  • Given a deductive system of logic, there’s an associated category where
    • the objects are formulas
    • an arrow from φ to ψ is a deduction of ψ from the assumption φ.
  • Given a functional programming language L, there is a category where
    • the objects are the data types of L
    • the arrows are the computable functions of L.
    • composition of two programs is given by applying g to the output of f.
    • the identity is the “do nothing” program.
    • the denotational semantics of the language L in a category D of Scott domains is a functor $S : C(L) \rightarrow D$, where $C(L)${find} is the category just defined.
  • Given a set X, Dis(X) is the category where
    • objects are the elements of X
    • arrows are just the identity arrows.
    • such categories are called discrete. They are very special posets.
  • Monoids
    • Classical definition:
      • A monoid is a set M equipped with:
      • a binary operation $· : M × M \rightarrow M$
      • and a “unit” element $u ∈ M$
      • such that for all $x,y,z ∈ M$
        • $x · (y · z) = (x · y) · z$ (associativity)
        • $u·x = x = x·u$ (unit)
      • For example the Natural Numbers form a monoid under addition, whose unit element is 0.
    • Category theoretical definition:
      • A monoid is a category with exactly one object.
      • Explanation:
        • Suppose we have only one object, which we call ‘*‘. This means that all the maps in the category are endomaps (from this object to iself). Nevertheless, there maybe many maps in this category. Suppose that as maps we take all natural numbers: 0 is a map, 1 is a map, 2 is a map. They all are maps from * to *.
          * $\overset{\mbox{1}}{\longrightarrow}$ *, * $\overset{\mbox{2}}{\longrightarrow}$ *
        • Let’s take as composition for this category addition.
        • The composite of two numbers is their sum: $ m \circ n = m+n$.
        • As identity we choose 0.
        • If we take as the only object * of the category to be the set $N$ of natural numbers, each map of the category is a map from the set of natural numbers to itself $N \overset{\mbox{ $f_n$ }}{\longrightarrow} N$ defined by
          • $f_n(x) = n + x$.
          • Thus $f_3(x) = 3 + x$.
        • Identity: $f0 = 1*$
        • Composition: $f_n \circ fm = f{n+m}$
        • Two different points of view to integers: Instead of viewing it as a set containing various members with a single binary operator, we see it as an unstructured blob, with a collection of unary operations applying to it.
  • Mon : category whose objects are monoids and whose arrows are functions that preserve the monoid structure.
    • a homomorphism from a monoid M to a monoid N is a function $h : M \rightarrow N$ such that for all $m,n ∈ M$
      • $h(m ·_M n) = h(m) ·_N h(n)$ and
      • $h(u_M ) = u_N$

Isomorphisms

  • In any category C, an arrow $f : A \rightarrow B $ is called an isomorphism if there is an arrow $g : B \rightarrow A$ in $C$ such that $g \circ f=1_A$ and $f \circ g=1_B$
  • $g = f^{-1}$
  • We say A is isomorphic to B: A ≅ B
  • A group G is a monoid with an inverse $g^{-1}$ for every element g.
    • Thus G is a category with one object, in which every arrow is an isomorphism.
    • The natural numbers do not form a group under either addition or multiplication.
      • (why?)
        Assuming 0 is part of the natural numbers, and that it is the identity for addition, they still don’t form a group because they don’t have inverses, except for 0.
  • Automorphism: an isomorphism from an object to itself (or permutation).
  • Aut(X) (automorphism group) is the set of all automorphisms of an object.
  • A group of permutations is a subgroup G ⊆ Aut(X) for some set X. G must satisfy:
    • $1_x \in G$
    • If $g, g’ \in G$, then $g \circ g’ \in G$
    • If $g \in G$ then $g^{-1} \in G$
  • Theorem (Cayley): Every group G is isomorphic to a group of permutations.
    • it means any abstract group can be represented as a “concrete” one.
  • Theorem: Every category C with a set of arrows is isomorphic to one in which the objects are sets and the arrows are functions.

Constructions on categories

  • product of two categories C and D, C×D
    • has objects $(C,D)$, for $C ∈ C$ and $D ∈ D$
    • and arrows $(f,g) : (C,D) \rightarrow (C′,D′)$ for $f : C \rightarrow C′ ∈ C$ and $g : D \rightarrow D′ ∈ D$
    • there are two obvious projection functors: $C \overset{\mbox{π1}}{\longleftarrow} C×D \overset{\mbox{π2}}{\longrightarrow} D$
  • opposite (or dual) category $\mathbf {C^{op}}$ of a category C
    • has the same objects as C with all the arrows turned around; an arrow $C \rightarrow D$ in $\mathbf {C^{op}}$ is an arrow $f: D \rightarrow C$ in $C$.
  • arrow category $\mathbf{C^{→}}$ of a category C
    • has the arrows of C as objects
    • an arrow g from $f : A \rightarrow B$ to $f′ : A′ \rightarrow B′$ in $C^{→}$ is a pair of arrows $ g(g_1, g_2) $ in C such that $ g2 \circ f=f′ \circ g_1 $
  • The slice category C/C of a category C over an object C∈C has:
    • objects: all arrows $f \in C$ such that $cod(f) = C$
    • arrows: g from $f : X \rightarrow C$ to $f′ : X′ \rightarrow C$ is an arrow $g : X \rightarrow X′$ in C such that $f′ \circ g = f$, as indicated in
    • if C = P is a poset and p ∈ P, then P/p ∼= ↓(p)
      • the slice category P/p is just the “pricipal ideal” ↓(p) of elements q ∈ P with q ≤ p.

Free Categories

  • Free monoid
    • “alphabet” A of “letters” (a set) $A = \{a, b, c, ..\}$
    • A word over A is a finite sequence of letters.
    • ”-” is the empty word.
    • The Kleene closure is: $A^*$ = {words over A}
    • Let “*” be the concatenation
      • for $w, w’ \in A^*$, $w*w’ = ww’$
      • * is associative, the empty word “-” is unit. Thus $A^*$ is a monoid.
      • Called the free monoid on the set A.
    • Why is it called “free”?
      • Baby algebra definition:
        • A monoid M is freely generated by a subset A of M if:
          • every element e $\in$ M can be written as a product of elements of A. (no junk)
          • No non-trivial relations hold in M. (no noise)
        • Category theoretical definition:
          • The free monoid M(A) on a set A is “the” monoid with the Universal Mapping property.
    • Universal Mapping Property of M(A)
    • There’s a function $i: A \rightarrow \lvert M(A)\rvert$ and given any monoid N and any function $f : A \rightarrow \lvert N \rvert $, there s a unique monoid homomorphism $ \bar f : M(A) \rightarrow N $ such that $ \lvert \bar f \rvert \circ i = f $
    • $(A^*, *)$ has the UMP of the free monoid on A.
  • Free category
    • Categories have underlying graphs instead of underlying sets.
    • Graphs consist of the set $E$ (edges), $V$ (vertices), functions $ s : E \rightarrow V $ (source) and $ t : E \rightarrow V $ (target).
    • Every graph G “generates” a category $ C (G) $, the free category on G, defined by taking the vertices of G as objects and the paths in G as arrows.
    • Define a forgetful functor $ U : Cat \rightarrow Graphs $ as the underlying graph of a category C which has as edges the objects of C, and as vertices the arrows.
    • the free category on a graph has the following UMP:
    • Universal Mapping Property of C(G)
      • There is a graph homomorphism $ i : G \rightarrow \lvert C (G) \rvert $, and given any category D and any graph homomorphism $h : G \rightarrow \lvert D \rvert$, there is a unique functor $ \bar h : C (G) \rightarrow D $ with $ \lvert \bar h \rvert \circ i = h $.

Foundations

  • We distinguish between
    • categorical foundations for mathematics
      • category theory can be used to provide foundations for mathematics as an alternative to set theory. But it is not what we are doing here.
    • mathematical foundations for category theory.
      • we assume our categories are comprised of sets and functions.
      • we some times run into difficulties of size
        • some categories are “too big” to be handled in conventional set theory.
  • A category C is called small if both the collection $C_0$ of objects of C and the collection $C_1$ of arrows of C are sets. Otherwise, C is called large.
  • We let Cat be the category of all small categories, which itself is a large category.
  • A category C is called locally small if for any objects X, Y in C,the collection $ Hom_C(X,Y)= \{ f \in C_1 \lvert f:X \rightarrow Y \} $ is a set (called a hom-set).