FOM: Definition of Lawvere theory: additional condition needed

Vaughan Pratt pratt at cs.Stanford.EDU
Sun Mar 22 15:47:18 EST 1998

>The difference between graph theory and category theory is that category
>theory incorporates the congruence on paths as part of its structure,
>permitting every instance of "congruent to" to be streamlined to
>"equal to".  The graph theory formulation of category theory is like a
>bicycle with training wheels: great for getting started but eventually
>you want to take off the training wheels so you can go faster.

From: martind at (Martin Davis)
>Surely this is not the only difference between such utterly different

Quite right, I should have said "The difference between graphs and

>It has been noted that the \in relation in a model of set theory
>can be thought of as defining a graph. But single sentence of the form: "The
>difference between grapg theory and set theory is ..." would just be silly.

As I observed in message 11 of the February FOM archives, "graphs are
positioned midway between sets and categories, being simultaneously
discrete and connected.  Graphs are equationally definable in set
theory, and categories are equationally definable in graph theory, but
categories are not equationally definable in set theory, the canonical
counterexample to the transitivity of monadicity."

Graphs are sets (of edges and vertices) with operations of source and
target giving the endpoints of edges.  Categories are graphs modulo a
congruence (with respect to concatenation) on their paths.

>From that perspective I fully agree that graphs are not significantly
closer to categories than to sets.  My remarks were directed to students
of category theory who are starting from a set theory perspective,
for whom graphs are an ideal stepping stone along the way.

Vaughan Pratt

More information about the FOM mailing list