It’s worth noting that I needed this level of depth to bump into, yet again, a (seemingly persistent) fundamental misunderstanding of morphisms. Looking at the naturality square, I initially thought something like the following: “well both paths from $Y_1$ get us to $Y_3$, so things just seem to hold by definition.” The first part of that is perfectly accurate I suppose, but it’s missing the actual meaning of the statement. Morphisms are more than just a map from one object to another, as in they don’t just take in a whole object and produce another whole object. Getting to an object isn’t enough here, it’s getting to it in the same way. Put simply, I was thinking on too high a level, as if morphisms are necessarily maps that must ignore any inner components of the objects they’re acting on. This is likely me just misinterpreting the super high level of abstraction one faces when warming up to category theory. We write morphisms as maps $f: X\rightarrow Y$ and rarely say anything more specific unless working in a specific category, so I pretty much took that mean what it says in the most general sense: a morphism $f$ takes in an object $X$ and gives out an object $Y$, as if there’s nothing more atomic to act on than entire objects. But of course, a morphism merely maps from an object to another with no explicit guarantees of completeness, and the way you get to the co-domain can vary. Morphisms in general can exhibit all the usual flexibilities of functions in $\text{Set}$, e.g., not strictly being surjective, and of course two functions $f: X\rightarrow Y$ and $g: X\rightarrow Y$, despite sharing a domain and co-domain, need not actually map individual components to the same place (i.e., we can have $f(x) \not= g(x)$ for any $x\in X$).

I faced similar issues over in Category theory§Pullback, with a similarly detailed accounting of what now feels like an incredibly basic point. This just goes to show how easy it can be to misconstrue even simple, foundational concepts. Ultimately I think this just stems from operating at a level of uncomfortable abstraction, and you tend to be very careful making assumptions about anything that isn’t otherwise stated outright. I think the fundamental disconnect here has been the fact that almost no category theory verbiage deals in elements smaller than objects, and I’ve hesitated thinking in terms of anything lower as a result. Perhaps this is a result of not having followed a clear introduction built on the back of sets, which perhaps would’ve made this whole thing a non-issue.

After a considerable amount of toiling, I finally feel okay with how we get from the very abstract and vague descriptions of morphisms to maps aware of object structure. I didn’t even think I took issue with this, but I got myself caught in a loop where I just couldn’t feel why maps shouldn’t be required to return full objects. We say generally that a morphism is a map from an object $X$ to an object $Y$, and that’s about as specific as we get (except for identity and associativity). If we’re operating at this level and saying nothing further about the structure of those objects, it feels pretty straightforward to interpret that as a map taking an object $X$ and giving us an object $Y$ out. The problem is: it doesn’t mean that, or at least it doesn’t have to. Firstly, we stay at such an abstract level because it lets us say only as much as we need: as long as those top-level items are true, we have a viable morphism. Anything that falls under that jurisdiction should then be fair game; from here on out my problems mostly remained with the verbiage.

Here I was struggling with the idea that objects are atomic units that can’t be further decomposed. This is again missing nuance; we obviously have some kinds of objects, like sets, that can be seen as containers of other items. When we say objects are atomic, we effectively mean they’re atomic relative to the category theoretic statements being made. That is, they’re the “lowest level” construct those statements need to care about to be true, and they don’t care if there happens to be further structure when one looks closer. Now, actually defining classes of morphisms in specific categories is almost always a process of designing a map-like construct that is not only aware but often preserving of underlying object structure. So it’s not as if morphisms, in the way they’re actually applied, don’t look closer at the objects they apply to; they often must in order to remain consistent. It’s just that one can ignore those specifics and treat objects as black box units when it comes to making broad, category theoretic statements about the structures at play.

