Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: category theory

Topic: Decompositional Category Theory

Joseph Denman (Aug 09 2021 at 15:05):

This statement is banal by now, but CT has a bias in favor of compositionality and against decompositionality. But agents navigating the world understand both; they have the ability to construct relationships and deconstruct relationships. I'm curious what CT would look like if it took this idea seriously. The hom sets of a category behave like a monoid with a level of indirection. The hom sets of a decompositional category would behave as a comonoid with a level of indirection.

A decompositional category $\mathcal{C}$ still has a class of objects $ob(\mathcal{C})$ and for every two objects $A$ and $B$ a set of morphisms $\mathcal{C}(A, B)$. But now instead of a binary operation $\circ : \mathcal{C}(B, C) \times \mathcal{C}(A, B) \rightarrow \mathcal{C}(A, C)$ it has a factorization operation $\cdot: \mathcal{C}(A, C) \rightarrow \mathcal{C}(B, C) \times \mathcal{C}(A, B)$ such that the analogous comonoid equations are satisfied.

An obvious example of this structure is the category of real numbers with $\leq$ as morphisms. But, aside from that, not many examples come to mind. This is surprising given that our perception of mathematics is often as a tool for discovery rather than a tool for construction. It makes me wonder the extent to which discovery is actually a constructive process - the process of constructing a model of the world in our minds. To understand something in terms of its parts, does our model of that thing have to be more complex?

I also wonder if there's a way to capture both compositionality and decompositionality in the same structure. There is a version of the Frobenius algebra equations that the factorization and composition operations might satisfy, though the equations IMG_0256.jpg only to apply when objects are related to each other (see attached).

Anyways, I'm searching for examples of this structure if any come to mind.

Oscar Cunningham (Aug 09 2021 at 15:09):

LaTeX has to go in double dollar signs on Zulip for some reason.

Morgan Rogers (he/him) (Aug 09 2021 at 15:21):

@Joachim Kock talked about decompositionality in this thread a while back, initially suggesting it as a way to tackle emergent behaviour. I hope this provides a spark for further discussion on the topic!

Jesse Sigal (Aug 10 2021 at 14:14):

A bit of a shot in the dark, but the type of $\cdot: \mathcal{C}(A, C) \rightarrow \mathcal{C}(B, C) \times \mathcal{C}(A, B)$ reminds me of fact that the $\text{Hom}$ profunctor is the identity in the category of profunctors, and so $\text{Hom} \cong \text{Hom} \star \text{Hom}$ where $\star$ is profunctor composition. Writing this out as a coend, I think we get

$\text{Hom}(A,C) \cong \int^{B} \text{Hom}(B, C) \times \text{Hom}(A,B)$

which is related to your factorization operation. I also think that $\text{Hom} \cong \text{Hom} \star \text{Hom}$ means $\text{Hom}$ has an idempotent (co)monoid structure. I'm not very experienced with profunctors though!

Oscar Cunningham (Aug 10 2021 at 14:19):

Joseph Denman said:

An obvious example of this structure is the category of real numbers with $\leq$ as morphisms.

I don't see how this works. Wouldn't this be saying 'if $a\leq c$ then for all $b$, $b\leq c$ and $a\leq b$'? That's not true.

Jesse Sigal (Aug 10 2021 at 14:24):

Maybe it should something like "if $a \leq c$, then there exists a $b$ such that $b \leq c$ and $a \leq b$"? I think this is a concrete description of part of the coend I wrote above.

Nick Hu (Aug 10 2021 at 14:27):

@Jesse Sigal It looks like you are noticing that Prof is able to distinguish categories only up to Cauchy completion, which can be an important detail

Joseph Denman (Aug 12 2021 at 21:53):

@Jesse Sigal @Oscar Cunningham The same way that regular composition is defined via there exists so would decomposition. Thanks for your thoughts on profunctors.

Morgan Rogers (he/him) (Aug 14 2021 at 12:06):

But if you just put in a "there exists", then every category has two canonical decomposition structures: identity on the left and identity on the right!

Jesse Sigal (Aug 14 2021 at 22:25):

The existence of trivial structures in the most general case can be a good thing in my opinion :)

Morgan Rogers (he/him) (Aug 16 2021 at 10:59):

