#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Exercise 8 - Chapter 3

edited June 2018

For $$\textbf{Free}(G)$$ to really be a category, we must check that this data we specified obeys the unitality and associativity properties. Check that these obeyed.

Definition 3.2. To specify a $$\textit{category C}$$:

(i) one specifies a collection $$Ob(\textit{C})$$, elements of which are called $$\textit{objects}$$.

(ii) for every two objects $$c, d$$, one specifies a set $$C(c, d)$$, elements of which are called $$\textit{morphisms}$$ from $$c$$ to $$d$$.

(iii) for every object $$c \in Ob(C)$$, one specifies a morphism $$id_c \in C(c, c)$$, called the $$\textit{identity morphism}$$ on $$c$$.

(iv) for every three objects $$c, d, e \in Ob(C)$$ and morphisms $$f \in C(c, d)$$ and $$g \in C(d, e)$$, one specifies a morphism $$f.g \in C(c, e)$$, called the composite of $$f$$ and $$g$$.

It is convenient to denote elements $$f \in C(c, d)$$ as $$f : c \rightarrow d$$. Here, $$c$$ is called the $$\textit{domain}$$ of $$f$$, and $$d$$ is called the $$\textit{codomain}$$ of $$f$$.

These constituents are required to satisfy two conditions:

(a) unitality: for any morphism $$f : c \rightarrow d$$, composing with the identities at $$c$$ or $$d$$ does nothing: $$id_c . f = f \text{ and } f . id_d = f$$.

(b) associativity: for any three morphisms $$f : c_0 \rightarrow c_1 , g : c_1 \rightarrow c_2 , \text{ and } h : c_2 \rightarrow c_3$$, the following are then equal: $$( f . g) . h = f . (g . h )$$. We can write it simply as $$f.g.h$$.

• Options
1.
edited August 2018

According to the text leading up to exercise 8 (in Seven Sketches), $$\textrm{Ob}(\textbf{Free}(G))=V$$, and the morphisms are paths (i.e., possibly infinite lists of arrows $$a,b,c\ldots{}\in A$$ such that $$t(a)=s(b)$$, $$t(b)=s(c)\ldots$$), including paths of length zero, i.e., identity arrows. Where $$V$$ is the set of vertices of the graph, $$A$$ is the set of arrows (directed edges, including loops from a vertex to itself), and $$s,t:A\to V$$ are the source and target maps.

a) Composing an arrow $$f:c\to d$$ with the identity on either side yields a path of the same length, one, containing equivalent arrows in the same order. Since paths are lists of arrows with matching sources and targets, where identity arrows can be omitted, $$\mathrm{id}_d\circ f$$, $$f$$, and $$f\circ\mathrm{id}_c$$ all yield the same/equivalent path(s), and so the morphisms are equal.

b) Since paths, i.e., lists of arrows, are associative (i.e., $$(ab)c=a(bc)$$), morphisms are also. This is because morphisms are equivalence classes of paths, where paths with or without identity arrows are considered equivalent (and one makes only this identification), and associativity of paths is respected by this equivalence (e.g., $$(h\circ g)\circ (f\circ \mathrm{id}_{c_0})$$ $$=(h\circ g)\circ f=h\circ (g\circ f)$$ yields the same thing as $$(h\circ g)\circ (f\circ \mathrm{id}_{ c_0})$$ $$=h\circ (g\circ(f\circ\mathrm{id}_{c_0}))$$ $$=h\circ (g\circ f$$).

Edit: This can be seen as a consequence of the commutativity of a certain diagram corresponding to the equation: $$\alpha\circ\sim=\sim\circ\alpha$$, where $$\alpha$$ serves to switch the position of parentheses and $$\sim$$ identifies paths differing only by identity arrows.

Comment Source:According to the text leading up to exercise 8 (in Seven Sketches), \$$\textrm{Ob}(\textbf{Free}(G))=V\$$, and the morphisms are paths (i.e., possibly infinite lists of arrows \$$a,b,c\ldots{}\in A\$$ such that \$$t(a)=s(b)\$$, \$$t(b)=s(c)\ldots\$$), including paths of length zero, i.e., identity arrows. Where \$$V\$$ is the set of vertices of the graph, \$$A\$$ is the set of arrows (directed edges, including loops from a vertex to itself), and \$$s,t:A\to V\$$ are the source and target maps. a) Composing an arrow \$$f:c\to d\$$ with the identity on either side yields a path of the same length, one, containing equivalent arrows in the same order. Since paths are lists of arrows with matching sources and targets, where identity arrows can be omitted, \$$\mathrm{id}_d\circ f\$$, \$$f\$$, and \$$f\circ\mathrm{id}_c\$$ all yield the same/equivalent path(s), and so the morphisms are equal. b) Since paths, i.e., lists of arrows, are associative (i.e., \$$(ab)c=a(bc)\$$), morphisms are also. This is because morphisms are equivalence classes of paths, where paths with or without identity arrows are considered equivalent (and one makes only this identification), and associativity of paths is respected by this equivalence (e.g., \$$(h\circ g)\circ (f\circ \mathrm{id}\_{c_0})\$$ \$$=(h\circ g)\circ f=h\circ (g\circ f)\$$ yields the same thing as \$$(h\circ g)\circ (f\circ \mathrm{id}\_{ c_0})\$$ \$$=h\circ (g\circ(f\circ\mathrm{id}\_{c_0}))\$$ \$$=h\circ (g\circ f\$$). Edit: This can be seen as a consequence of the commutativity of a certain diagram corresponding to the equation: \$$\alpha\circ\sim=\sim\circ\alpha\$$, where \$$\alpha\$$ serves to switch the position of parentheses and \$$\sim\$$ identifies paths differing only by identity arrows.