Hacker News Reader

Comment by pgustafs | Hacker News Reader

The main thing categories add to graphs is identifications of paths. Every pair of edges f: A -> B and g : B -> C generates a third edge g.f, and we identify the path (g)(f) with the new edge (g.f). Not only that, we add h.(g.f) = (h.g).f for any h: C -> D, which basically says that "." acts like concatenation of paths (it doesn't matter how you group the edges in a path, you get the same thing).

Those are the basic axioms to say you're working with a nice operation that turns paths into edges in a reasonable way. It gets interesting when you add more identifications (commutative diagrams) and operations (functors). Prototypical example: vertices are sets, edges are functions, you get identification of paths (sequential compositions of functions) whenever the underlying composite functions are pointwise equal.

View on HN

> The main thing categories add to graphs is identifications of paths.

There's another, very different way to describe "identification of paths", although I agree that both are fundamental to categories.

What you've described is better known in graph theory as the "transitive closure" of a graph. Indeed, every graph (and even every multigraph, with multiple edges between two nodes) gives a category via its transitive closure. But this category is the free category on a graph, and there are many categories that are not "free", so there is still something missing.

What categories add on top of the transitive closure is the ability to say that two paths between the same nodes are fundamentally equivalent. (In other words, you are identifying two paths -- see the confusion?) If those paths could be further composed with other paths, then the resulting composites are also equivalent (i.e. if a = b then ac = bc); proceeding in this way gets you a new category.

It's the ability to say that two distinct "paths" (lists of edges) give you the same "edge" (single step) that really distinguishes category theory from graph theory. Commutative diagrams are popular in category theory precisely because they graphically display which paths produce equivalent edges.

> It's the ability to say that two distinct "paths" (lists of edges) give you the same "edge" (single step) that really distinguishes category theory from graph theory. Commutative diagrams are popular in category theory precisely because they graphically display which paths produce equivalent edges.

It's the idea of graph isomorphism that confuses me about this, because I have trouble separating it from recognizing two equivalent paths as a type. The main reason is I don't have depth in the concepts at all, but the secondary one is that di-graphs with attributes seem to provide a covering abstraction for this. I should probably RTFM, (or more accurately, Do-TF-Graduate-Degree) but every time I read an explanation it creates a curiosity I can't leave alone.

I'm nervous that there might be a confusion between levels of abstraction here. Let me try to ground the terminology a bit, and see if that helps first.

As a recognized term, "graph isomorphism" would lift to category theory as "category isomorphism". These are not entities within a category (uh, per se), but they're relationships about and between categories. A graph/category isomorphism describes how two graphs/categories can be equivalently described in terms of each other.

In graph theory, a bidirectional path is a pair of paths within a graph. Two nodes are part of the same strongly-connected component if you can travel between them both ways. In the transitive closure of a graph, two nodes are in the same strongly-connected component if and only if the edges a->b and b->a exist within the graph.

In category theory, an isomorphism of objects is a pair of arrows f, g within a category between the same two objects -- such that their compositions fg and gf are both equivalent to the identity arrow. (In graphs, the paths fg and gf must be considered equivalent to the empty path.)

In a graph, you might naturally think of isomorphic objects as those that "relate" the same way to all other objects -- that is, if you didn't already know which node you were looking at, you couldn't tell the two apart from a vantage point anywhere else in the graph. This intuition broadly carries into category theory, though you can have multiple edges betwen nodes -- that's why the `fg = gf = 1` rule needs to be added. The transitive closure guarantees that for any isomorphic objects A and B, any path entering (leaving) A (B) can be extended to enter (leave) B (A), and the identity condition guarantees that the extension we added to cross between the two objects didn't add or remove information.

Put a slightly different way, if I have a path X -> Y that passes through either A or B, there is no way to distinguish whether the path went through A or went through B.

Thnk you, yes, levels of abstraction is precisely what I'm being tedious about. These are very generous explanations and I respect your time on this, please ignore if I veer into a cranky Gish gallop.

This distinction between a bidirectional path in a graph vs. a functor between objects is a great clarification, and I can begin to comprehend how I would be confusing the representative directional arrow in a graph with the logical operation of mapping in CT is different - because I'm treating them both as just morphisms between objects.

The universality of CT implied a conjecture to me where, either there are theorems of CT that cannot be expressed as graphs, or there are graph theorems that cannot be expressed in CT.

"Expressed," is handwavy, but because we're on the edge of notation/encoding and representation vs. whether there a homology between graphs and categories, when I get into the question of a universal modelling languege, it raises the question of what the minimum necessary set of instructions to express theorems in that language (either CT or graphs), and whether the smallest program that can express CT will resolve to a graph.

If the Kolmolgorov complexity of the program that produces theorems in CT is greater than the one which produces theorems for graphs, and that program itself reduces to a graph, it implies to me that the less complex program is the more universal modelling language.

This was why in terms of modelling I thought that CT seemed more like an ornamented subset of graph theory. However, that's like if someone said math is a just subset of Godel numbering, which well, yes, but that's not very helpful. :)