So decomposing is fine, but how about non-surjectivity? That still irked me a bit, when our top level statements seem to suggest we’re dealing in “whole objects.” It’s worth noting right away that any notion of “partial objects” can only present inside categories where objects can be decomposed further. Again, at the top level, we just don’t see inside the objects, and statements we make cannot apply to a deeper, internal level. So this non-surjectivity is merely a byproduct of behavior we allow inside of a category like Set, because it doesn’t break those top-level rules. If it did, sure, surjectivity would be important to apply everywhere, but our rules of composition and identity on morphisms work all the same whether we have our set function mapping onto the co-domain or not. It is of course perfectly natural to non-surjectively map between two sets, so we also actually want to be able to do this. Here I find embracing the word “to” is effective: morphisms map an object $X$ to an object $Y$. Under the hood, this may very well correspond to associating an element in $Y$ to each element in $X$; that’s perfectly allowed when defining morphisms on set-like objects. To get the entirety of this whole aside, the only thing you need to accept is the following: we are merely taking $X$ to $Y$, not (necessarily) transforming it 1-to-1, and that’s an acceptable meaning of the term “map.” Imagine how small $X$ can be and how large $Y$ can be and this still make sense as a map. For example, let $X$ be my group of friends and $Y$ be seat numbers in an NFL stadium. Our NFL tickets map each person to their one seat number, but that makes up a tiny fraction of all available seats and is obviously not “onto.” And it shouldn’t have to be for this relation to serve as a valid map between $X$ and $Y$, not only in the set-level or the category theoretic sense, but in the more pesky linguistic sense that got me into this mess in the first place. From the top-level, such a map really does get to be an arrow between the two whole objects $X$ and $Y$. How much the image of that morphism actually “fills out” $Y$ just isn’t relevant: to even think about the items in the image requires set-level awareness that cannot be seen when dealing in statements where objects are atomic by definition.

Even with all this, I still find it slippery somehow. When I try to root out what’s wrong, I think it just comes down the notation of writing functions according to their domains/codomains, e.g., $f: A\rightarrow B$. It’s actually this that I take issue with, more than anything inherent to category theory or object level abstractions or whatever else. It really goes beyond functions: it’s with binary relations. The simple fact we can call a link between one object in $A$ to one object in $B$ a relation (which is actually a valid, minimal relation) is what I find kind of pesky and stupid. That just doesn’t feel like what we mean by relation. So something like the single pair (2, green) is a valid relation from integers to colors. By all accounts that’s an association from an integer to a color, but it doesn’t seem like what we’d ever mean by a relation $R: \text{Int} \rightarrow \text{Color}$ (that notation is a little more conventionally functional than barebones relation, but the point stands). That is where I’m getting so hung up I think.

I’ve spent even more time on this, with a three part audio recording series to accompany it. But I’ve hit the root of the issue with the following, once and for all.

(left side of diagram) Within Set, object structure is visible. Morphisms can be defined over the elements within the objects, and the above depiction includes (effectively) the simplest possible relation between the two (i.e., connecting a single element in X to a single element in Y). Two comments:

(right side of diagram) Outside of Set, back in the general abstract category theory viewpoint, we lack any insight into internal object structure. One can imagine masking off all element-wise knowledge we had while in Set, leaving the above: two atomic objects with some connection between them. How these objects are related is no longer even a well-posed question at this level of granularity; they simply are or are not connected, and the “endpoints” of the arrow can only be the entire object.

So all relations inside of Set, no matter how large, are viewed uniformly once we’re outside of Set. “Thin” relations mature to full morphisms in the abstract view (since they can’t be distinguished from any other relation), and from the abstract view a full morphism simply suggests any relation exists under the hood.

It’s worth noting that relations are not even valid morphisms in Set, as they do not generally respect associativity of composition. But once you accept that relations are, in the most basic sense, mappings between sets, then you’re past the issue of non-surjective functions and the idea of yielding “less than Y” via a morphism that doesn’t map onto the co-domain. That is to say: from the abstract point-of-view, any kind of connection between elements within Set simply looks like a connection between the set-objects themselves, and it says nothing about what that relation must look like once you’ve revealed the element-level details. Not involving all elements in your map is not something that can be seen outside of Set, so all relations between any source and target look the exact same.

Taking a look back at this some weeks later: I think I do a good job conveying what felt problematic and how I got past it. This is from the perspective of not really recalling (right away, anyway) what the problem was in the first place, and I feel satisfied by the end of this passage. Here I think it may be helpful to simply recap why we’re here in the first place: looking at diagrams like the naturality square, one gets the sense that simply following two trajectories that end up in the same object makes them equivalent, by the sheer fact they point to same place. But that alone doesn’t actually make those (composite) morphisms equivalent, since they’re allowed to have such distinct structure in arbitrary categories (like being functions in Set) while mapping from/to the same objects. So in commutative diagrams, like the naturality square, we’re not saying that any two composite morphisms are equivalent because they start and end at the same places, but instead that any two morphisms starting and ending at the sample place must be equivalent under the morphism structure in the category. That is, not just any morphisms with the right domain/co-domain will do; they must actually be the same in the underlying category in order to uphold the kind of constraints the diagram is talking about. This is annoying/confusing because the diagrams don’t really convey this: you simply see arrows between objects, and it seems to suggest that moving from/to the target objects is good enough. But in reality, they are merely abstracting away any category-level morphism specifics so as to make a category-independent statement, but crucially those specifics will still apply when operating in any such category. That is to say: once you’re actually operating in a specific category, the known structure of its objects and morphisms comes into view, and you cannot ignore that revealed structure. I routinely find myself thinking in terms of Set when staring at commutative diagrams, and it’s a mistake to mix the two levels of abstraction (e.g., allowing oneself to think of the objects as sets, but continuing to treat morphisms as vague, non-functional maps; if you embrace the former, you must also work with the latter, else you’re mixing levels of abstraction).