I was pointing out that if you're starting with a category, a decomposition condition of the form "for each arrow $a \to c$ there exists $b$ such that the arrow decomposes as $a \to b \to c$" is vacuous, since we can always take $b$ equal to $a$ or $c$. You'll need to be more specific.

Jesse Sigal (Aug 16 2021 at 12:57):

Ah I see what you mean. I was thinking more of the "give a structure" approach as opposed to the "identify a property" one. So a specific category could have many decomposition structures (at least two trivial ones by your previous observation), but could also have more non-trivial ones.

I think one way to relate the coend idea to what Joseph said is that since the coends are equivalence relations, a decomposition operator could be seen as a global choice of representatives of each equivalence class under suitable compatibility conditions. Then probably the left/right identities give such a valid choice, but hopefully there would be more :)

Fawzi Hreiki (Aug 16 2021 at 13:37):

It seems like lifting/extension properties should be relevant here. After all, lifting and extending are about undoing composition.

Fawzi Hreiki (Aug 16 2021 at 13:39):

Fiber bundles are the most basic examples of fibrations and it makes sense to think of fiber bundles as ‘decomposable’

Fawzi Hreiki (Aug 16 2021 at 13:43):

More generally, couldn’t the whole idea of descent in geometry be understood as studying how to define data on spaces via their ‘decompositions’?

Jesse Sigal (Aug 16 2021 at 14:30):

Interesting idea, I'm not familiar with those areas but sounds promising! :smile:

Fawzi Hreiki (Aug 16 2021 at 15:20):

In a way, a lot of geometry actually amounts to understanding how a given space 'decomposes' into simpler spaces and how much of the original space can be reconstructed from these decompositions.

As a simple example, you can always break up a topological space into its connected components and do things (compute fundamental groupoids, define vector bundles, etc..) connected-component-wise since these components don't interact with each other at all.
It becomes more interesting when you have to consider 'behaviour on the boundary' between components in a decomposition.

Fawzi Hreiki (Aug 16 2021 at 15:24):

E.g. when you decompose a topological space into an open cover, or a scheme into its irreducible components.

Keith Elliott Peterson (Aug 16 2021 at 17:17):

I'm not sure about outright dualizing composition.

That being said, I don't see why we couldn't speak of a kind of subtraction operator of homs:

$$\setminus :\hom[A,C]\otimes\hom[B,C]\to\hom[A,B],$$

which is certainly a way to decompose homs.

Joseph Denman (Aug 16 2021 at 18:51):

@Morgan Rogers (he/him)

I was pointing out that if you're starting with a category, a decomposition condition of the form "for each arrow a \to ca→c there exists bb such that the arrow decomposes as a \to b \to ca→b→c" is vacuous, since we can always take bb equal to aa or cc. You'll need to be more specific.

By the comonoidal interpretation that decomposition should follow, decomposition into an identity followed by a morphism should be equivalent to that morphism. This is dual to the identity axiom in category theory. An identity followed by a morphism is equivalent to that morphism.

@Jesse Sigal

I think one way to relate the coend idea to what Joseph said is that since the coends are equivalence relations, a decomposition operator could be seen as a global choice of representatives of each equivalence class under suitable compatibility conditions. Then probably the left/right identities give such a valid choice, but hopefully there would be more :)

I would probably try to develop decompositional category theory to the point where things like coends can be expressed. The relationship between the coend description of decomposition that you gave and whatever a coend would be in decompositional category theory is not obvious to me.

@Fawzi Hreiki

In a way, a lot of geometry actually amounts to understanding how a given space 'decomposes' into simpler spaces and how much of the original space can be reconstructed from these decompositions.

Interesting. How often do spaces that can be decomposed indefinitely arise? This actually gives me an idea. I thought that this structure implied that you could only examine structures where a morphism $A \xrightarrow{h} C$ could always be factored into two morphisms $A \xrightarrow{f} B$ and $B \xrightarrow{g} C$ where $B \neq C$ and $A \neq C$. But that's not the case. It could be the case that a morphism can only be factorized into the original morphism and an identity morphism. These morphisms are in some sense the most elemental morphisms of the category. But that doesn't actually sound different from a traditional category :thinking:

Fawzi Hreiki (Aug 16 2021 at 19:20):

You might want to take a look at ‘Möbius categories’

Fawzi Hreiki (Aug 16 2021 at 19:25):

Or perhaps just generally at factorisation systems.