Math and science::Algebra::Aluffi
Category Theory. Essence of associative composition.
Morphisms of a category obey the following two properties:
- Composition
- For any objects , there is a function
[].
-
- Associativity
- For any morphisms , [...].
Composition and the question of a category's datum
Are functions between sets of morphisms part of the datum of a category? Or are the sets of morphisms sufficient themselves, and there is simply a requirement that a function between the sets must be possible?
I'm not sure whether is part of the datum of a category. A second phrasing of the composition property suggests that the functions are a datum of a category:
For any two morphisms and
of category there is a morphism
. Write [...] as notation to represent .
The notation to represent the composition of and picks out a specific element of , but this would not be possible if there isn't a specific function decided (maybe there are many possible functions).
Which of the two formulations is the true formulation is not just a question
of conceptual framing. If the function
is
part of the datum of a category, then two categories could be considered
different by having different compositional mapping and , both
of the form , while having the same sets of morphisms.
Directed graphs as a model of a category
A directed graph is the best visual model I have found so far to represent
the two above properties of morphisms. Nodes represent objects and edges represent morphisms. Composition and composition associativity place two restrictions on what graphs represent valid categories.
Composition
The composition property applied to a directed graph asserts that every
pair
of directed edges that form a 2-edge path from [...] to [...] via [...]
must correspond to a 1-edge path from [...] to [...]. Thus, the former pair asserts the existance of the latter, and there is a function (possibly part of the category datum) that describes this mapping.
Associativity
A 4 node graph is required to demonstrate the associativity of composition.
In the graph below, there are many edges (morphisms) between the nodes. Pick out four edges and . The naming indicates which set of morphim they belong to,
for example, .
To demonstrate associativity of composition, first we introduce two 2-edge paths: and . Each 2-edge path represents a pair in a product space such as []. By composition of morphisms, each of these 2-edge paths have a correspondence with a 1-edge path; one is from
to and one from to .
2-edge path,
The morphism pair must map to a morphism in
, which we will denote as . This mapping is
done through a function
[]. The preimage might contain many pairs
of edges from and , or it could contain just the pair .
2-edge path,
In a similar way, let be the morphism in
which is the image of the morphism pair through the
function .
Associativity. Essence.
It is not possible for two different compound paths between the same nodes to have exactly the same 1-edge 'building blocks'. This is a phrase that tries to express the nature of composition associativity in a manner that appeals to intuition. A more concrete description follows.
Let
and be mappings
between sets of morphisms. These represent the correspondence from (the two sets of paths from which include one of the red edges) to (the set of 1-edge paths from ). If and , then associativity of composition asserts that
. In otherwords, the 2-edge path from to via
and the 2-edge path from to via must map to
the same 1-edge path from to . This is so as both of these paths have a preimage through and respectively which 'unfold' as the same ordered 3-tuple .
The word 'unfold' in the previous sentence does a lot of heavy lifting. The edge
might be one of many edge in . However, if, following
recursively back through preimages 'touch' a path tuple, such as
, then no other edge in
can 'touch' this tuple, no matter how the morphism mappings are recursively
passed through.