To preface: equivariance is easily framed from the perspective of structure-preserving maps, which is a term commonly thrown around when speaking about morphisms. Therefore, this too has been a slippery topic for me in the past, and I’ve spent a sizeable chunk of time ensuring I have a comfortable intuition around this. Structure preservation, equivariance, and natural transformations are heavily intertwined; I find it helpful to frame latter two as structure preservation through entire classes or groups of transforms; we’ll formalize this afterwards. For now, I want to clarify the many, many places I’ve found myself stuck on structure-preserving maps and leave no doubt about how we should interpret this moving forward.

For starters: what we mean by “structure-preserving,” in the most general sense, can’t really be boiled down to anything more precise. As mentioned, we often call such things, in the abstract, morphisms. In that sense, one might imagine a structure-preserving map need only operate from/to the same kind of object: the very fact we “end up” in the (structured) object suggests we’re upholding necessary structure. But this is not generally what we mean, or is at least often not sufficient. That is to say: being a map with the appropriate external “signature” (i.e., mapping to/from the right kind of object) is alone not enough, as we care about how we move between the objects (and whether that movement preserves some structure within them).

Take, for instance, addition over the integers. Suppose we have the groups $G=(\mathbb{Z}, +)$ and $H=(\mathbb{Z}, +)$, and a map $f:G\rightarrow H$ defined $f:x\mapsto x+1$. Clearly “pushing” all integers through $f$ still just gives you $\mathbb{Z}$, and so in a very loose sense upholds “group structure” insofar as there is still a valid group on the other side. But the way we move under $f$ does not preserve addition (which is really all we mean by “structure” in this case): for any $a+b=c$ in $G$, we do not have $f(a)+f(b)=f(c)$ in $H$. So even though $f$ moves from a valid group to a valid group, it does not align the elements of the groups in a manner that is consistent with the addition operator.

As a reminder, $f$ is unary in $\mathbb{Z}$. Even if our binary operation (addition) had arbitrary arity, $f$ is a still a bottleneck of sorts through which each integer individually passes. So applying $f$ to individual elements in the underlying set is the only way to apply the transform at all. I’ve found myself occasionally thinking that $f$ could have distinct joint behavior, similar to the operator, but this isn’t true and recognizing as much helps simplify things. When I look at the required equality here, i.e.,

$$f(a+b) = f(a) + f(b),$$

I’ve let myself question whether this is the only constraint that could mean $f$ is structure preserving. But recalling how $f$ can only operate on single items in the underlying set, it becomes clear this is really the only thing you even can say in the first place. We use $f$ to map the items of one group onto another one-by-one, and the question is simply whether related items in the source group remain related in the transformed group. $a$ must go to $f(a)$, $b$ must go to $f(b)$, and the only real question from there is whether $a+b$ goes to the same place as $f(a)+f(b)$.

That last bit, the only salient part, has made me nervous for reasons I can’t easily articulate. I think it just somehow feels mysterious every time: I have to unpack it and check that it makes sense, and I get lost along the way. Either that, or as I mentioned before, the idea that there could be some other way to express structure preservation that I’m not able to see bugs me; I don’t have good intuition that the form is “tight.” At risk of restating what has already been said, the following might help:

We’re looking for a way to relate the transform $f$ to the operation at hand. Both need to be involved for us to establish any such link, and it’s critical to note that we’re observing what happens with the trajectories themselves under $f$. It’s not $f$’s image, it’s not its co-domain; these are more like aggregate consequences of having applied $f$ to every item. Working with $f$’s image or its co-domain ignores how we got there, and would therefore say nothing about $f$ at all. The entirety of the setup also avoids relating the transform and the operation: $a$ and $b$ are just any two items in the source set, $f(a)$ and $f(b)$ are the items we map them to, and both $a+b$ and $f(a)+f(b)$ are the results of applying our operation on those pairs. Thus far, we’ve said nothing about how $f$ and $+$ interact, we’ve merely applied them to eligible operands/inputs. Now, if $f$ is going to respect $+$, the only thing that matters is that it takes a valid application of the operation to another valid application of the operation: that’s just about all one could mean when saying “$f$ preserves the operation.” If it took three items $a+b=c$ to three items that couldn’t be related via addition, then $f$ would clearly not be compatible with the behavior of that operation. In such a case, I couldn’t rely on my operation as a means of relating items under the movement/flow of $f$. The operation is like a stitching in the set-fabric between items $(a, b, a+b)$, and preserving it means the same stitching is present when moving the fibers through $f$. This can only mean that I produce related items $(f(a), f(b), f(a+b))$: after I’ve taken my stitches to their new locations via $f$, I find they’re still intact.

