What are the functions of a graph in relation to arrow composition?

[Math Amateur]

I am reading Steve Awodey's book of category theory.

I am, at the moment, studying Section 1.7 on free categories and graphs ...

Under the heading Free Categories on page 20 we have the following text:

View attachment 2551
View attachment 2550

I am struggling to get a clear picture of the two functions of a graph, namely:

\(\displaystyle s : \ E \to V \) (source)

\(\displaystyle t : \ E \to V \) (target)

In relation to the arrow \(\displaystyle e_n e_{n-1} ... e_1 \) of C(G) ... is the following correct?

\(\displaystyle s(e_1) = v_0 \)

\(\displaystyle t(e_n) = v_n \)

Are these two equations correct? So then is it the case (sounds strange) that the domain and codomain of an arrow or morphism is one element? (with functions on sets a domain or a codomain are sets?)

Peter

 

[Deveno]

Lets look at a very simple graph:

$v_1 \stackrel{e_1}{\to} v_2$

Here. $V = \{v_1,v_2\}$, and $E = \{e_1\}$.

It follows then, that there is only one possible function $s$, namely:

$s(e_1) = v_1$

and only one possible function $t$, namely:

$t(e_1) = v_2$.

Since there are no "compound paths" to create, "composition" of walks is a non-issue, there is only one thing we can do: start at $v_1$ and go to $v_2$. So associativity of composition holds "by default" (it is vacuously true). The only thing missing to make this a category, is "identity morphisms", so we add them in. This gives us a finite category, which is (not surprisingly) known by the name $\mathbf{2}$.

We can actually "reduce" this notion a little bit further: suppose that:

$E = \emptyset$
$V = \{v_1\}$.

There is a unique function, then, $E \to V$, known as the empty function (we have no paths at all). To make it into a category, all that is needed is to add the only possible identity arrow $v_1 \to v_1$. This, then, the free category on a single vertex with no edges, is known as the category $\mathbf{1}$.

One thing to note here, is that the category $\mathbf{1}$ captures what we mean by "object", and the category $\mathbf{2}$ captures what we mean by "arrow". You should get in the habit of thinking: "arrows are one dimension higher than objects". What would "the next dimension" be? The simplest possible commutative diagram! THAT category is built from a graph with 3 vertices, and 3 edges, and is known as $\mathbf{3}$. Not surprisingly, it describes perfectly the ordered set: $\{0,1,2\}$ as a category, where we have a (unique) arrow $a \to b$ if and only if $a \leq b$.

But...we're not done yet: we can actually form a category from "the empty graph" (no edges, no vertices, no paths). The axioms are vacuously satisfied, since there are no objects or arrows to violate them. This category, is called $\mathbf{0}$, and is the template for many "zero-like" entities in many areas of math.

*********

All of this can take some time to get used to. The general idea of a "free something" is this:

We start with "something" given, and try to add "the missing parts of the structure until it works". Well, graphs already have "objects" (the vertices) and "arrows" (the paths), so all we need to do is:

1. have some notion of "identity arrow" (so we just add them in if they're not already there)
2. have some notion of "composition of paths", which we do in the most intuitive way possible: the "composition" of two paths is: first walk one, then walk the next by starting the second, where the first one ended.

*********

I'm sure somewhere Mr. Awodey must have an exposition of a given partially ordered set $P$ as a category. Review that, it will give you another example of how the domain and co-domain of an arrow can be "a single entity".

 

[Math Amateur]

Lets look at a very simple graph:

$v_1 \stackrel{e_1}{\to} v_2$

Here. $V = \{v_1,v_2\}$, and $E = \{e_1\}$.

It follows then, that there is only one possible function $s$, namely:

$s(e_1) = v_1$

and only one possible function $t$, namely:

$t(e_1) = v_2$.

Since there are no "compound paths" to create, "composition" of walks is a non-issue, there is only one thing we can do: start at $v_1$ and go to $v_2$. So associativity of composition holds "by default" (it is vacuously true). The only thing missing to make this a category, is "identity morphisms", so we add them in. This gives us a finite category, which is (not surprisingly) known by the name $\mathbf{2}$.

We can actually "reduce" this notion a little bit further: suppose that:

$E = \emptyset$
$V = \{v_1\}$.

There is a unique function, then, $E \to V$, known as the empty function (we have no paths at all). To make it into a category, all that is needed is to add the only possible identity arrow $v_1 \to v_1$. This, then, the free category on a single vertex with no edges, is known as the category $\mathbf{1}$.

One thing to note here, is that the category $\mathbf{1}$ captures what we mean by "object", and the category $\mathbf{2}$ captures what we mean by "arrow". You should get in the habit of thinking: "arrows are one dimension higher than objects". What would "the next dimension" be? The simplest possible commutative diagram! THAT category is built from a graph with 3 vertices, and 3 edges, and is known as $\mathbf{3}$. Not surprisingly, it describes perfectly the ordered set: $\{0,1,2\}$ as a category, where we have a (unique) arrow $a \to b$ if and only if $a \leq b$.

But...we're not done yet: we can actually form a category from "the empty graph" (no edges, no vertices, no paths). The axioms are vacuously satisfied, since there are no objects or arrows to violate them. This category, is called $\mathbf{0}$, and is the template for many "zero-like" entities in many areas of math.

*********

All of this can take some time to get used to. The general idea of a "free something" is this:

We start with "something" given, and try to add "the missing parts of the structure until it works". Well, graphs already have "objects" (the vertices) and "arrows" (the paths), so all we need to do is:

1. have some notion of "identity arrow" (so we just add them in if they're not already there)
2. have some notion of "composition of paths", which we do in the most intuitive way possible: the "composition" of two paths is: first walk one, then walk the next by starting the second, where the first one ended.

*********

I'm sure somewhere Mr. Awodey must have an exposition of a given partially ordered set $P$ as a category. Review that, it will give you another example of how the domain and co-domain of an arrow can be "a single entity".

Another EXTREMELY helpful post! Thanks Deveno

Anyone wishing to understand category theory (and in particular Awodey's text) should review your posts on MHB!

Thanks!

Peter