Exercise about map of graph in "Conceptual Mathematics"

Question

I'm reading the Lawvere and Schanuel's "Conceptual mathematics", and could't solve both (a) and (b) of Exercise 8.

What I understood is below.

In a category of graph, an object is a graph, and a map is from graph to graph. Below image is a map $(f_A, f_D)$ of graph from $(X, Y, s, t)$ to $(X^{'}, Y^{'}, s^{'}, t^{'})$. In this map, $f_D s = s^{'} f_A$ and $f_D t = t^{'} f_A$ hold.

Suppose in graph $G$, $x$ represent any arrows(edges) whose source is $b$, and $y$ represent any arrows(edges) whose target is $e$. According to $f_D s = s^{'} f_A$, $f_D t = t^{'} f_A$, $f_D(b)=0$, and $f_D(e)=1$, I could show $s^{'}f_A(x)=0$ and $t^{'}f_A(y)=1$. So in graph $J$, $f_A(x)$ is equal to the arrow from 0, and $f_A(y)$ is equal to the arrow to 1.

Please give me advice to prove (a) and (b) of Exercise 8.

Answer 1

a) Let $b=a_0,a_1,\dots, a_n=e$ be (the vertices of) a path $b\leadsto e$ in $G$, and assume $f:G\to J$ is any map of the vertices of $G$ such that $f(b) =0$ and $f(e) =1$.
Then $f$ can't extend to a graph morphism: take the least index $k$ such that $f(a_k) =1$. Then $k>1$ and $f(a_{k-1}) =0$, and $G$ has an edge $a_{k-1}\to a_k$ but $J$ doesn't have an edge $0=f(a_{k-1})\to f(a_k) =1$.

b) Suppose $G$ has no path $b\leadsto e$, and let $E$ be the set of vertices from which there is a path to $e$, and let $B$ be the rest. We include the path of zero length as well, so that $e\in E$ and $b\in B$.
Note that for $p\in B$ and $q\in E$, there's a path $q\leadsto e$, so there can't be any path $p\leadsto q$, in particular $G$ has no edge $p\to q$.
Map now every vertex in $B$ to $0$ and every vertex in $E$ to $1$, and check that it yields a graph homomorphism $G\to J$.

Answer 2

$J$ is the graph-category with $A_J = \{l_0, l_1, 10\}$, say, and $D_J = \{0,1\}$ and $s_J,t_J : A_J \to D_J$ defined by $s_J(l_0) = 0$, $s_J(l_1) = 1= s_J(10)$ and $t_J(l_0) = 0 = t_J(10)$ and $t_J(l_1)= 1$.

The book does not exactly define what a path from $b$ to $e$ actually means (it's more general than just an arrow from $b$ to $e$) but there is a standard notion from graph theory that I can translate to this category context:

A path in $G=(A_G,D_G;s_G,t_G: A_G \to D_G)$ from $b$ to $e$ (where $b,e \in D_G$) is a finite set of arrows $\alpha_1, \ldots \alpha_n$ for some $n \ge 1$ such that

• $s_G(\alpha_1) = b$ (the first arrow starts at $b$),
• $t_G(\alpha_n) = e$ (the last arrow ends at $e$),
• for all $1\le i \le n-1$ we have $t_G(\alpha_i) = s_G(\alpha_{i+1})$ (the next arrow starts where the previous one ended).

Now, consider what happens to the path if I take the images of the $\alpha_i$ under $f_A$, where $f=(f_A,f_D)$ is a graph-arrow between $G$ and the above $J$, that obeys $f_D(b)=0$ and $f_D(e) = 1$:

$$s_J(f_A(\alpha_1)) = f_D(s_G(\alpha_1)) = f_D(b)=0$$

and as in $J$ we have the following fact (seen by inspection)

$$\forall x \in A_J: s_J(x)=0 \rightarrow x=l_0$$

we conclude that $f_A(\alpha_1) = l_0$.

If $n=1$ we would have a contradiction, as $$t_J(f_A(\alpha_n)) = f_D(t_G(\alpha_n)) = f_D(e) = 1$$ while $t_J(f_A(\alpha_1)) = t_J(l_0) = 0$.

And next we see (using what we already know, the arrow properties and the path property):

$$0 = t_J(l_0) = t_J(f_A(\alpha_1)) = f_D(t_G(\alpha_1)) = f_D(s_G(\alpha_2))= s_J(f_A(\alpha_2))$$

and again we conclude from the same property for $J$ that $f_A(\alpha_2)) = l_0$.

Now show yourself that $n$ cannot be $2$ (by looking at $e$ again, as before), and then conclude that $f_A(\alpha_2) = l_0$ again. So in finitely many steps we always get a contradiction. Alternatively, prove by induction on $n$ that there is no path from $b$ to $e$ in $n$ steps.

Intuitively it's clear that this should hold, but it's a bit of a hassle to prove formally.