That last bit I find the most helpful. Taking a concrete thing like $((a, b), a+b)$ (the operands and their output) removes the burden of feeling like there’s some nebulous structure coming along with the operation for which I need to have developed intuition. That pair is the structure; it’s like an extensional view of the operation (basically its graph). So every such pair that holds true in the source set is a little knot/stitch that locally exhibits the structure we’re trying to preserve, and we cannot untie it under $f$’s movement. If $f$ in fact preserves the desired structure, it will move every such knot to another valid knot, locally preserving our operation dynamics. Note that $f$ doesn’t directly map knots to knots, though; it applies uniformly on an element-level basis. Therefore it takes our knot

$$((a, b), a+b) \rightarrow ((f(a), f(b)), f(a+b))$$

In order for that right-hand tuple to be a “valid knot” under $+$, it must be consistent with the structure of the left-hand side, i.e., have an output element that is the sum of the two operands. So if $f$ preserves the knot, the item in the output slot, $f(a+b)$, must be equal to the sum of the input items, i.e.,

$$f(a+b) = f(a)+f(b),$$

which is the usual constraint. Let’s take a look at a concrete example:

Take the red bridge along the top: this is a “local knot” that $+$ ties. That is, it exemplifies the kind of structure that $+$ induces, and as a result that which we want $f$ to preserve. But as we move down the diagram via $f$, we see that it “unties” the knot, giving us transformed operands whose sum does not match the transformed sum. The red bridge along the bottom shows the knot that would be valid under our transformed inputs. It would be equally reasonable to consider the kinds of inputs $f$ could’ve “chosen” to reach the needed output. In either case, $f$ does not align them correctly: it doesn’t map a $+$-knot to a $+$-knot.

For the linear transformation $f(x)=2x$, on the other hand:

Here we find the map does respect the $+$ operation (at least over the specific operands we’ve plotted): the knots remained tied through $f$.

Moving back out, recall that we say generally that, for a transformation $f:A\rightarrow B$ and $k$-ary operations $\mu_A: A^k \rightarrow A$ and $\mu_B: B^k \rightarrow B$ defined over $A$ and $B$, respectively, $f$ is said to be structure-preserving if the following holds:

$$f(\mu_A(x_1,\dots,x_k)) = \mu_B(f(x_1),\dots,f(x_k))$$

This is very general, and worth exploring the dynamics when $f$ is more like a binary relation. In this case, I found myself thinking of addition in modular arithmetic. Here we have an operation that behaves similarly over entire classes of values: rather than observing the “paired” association of structure $(x,\mu(x))$ with $(y,\mu(y))$ through $f$ (paired as in we relate one “bit of structure” with just one other), we now say something like the structure $(x,\mu(x))$ can be associated with many occurrences $(z,\mu(z)), z\sim x$, under the relation $\sim$. Nothing is fundamentally different here save for our map being “wider” in a sense: it links together more structure across objects.

Looking at a rough sketch of congruence modulo $k$, we can imagine “folding up” $\Bbb Z$ to give us $k$ new classes of items:

It’s over these equivalence classes that we observe consistent structure under addition. That is, the relation that induces this partition respects the operation: we can first add values in $\Bbb Z$ and map to their equivalence classes, or first map to equivalence classes and “add” them².

The diagram above attempts to show what’s happening as move from items to their equivalence classes (going down), and the ways we add those objects (moving right). Note the difference in the 2D representation here compared to similar diagrams above: $x_1$ and $x_2$ are both meant to be $k$-dimensional, and we’re simply laying out our objects in the grid there. Note also the notion of addition used over equivalence classes is the Minkowski sum, showing how the operation being respected can show up in slightly different forms between $\mu_A$ to $\mu_B$. In any case, the high-level take away here is that our structure-preserving maps can be more than just functions: they can associate many target objects to a single source, and this naturally abides by the same principles we’ve discussed above. In this particular case, we’re saying that whatever the equivalence class “allegiances” of $+$’s operands and output are, they will be respected: addition is consistent up to class assignment. Put another way, $+$ plays along with the new notion of identity induced by the equivalence relation (color in the diagram). If a blue item and green item add up to a red item (following the top bridge), then adding any blue and green items will yield a red item (following the bottom bridge).

