In a previous post, I suggested we should think of abstractions/ontologies as maps that make a certain commutative diagram commute:
The downward arrows are the abstraction, which throws away some information about the world state while keeping other parts. The horizontal arrow at the top is time evolution. The diagram says that there should be a way to "mirror" the time evolution inside the high-level model (that's the dashed arrow at the bottom). Commutativity of this diagram means that we can either do time evolution in the actual world and then abstract, or first abstract and then do time evolution in the model. If this doesn't make sense, the original post has more details and examples.
It turns out that this idea is very, very far from new. I'll hopefully write a post on some related literature soon, but here I want to discuss one connection in particular: category theory, and more specifically (co)algebras of endofunctors. Using coalgebras for abstractions is an idea from bisimulations in computer science. See nlab if you just want a quick version. This post essentially just adds lots of examples and some reframing—the computer science discussions I've seen tend to be heavily focused on the special case of abstractions of transition systems.
There are two main things the (co)algebra framework will give us:
I'll briefly elaborate on why the description in my earlier post was a bit vague. I had another example of the commutative diagram above with a somewhat different flavor:
The abstraction M maps from real numbers to a representation using 11 decimal digits (the details don't matter here). The horizontal arrow isn't time evolution of a physical system in this example, instead it's addition of real numbers. The commutative diagram essentially says we should also be able to add within our decimal approximation.
A key difference is that in the time evolution example, the horizontal arrow was an endomorphism, i.e. it mapped from the set of possible states to itself, with a type signature like X→X. Addition does not have this type signature, it's a map R×R→R. This means we can't use the same function for both downward arrows. Intuitively, it's pretty clear that it makes sense to use M×M on the left side, i.e. apply the abstraction to each input independently. But what's the general principle that tells us how the two downward arrows should be related? And what kinds of horizontal arrows can we use besides time evolution and addition? That's what this post gives one potential answer to.
I'll assume you know what categories and functors are, and just focus on slightly less well-known concepts. If you don't know category theory, the next section with examples could still be interesting to get a sense of what kinds of things can be described in this abstractions framework.
First, an endofunctor is simply a functor F:C→C from a category C to itself. All of my examples are going to be for C=Set since that already gives us plenty. Some examples of endofunctors we'll use:
An algebra of an endofunctor F is a morphism α:F(X)→X for some specific object X (i.e. a set in our examples). A coalgebra is the same thing in the other direction, α:X→F(X). Some examples:
As you can see, both the time evolution example and the binary operation example have a horizontal arrow that can be understood as a (co)algebra. In general, I think any algebra or coalgebra of any endofunctor can be used as a horizontal arrow. The choice of functor and (co)algebra is going to describe which "task" we care about: prediction of next time steps, addition of numbers, etc.
Given a horizontal arrow, i.e. a (co)algebra, we can think of abstractions as morphisms from this (co)algebra to another one. A morphism from an algebra α:F(X)→X to β:F(Y)→Y is defined as a map f:X→Y such that this diagram commutes:
In our context, the morphism f is the abstraction, with X the low-level/detailed system and Y the high-level model. β is the representation of the task/operation α within the high-level model (the dashed arrow in the diagrams above).
This is a generalization of the addition diagram above: there, F(X)=X×X and F(f)=f×f. Note how this answers the question of what the relation between downward arrows should be: we choose the abstraction f and then get the other arrow by applying the functor F, which is part of the specification of the horizontal arrow.
Coalgebras work analogously, except we choose the downward arrow on the left side and then translate it to the right using the functor:
This shows how (co)algebras are one possible formalization of these commutative diagrams. I don't see any strong a priori justification of why they are the correct formalism. The main reason this approach seems interesting to me is that lots of examples work out: abstractions I had thought about before seeing this formalism fit in nicely, and if I plug in endofunctors I hadn't thought about before, I often get good examples of abstractions out. This is what we'll look at next.
I'll now quickly go through some examples of different endofunctors and how to interpret them in the context of abstractions. These are going to be pretty informal but hopefully still clear (otherwise let me know and I'll be happy to give a more detailed version in the comments).
I don't view any of these as decisive issues. Possible objections that I think could be a bigger deal:
Thanks to Generallyer for pointing out related work in causality; there are many other examples as well.
Here is a couple of my somewhat related comments from awhile back: https://www.lesswrong.com/posts/NFMPftEhagCcHcmQJ/on-the-role-of-abstraction-in-mathematics-and-the-natural?commentId=GRp8PKJd64Tm5DhtA
I wish I had the background to formalize them the way you have in your post.
In general, I get the importance of keeping in mind the relevant commutative diagram (often more than one) for whatever mapping you are working on, but it is not clear to me that you can get anything actionable out of them. Still, I do think that even if all your examples are in Set, CT is a good framework for thinking about them, without going down the abstraction levels.