# $A \times A = A + D +D$ in category of irreflexive graphs

In p.223 of Conceptual Mathematics, 2nd ed., by Lawvere and Schanuel, Exercise 21 asks:

If $A, D$ denote the generic arrow and the naked dot in $S^{\Downarrow}$, show that

$$A \times A = A + D +D$$

Hint: Besides counting the arrows and dots of an arbitrary graph $X$ (such as $X = A \times A$) via maps $A \rightarrow X$, $D \rightarrow X$, the actual internal structure of $X$ can be calculated by composing these maps with the two maps $s,t: D \rightarrow A$.

For context:

$S^{\Downarrow}$ is the category of irreflexive graphs, whose objects are two sets $X$ (the set of arrows) and $P$ (the set of points) with maps $source: X \rightarrow P$ and $target: X \rightarrow P$. A map between graphs is a structure-preserving morphism with respect to these two graphs.

$A$ the generic arrow is the graph that looks like * -> *.

$D$ the naked dot is the graph that looks like *.

This problem appears in the section for the distributive law which states the following maps are isomorphisms:

$$(A \times B) + (A \times C) \rightarrow A \times (B + C)$$ $$0 \rightarrow A \times 0$$

My interpretation of the hint is that any graph map $A \rightarrow X$ is equivalent to a graph map $D \rightarrow X$ defined as the arrow map pre-composed with either the $s$ or $t$ map, since every arrow must have either a source or target. Beyond that I have been having trouble figuring this out.. I assume the use of the distributive law is needed at some point.. maybe using something like

$$A \times A = A \times (A + 0)$$

or

$$A + D + D = A + (D \times (1 + 1))$$

Any guidance would be appreciated.

Call $a,b$ the vertices of $A$, i.e. $A$ is the graph $a\to b$.

Then the vertices of $A\times A$ are $(a,a),\ (a,b),\ (b,a),\ (b,b)$, and we have only one arrow $(a,a)\to (b,b)$ and thus $(a,b)$ and $(b,a)$ are isolated points.

We can formulate then a proof according to the hint, purely categorically, as follows:

We have to prove that $B:= A+D+D$ (depicted as $\left[\matrix{a&d_1\\d_2&b}\right]$ with an arrow $a\to b$) is a product of $A$ and $A$.

Consider the graph homomorphisms $\pi_1:a,d_1\mapsto a;\ d_2,b\mapsto b$ and $\pi_2:a,d_2\mapsto a;\ d_1,b\mapsto b$, and prove the universal property.

• Ahh that's interesting and certainly makes sense. I am curious how one can formulate this answer in terms of the distributive law? May 14, 2017 at 22:54
• I'm not sure the distributive law is used here (maybe this will be needed in proving that). But you still have some work to prove the universal property plainly by following the hint.. May 14, 2017 at 22:59
• Hmm alright, you've certainly given me a good starting point. Will think through proving the universal property, thanks! May 14, 2017 at 23:09
• Alright so I think I have it. There are 4 maps $D \rightarrow A \times A$, namely $\{<s, t>, <s, s>, <t, s>, <t, t> \}$. These maps correspond to mapping $D$ to $d_{1}$, $a$, $d_{2}$, and $b$, respectively. From there any pair of graph maps $f,g: G \rightarrow A$ can be translated into maps into $A + D + D$ by seeing how each dot of $G$ is mapped by $f$ and $g$ (e.g. to the source or target of each $A$) and using the appropriate map $D \rightarrow A + D + D$ shown above. Is that right? May 15, 2017 at 1:44