In total, the relation-like map explored here helps broaden my intuition, shedding light on how general a structure-preserving map really can be. If we’ve allowed a generalization from pairwise associations through functional maps to more “class-like” associations via relational maps, you might naturally ask whether we can do something similar over the operation. That is, can a map respect a class of operations or transformations? This is pretty much exactly what we do with equivariant maps, and we rely on group theory to formalize valid collections of transformations through the same language of operations (i.e., the group action). We explore this in depth below; that’s what kicked off this aside in the first place.

One final remark to potentially keep in mind: the notion of structure preservation is really more of a loose hierarchy. Questions like which structure or how much of it can be naturally addressed by strengthening or weakening one’s requirements in a given setting. What is meant by “structure-preserving” is generally very flexible and, within the general framework we’ve formulated here, can accommodate any object, transformation, or interpretation of “map.” One might attempt to formulate a map between groups and find that it fails to be a group homomorphism, but it can perhaps still be seen as a map preserving structure of sets or even some other relaxed notion of symmetry. One also needn’t have maps that are particularly well-defined, e.g., analogous to surjectivity/injectivity; even trivial, information-destroying maps can be structure-preserving over the “places” where they’re defined. All in all: structure preservation is very fundamental in abstract algebra, and having a strong intuition for what it means is important (even if I don’t yet have that, but I sure have spent a lot of time toiling). But it is ultimately incredibly flexible and context-dependent, applying across many different layers of abstraction.

Small confusing point for me here: the analogy of $\mu$ to a binary operation, in the usual sense, was unclear to me. We have $\mu: T^2\rightarrow T$, but $T^2$ is still just a functor, i.e., $T\circ T$, so it feels just like a unary operation defined over any other functor, e.g., some natural transformation $f: T\rightarrow T$. That is, $\mu$ isn’t defined over pairs of objects, nor does it map explicitly from two functors; composition can at least be seen to operate on two functors $\circ(F_A, F_B) \mapsto F_C$. $\mu$, however, doesn’t operate explicitly on two items.

A quick, perhaps obvious thing: maps can always be seen as operating on one object. Even multivariate functions can just be seen to map from a single $n$-tuple, rather than being a construct capable of accepting $n$ separate objects. Of course, this changes nothing about what any map of this kind is capable of, but it’s a simplifying perspective that helps open new possible interpretation for the term “arity.”

We might now say the following: a map’s arity isn’t simply the number of arguments it can accept. Rather, it’s a quantifiable property of the domain of objects over which it’s defined. Addition over the reals, $+:\Bbb R^2\rightarrow\Bbb R$, remains the same 2-ary operation in the usual sense: it maps from the space of 2-tuples, explicitly pairing up two items. Implicitly here $\Bbb R^2$ refers to the cartesian product $\Bbb R\times\Bbb R$, and the arity of the resulting map is aligned with the dimensionality of the product space domain. But what if we had an operation other than $\times$, e.g., $\otimes$?

This is precisely the question that leads us to analogizing $\mu$ with a (typical) binary operation. In monoidal categories, we saw above that $\otimes: C\times C\rightarrow C$ is a bifunctor. (Note how $\times$ is used in the definition of $\otimes$; this whole “arity generalization” only really applies inside monoidal contexts, so we have to get there first with existing machinery.) This can be seen to operate on pairs of objects (and morphisms) in $C$, mapping them to other objects (and morphisms) in $C$. $O\otimes O$ is simply us applying $\otimes$ to the same object $O$, and this is the new form of the domain for the binary operation-like map $\mu$. We’re simply generalizing the way we build the domain from two objects by letting our bifunctor $\otimes$ “put things together” instead.

In total, for our multiplication morphism $\mu: O\otimes O\rightarrow O$ defined for monoid objects in any monoidal category, we have a map that doesn’t strictly look like a binary operation in the usual sense (hence this messy aside). It is nevertheless constructed around a domain that is built from two objects with $\otimes$, and that’s good enough for a general analogy to binary operations. It’s worth noting that for monads, in particular, $\otimes$ is fixed as functor composition $\circ$, and $\mu$’s domain $T^2 = T\circ T$ is still just a functor. $\mu$’s “arity” is therefore more akin to levels of nested composition rather than number of dimensions or arguments: it flattens.