Multiplication:composition::monoid:category

The last example in the previous post was the monoid consisting of all functions from a set T to itself under composition. We could multiply the elements (i.e. compose them) in any order because the source and the target were the same, the set T.

\displaystyle \stackrel{T}{\mathop{\circlearrowleft}_f}

For arbitrary sets, we still know how to compose, but we have some restrictions on what functions are composable: the target of the first has to match the source of the second. Given f:T\to U and g:U\to V, we can compose them:

\displaystyle T \stackrel{f}{\to} U \stackrel{g}{\to} V.

So where multiplication had to start and end at the same place, composition can wander around.

Just as the essence of a monoid is multiplication, the essence of a category is composition.

A category consists of

  • a collection of objects and
  • for each pair of objects x,y a set {\rm hom}(x,y) of morphisms or arrows from x to y (if f \in {\rm hom}(x,y), we write f:x\to y)

such that

  • for every object x there is a morphism 1_x:x\to x,
  • for every triple of objects x,y,z and pair of morphisms f:x\to y, g:y\to z there is a composite morphism

    g\circ f:x\to z,

    and

  • composition is associative

    (h \circ g) \circ f = h \circ (g \circ f)

  • and obeys the left- and right-unit laws

    f \circ 1_x = f = 1_y \circ f.

One simple structure on which something can wander is a directed graph. It has vertices and directed edges between them. We can’t compose two edges and get a new edge, but we can compose two paths and get a new path. Every directed graph gives rise to a category whose objects are the vertices of the graph and whose morphisms are paths in the graph, including “identity paths” that start and end at the same point without going anywhere in between.

Whereas a graph is discrete, a manifold (like a circle or Euclidean space) is continuous. Any manifold gives rise to a category whose objects are the points of the space and whose morphisms are paths between them.

Here are more examples of categories:

1. The empty category:

  • no objects
  • no morphisms

2. The category “1″:

  • one object T
  • one trivial morphism 1_T:T\to T

3. The category “2″:

  • two objects S, T
  • the trivial morphisms 1_S, 1_T and one nontrivial morphism a:S\to T

4. The category Set of all sets:

  • objects are sets
  • morphisms are functions
  • For example, S = {1,2} and T = {purple, green, yellow} are two objects in Set, and the function f:S\to T, where f(1) ={\rm purple} and f(2)={\rm green}, is a morphism in {\rm hom}(S,T).

5. Any monoid “is” a one-object category:

  • one object T
  • the set of morphisms from T to itself is equipped with extra structure that makes it a monoid. We define the category in terms of the monoid as follows:
    • {\rm hom}(T,T):= S
    • 1_T:= e(\bullet)
    • b \circ a := m(a,b)

For example, the real numbers under multiplication form a monoid, so we get a category where

  • there’s one object T, and
  • {\rm hom}(T,T) = \mathbb{R}.
  • Given r, s \in \mathbb{R}, we compose them by multiplying them:

    T \stackrel{r}{\to} T \stackrel{s}{\to} T = T \stackrel{sr}{\to} T

Note: T could be anything, as long as it makes sense to multiply it by a real number.

For example, T could be the set of scalings of a picture of a dog. Then a morphism from T to itself would be a function, since functions are the things that go between sets, and the function would be parameterized by a real number r \in \mathbb{R}. We define

f_r(t) = the picture t scaled by a factor r, and

(f_s \circ f_r)(t) = f_s(f_r(t)) = f_{rs}(t).

The identity morphism in this case is

1_T(t) = f_1(t) = t.

Or, T could be the lone dot in a one-dot graph with infinitely many self-loops, each labelled with a real number. We then say the weight of a path on the graph is the product of the loop labels. The identity morphism is the self-loop labelled with the number 1.

6. Any collection of algebraic gadgets and the structure-preserving maps between them. For example, a ring is an algebraic gadget with two monoids that work together:

  • there’s a set S
  • two different special points, or identities: the multiplicative identity e_{\cdot}(\bullet) = 1 and the additive identity e_+(\bullet) = 0
  • two different associative binary operations
    • multiplication:

      (ab)c = a(bc)

    • addition, which is also commutative:

      (a+b)+c = a+(b+c)
      a+b=b+a

  • multiplication distributes over addition:

    a(b+c) = ab + ac

There is a category Ring consisting of all rings and maps between them that preserve the ring structure.

  • objects: rings
  • morphisms: ring homomorphisms
    • A ring homomorphism F:R_1 \to R_2 is a map between rings that preserves the ring structure: identities, multiplication and addition. That is, it doesn’t matter which way you go around the squares below; the answer will be the same either way:

      \begin{array}{ccc}R_1 \times R_1 & \stackrel{F \times F}{\to} & R_2 \times R_2\\ \cdot_1 \downarrow & & \downarrow \cdot_2 \\ R_1 & \stackrel{F}{\to} & R_2\end{array}

      \vspace{0.5in}

      \begin{array}{ccc}R_1 \times R_1 & \stackrel{F \times F}{\to} & R_2 \times R_2\\ +_1 \downarrow & & \downarrow +_2 \\ R_1 & \stackrel{F}{\to} & R_2\end{array}

    • For example, the ring of integers \mathbb{Z} is an object in Ring, as is the ring \mathbb{Z}_2 (where \mathbb{Z}_n denotes integers modulo n). The set {\hom}(\mathbb{Z}, \mathbb{Z}_2) = \{ 0, p \}, where 0 is the ring homomorphism that takes all integers to zero and p is the map that takes each integer to its remainder modulo 2.

      \begin{array}{ccc}(-4, 7) & \stackrel{p \times p}{\mapsto} & (0, 1) \\ \cdot \downarrow & & \downarrow \cdot_2 \\ -28 & \stackrel{p}{\mapsto} & 0\end{array}

      \vspace{0.5in}

      \begin{array}{ccc}(-4, 7) & \stackrel{p \times p}{\mapsto} & (0, 1)\\ + \downarrow & & \downarrow +_2 \\ 3 & \stackrel{p}{\mapsto} & 1\end{array}

This entry was written by reperiendi and posted on 2007 September 12 at 1:35 pm and filed under Category theory, Math. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.

Post a Comment

You must be logged in to post a comment.