Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Usually I look at a category as a digraph with an associative (partial) binary function $\circ$ on its arrows.1 When regarding commutative diagrams I look at a category as a digraph with an equivalence relation $\simeq$ on its paths. Just like the function $\circ$ has to be associative, the equivalence relation $\simeq$ has to fulfill a condition – to be considered "categorical" or "commutative".

I guess (but I may be wrong) that this condition simply is:

An equivalence relation $\simeq$ on the paths of a digraph $G$ is commutative when there is an associative binary function $\circ$ on its arrows such that2

$ \qquad G \models p_1 + \dots + p_n \simeq q_1 + \dots + q_m$

$ \qquad\qquad\qquad$if and only if

$ \qquad G \models p_1 \circ \dots\circ p_n = q_1 \circ \dots \circ q_m$

i.e. when $\simeq$ is (naturally?) induced by an associative function $\circ$.

What I'd like to know:

How can commutative equivalence relations on the paths of a digraph be characterized, i.e. which of their necessary properties are sufficient?

Consider the following properties that commutative equivalence relations – as defined above – must have by definition:3

(1) $ \qquad |p|=|q|=1 \qquad\qquad\qquad\quad\ \ \Rightarrow \big(\exists\ r\ : |r| = 1 \wedge p + q \simeq r\big)$

(2) $ \qquad |p|=|q|=1 \qquad\qquad\qquad\quad\ \ \Rightarrow \big( p \simeq q \Leftrightarrow p = q \big)$

(3) $ \qquad |p|=|q|=|r|=1 \qquad\qquad\quad \Rightarrow \big( p \simeq q \Rightarrow p + r \simeq q + r \big)$

(3') $ \qquad |p|=|q|=|r|=1 \qquad\qquad\quad \Rightarrow \big( p \simeq q \Rightarrow r + p \simeq r + q\big)$

(4) $ \qquad |p|=|q|=|q'| = |r|= |r'|= 1 \Rightarrow \big( q + p \simeq r \wedge p + q' \simeq r' \Rightarrow q + r' \simeq r + q'\big)$

Note that equivalence relations with properties (3) and (3') are known as congruences in the literature (see Awodey and Spivak).

Note that (4) is an explicit expression of the associativity of $\circ$ in terms of $\simeq$.

So my main question is:

Are the properties (1) to (4) – eventually – sufficient to characterize commutative equivalence relations?

If not so: what is missing?

More of a side question is:

(Under which conditions) can the preconditions of properties (3) to (4) – requiring that the paths involved be arrows – be dropped, i.e., the conclusions hold for all paths, not only for arrows (which seems true at blue-eyed first sight)?

1 The bookkeeping details concerning source and target of both arrows and paths and their composites are tacitly assumed.
2 Let $+$ be the (associative) path concatenation operator.
3 Let $|p|$ be the length of the path $p$, so $|p|=1$ means that $p$ is an arrow.

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.