> Gish gallop

Thanks for that; I learned a new phrase ^_^

Yes, admittedly your post throws a bit of a wide net, but I think I see what you're angling for.

> it raises the question of what the minimum necessary set of instructions to express theorems in that language

That's a really good question. Take the NAND gate as an example: we know we can implement any boolean function with only NAND gates. So the circuit language consisting purely of the NAND gate (and wiring rules for connecting gates) is ridiculously compact, even minimal. In some sense, it has a very very low entropy.

However, the circuits we construct are conversely ridiculously complex! Any given circuit is just a wad of NANDs, and trying to extract meaning from that circuit beyond executing it as a black box is going to be very difficult. You could say that these circuits have a very high entropy.

In comparison, suppose we allow ourselves the usual set of {AND, OR, NOT} gates. We know that any logical function implementable by {NAND} is implementable by {AND, OR, NOT}, and vice versa, so there is no loss in functionality. But circuits expressed in this language have far more structure, making them individually much easier to analyze. We can define such notions as "conjunctive normal form", in that any circuit can be transformed into an equivalent three-layer circuit: a layer of NOTs feeding into a layer of ORs feeding into a layer of ANDs. These circuits have far lower entropy in exchange for a modest increase in our circuit language.

So when you say this:

> it implies to me that the less complex program is the more universal modelling language.

I think we have two competing notions of "complexity" at hand, and it's very hard to say which one ought to win out. As a personal preference, I like to imbue my creations with more inherent structure, so I prefer things like {AND, OR, NOT} over things like {NAND}. It makes the constructions easier to understand.

If you're studying the languages and not the things created in those languages, then things like {NAND} may be superior. But you usually need some kind of language in which to describe your languages -- did you notice I was using set-theoretic notation? -- and so you have the same question again at a meta level.

One of the attractions of category theory is that it's also a pretty good language for speaking about category theory!

Super interesting, thank you. I forsee these topics distracting me well into old age.

This idea of adding the structure of AND, OR, NOT over a field of NAND gates, without losing information sounds like the the beginnings of where Categories become more meaningful than graphs. The analogy would be that AND would be like a functor category, where again, it is represented as an 'arrow' but it's really it's more like a lossless abstraction, in a strict information or logical sense.

This circuit that is a just wad of NANDs is not unlike a generalized universal intermediate representation of a program, or even an esolang program like BF, because while they aren't efficient for human reasoning or computation at all, they are consistent universal forms for symbolic representation.

The problem in code is always, "this would just be compute/work problem if only this thing were made of <consistent-data>," and what attracted me to the idea of CT was that it seemed to be a tool for reasoning 'different' things into compositions of their consistent abstractions. I still think that's true, but now have a better sense of why.

I will revisit the short course that led me here as well (https://applied-compositional-thinking.engineering/lectures/)

I've never studied categories, but my reading of the parent comment was that a category was the combination of a graph and a seperate identification of paths within the graph in addition to the bare graph. Thus having isomorphic graphs would be necessary but not sufficient for two categories to be equivalent.

I guess you could represent that as an extra complex graph, but I'm guessing that would be unwieldly, and may not actually be useful for analysos.

> I've never studied categories, but my reading of the parent comment was that a category was the combination of a graph and a seperate identification of paths within the graph in addition to the bare graph.

Pretty much, yes. In group theory we call this a "presentation": we give the generating elements of the group, followed by the equations to "mod" by. For instance, the group presented by <x, y | xy = yx> is the free commutative group on two elements -- the equation we've modded by forces commutativity, but leaves us otherwise unconstrained. Or the group presented by <x | x^5 = 1> -- that's the cyclic group of order 5.

Categories are novel algebraic structures in some respects, but conceptually relatively standard in others. A naive "presentation" of a category is exactly as you say: you define some fundamental edges and assert any desired equivalences of paths composed from them [0]. But, given the expressive power of categories, sometimes this is still quite explicit and clunky. In particular, you don't usually want to spell out all of the basic arrows you're starting with.

> I guess you could represent that as an extra complex graph, but I'm guessing that would be unwieldly

That being the case, it's often easier to define a model category by stating how it relates to other, already-understood categories. A "category with finite products" is any category that relates in a particular way to the category with two objects and no non-trivial morphisms. Of course, the phrase "a particular way" is load-bearing, but it's formalized on the notion of "functor" and "universal property". It's a much more implicit kind of definition, but in turn it gives you a very powerful tool for speaking about your category.

[0] https://ncatlab.org/nlab/show/presentation+of+a+category+by+...

Reply on news.ycombinator.com