The n-Category Café

This was a very enjoyable read!

As you write, a process is causal if when we do it and then chuck the result, its the same as having chucked the input. I can see this as saying that the result of the process is really everything the process effects; getting rid of the result is the same as not having done the process at all. But I’m struggling to see how this relates to causality – probably because I don’t have much of an intuition for what a “causal process” is pre-theoretically. Would ya’ll be willing to elaborate on how this definition of a causal process deserves the name?

In physics there’s been an extensive study of causality, especially in the context of special relativity — particularly in the study of relativistic quantum field theory, where there are some axiom systems that include axioms governing causality. For example, the Haag–Kastler axioms include an axiom of causal locality. I wonder if Kissinger’s approach has been related to this work in physics. It would be great if models of the Haag–Kastler axioms gave examples of categories obeying some of Kissinger’s properties.

Typos:

The numbering of conditions in the definition of a compact closed category being precausal is 1, 2, 1, 1.

Then in “Given a set of states $c \subseteq \C(I,C)$ for a system $A$”, the $C$ should be $A$.

This is really interesting and I would like to understand it, especially because I’ve recently been thinking a lot about $\ast$-autonomous categories. But I am confused about what a “higher-order process” is. Did you define it? Do I have to read the paper to find out what it is?

Hi all,

Great summary Joe & Dmitry, and great discussions. I would chime in to clarify some points, but it looks like you all have worked it all out already. :)

I’ll just sum things up a bit and make a few remarks:

HIGHER-ORDER PROCESSES

In the context of this paper, we use the term “higher order process” to refer to any morphism in Caus[C]. This includes:

1. first order processes, which are morphisms whose domain and codomain are first-order systems (i.e. those of the form (A, {discard}*) )

2. second order processes: morphisms whose domain and codomain are of the form (A -o B) for A and B first-order systems.

….and lots of other stuff. This is not a purely syntactic notion, because it relies on a fixed, concrete notion of what first-order means. It is useful to think of first-order systems as a sort of “atomic” type in the logic, which you can build more complicated things out of.

At some point, we were going back and forth between defining the objects of Caus[C] to be pairs (A,c) where c is flat and closed, or instead letting them be generated inductively from first order objects (A, {discard}*) using tensor and star. Since all such objects are pairs (A,c) where c is flat and closed, this would have yielded a smaller category than Caus[C] we defined (whose morphisms maybe had more right to call themselves “higher-order processes”). In the end, we opted for the non-inductive definition for the sake of simplicity, at the cost of Caus[C] possibly containing some “weird” systems (A,c) which don’t arise inductively from first-order ones.

Mike is right that there is a certain circularity to the definition of Caus[C], because precausal categories require that second-order causal processes factorise (where second-order causal processes are a Caus[C] concept). This chicken v. egg situation is solved by the fact that second-order causal is indeed defined by the LHS of the implication, as Robin points out. Put another way, the words in axioms (C3) and (C4) are only meant to give intuition behind these axioms. The formal content is precisely contained in the formulas.

CAUSALITY

Probably the most controversial aspect of this line of work is our insistence on calling the “discard output = discard input” equation the causality postulate. We do this for a couple of reasons.

The terminology originates in operational probabilistic theories, where (an equivalent version of) this equation is given the following interpretation, in terms of an abstract notion of measurement: “Causality: the probability of a measurement outcome at a certain time does not depend on the choice of measurements that will be performed later.” (see arXiv:1011.6451)

There is indeed a connection to special relativity. Namely, if you form a directed acyclic diagram of processes satisfying the causality postulate, then the overall process will respect the evident “non-signalling” constraints between certain inputs and outputs given by this diagram. Coecke, Hoban, and I explained this in some detail in arXiv:1708.04118. There, we call the causality postulate “process terminality” to avoid overloading the term “causality” too much.

So, toward addressing John’s question about the relationship to Haag-Kastler axioms: this obeying of non-signalling constraints, which is equivalent to our causality equation, seems to be most closely related to the Haag-Kastler axiom of causal locality, which states that spacelike subalgebras commute. For quantum-like C*-algebras, this is the same as non-signalling, as established by Clifton, Bub, and Halverson (arXiv:0211089).

Thanks for that explanation, Aleks! Now that I think I know what the definition of $Caus[\mathbf{C}]$ is saying, I want to understand it. To that end, let me try to dissect it using the sterile scalpel of pure category theory. Specifically, I will try to reinvent this definition wearing the hat of a category theorist who doesn’t know anything about “causality” or “processes”.

There is a straightforward way to try to make any closed symmetric monoidal category $\mathbf{D}$ into a $\ast$-autonomous one. Namely, pick an object $\bot$ and consider the subcategory of objects $X\in \mathbf{D}$ for which the double-dualization map $X \to (X\multimap\bot)\multimap \bot$ is an isomorphism. I don’t know the most general conditions under which this works, but one general case in which I’m pretty sure it works is when the self-duality adjunction $(-\multimap\bot)\dashv (-\multimap\bot)$ is idempotent, since then the subcategory in question is closed under $\multimap$, reflective (hence monoidal), and contains $\bot$. (An even more particular case of this is when $\mathbf{D}$ is a poset, since then all adjunctions are idempotent. This includes Girard’s original phase semantics of linear logic.)

Of course if $\mathbf{D}$ is already $\ast$-autonomous, with $\bot$ its dualizing object, then this construction gives $\mathbf{D}$ back again, and in particular that happens if $\mathbf{D}$ is compact closed (with $\bot = I$). So if we want to make a new $\ast$-autonomous category out of a compact closed one, we have to combine this construction with something else, and a natural choice is some sort of “free” or “universal” construction on our compact closed category $\mathbf{C}$. The first thing that would come to mind for me is the Yoneda embedding (with Day convolution), but another important such “universal” construction is Artin gluing and more specifically the scone. In the non-cartesian monoidal case, this means the comma category $scn(\mathbf{C}) = (Set\downarrow \mathbf{C}(I,-))$, whose objects are triples $(A,X,X\to \mathbf{C}(I,A))$.

If $A$ is closed symmetric monoidal, so is $scn(\mathbf{C})$. (More generally, if $F$ is colax monoidal and $G$ is lax monoidal, then the comma category $(F\downarrow G)$ is monoidal.) The tensor product is straightforward:

$$(A,X, X\to \mathbf{C}(I,A)) \otimes (B,Y, Y\to \mathbf{C}(I,B)) = (A\otimes B, X\times Y, X\times Y \to \mathbf{C}(I,A) \times \mathbf{C}(I,B) \to \mathbf{C}(I,A\otimes B).$$

The internal-hom $(A,X, X\to \mathbf{C}(I,A)) \multimap (B,Y, Y\to \mathbf{C}(I,B))$ is $A\multimap B$ equipped with the map $Z \to \mathbf{C}(I,A\multimap B) \cong \mathbf{C}(A,B)$ whose fiber over $f:A\to B$ is the set of liftings of $f$ to a morphism in $scn(\mathbf{C})$, i.e. the set of maps $X\to Y$ making the evident square commute.

Thus, from any closed symmetric monoidal category $\mathbf{C}$, if we pick an object $\bot$ and a function $Z\to \mathbf{C}(I,\bot)$, giving an object $\bot'$ of $scn(\mathbf{C})$, and we can then ask whether the induced adjunction $(-\multimap\bot')\dashv (-\multimap\bot')$ on $scn(\mathbf{C})$ is idempotent. Since $\multimap$ on $scn(\mathbf{C})$ acts as the original $\multimap$ on the $\mathbf{C}$ components, this requires the original adjunction $(-\multimap\bot)\dashv (-\multimap\bot)$ on $\mathbf{C}$ to also be idempotent. And since the fixed points of $(-\multimap\bot')$ will have fixed points of $(-\multimap\bot)$ as their $\mathbf{C}$ components, we might as well restrict ourselves to that latter category of fixed points to start with, which is to say we might as well assume that $\mathbf{C}$ is itself $\ast$-autonomous with $\bot$ its dualizing object.

This ensures that the double $\bot'$-dualization map is always an isomorphism on $\mathbf{C}$ components. To ensure that this adjunction is idempotent, therefore, it remains to consider the set components, and one natural way to make this happen is to make that “part” of the adjunction posetal. It certainly works if we simply restrict to the subcategory of $scn(\mathbf{C})$ where the function $X\to \mathbf{C}(I,A)$ is injective. I think it should also work if we assume merely that the map $Z\to \mathbf{C}(I,\bot)$ is injective, since then any hom-object $(A,X,c_A) \multimap \bot'$ will also have this property; but then any fixed point of $(-\multimap \bot')$ will also have this property, so we might as well have restricted to that subcategory in the first place.

So now what we have is a construction of a new “$\ast$-autonomous scone” starting from any $\ast$-autonomous category $\mathbf{C}$ equipped with a subset $Z$ of $\mathbf{C}(I,\bot)$. Its objects are objects $A\in \mathbf{C}$ equipped with a subset $c \subseteq \mathbf{C}(I,A)$ such that $c = c^{\ast\ast}$, where $c^{\ast}\subseteq \mathbf{C}(I,A^\ast) \cong \mathbf{C}(A,\bot)$ is the set of maps $\pi:A\to \bot$ such that for all $(\rho : I \to A) \in c$, the composite $I \xrightarrow{\rho} A \xrightarrow{\pi} \bot$ lies in $Z$. In particular, this applies when $\mathbf{C}$ is compact closed, with $\bot=I$, and where we can take $Z$ to be the singleton containing the identity, reproducing the main part of the definition of $Caus[\mathbf{C}]$.

So far we haven’t used any “discard processes” or any of the axioms of precausal-ness, and the only thing that’s missing from the definition of $Caus[\mathbf{C}]$ is the “flatness” condition (which refers to the discard processes). So that leads me to ask questions like:

1. Why are the “flat” objects closed under the $\ast$-autonomous structure of the scone? Presumably this uses the axioms of precausal-ness; does it use all of them?

2. What purpose does the “flatness” restriction serve?

3. For any scone there is a projection $scn(\mathbf{C}) \to \mathbf{C}$ preserving all the structure, and it’s interesting to ask to what extent (if any) it has a section. The blog post mentions that $C_C$ (what is that? The subcategory of causal maps?) embeds fully-fathfully in $Caus[\mathbf{C}]$; presumably this is a (partial?) section of this projection. How much of the axioms of precausal-ness does this statement use? Does it use all of them? If we assume only that such a (partial?) section exists, how much of the axioms of precausal-ness can we recover?

I’ll see if I can answer some of these questions, and try not to get cut. :)

1. Flatness is a pretty robust concept. All it depends on is that fact that the “raw materials” category C is compact closed, and precausal axiom (C1), namely that C is equipped with discarding maps $d_A : A \to I$, and they respect the monoidal structure. Then, preservation under tensor is immediate, and preservation under (-)* follows from the fact that the definition of flat is symmetric under taking the (compact closed) star of everything.

2. This is a bit more mysterious. Any object built up inductively from first-order objects and the *-autonomous structure is flat, however the converse is not true. So, flatness might not be the One True Definition needed for the Caus[C] construction.

   Intuitively, it is saying something like both c and c* have something that plays the role of a “top” element (or a “bottom” element, depending on how you order things). In the concrete model of stochastic maps, that element for first-order systems is the uniform distribution, for systems A -o B, this is the constant function on to the uniform distribution (aka the perfectly noisy channel) and so on.

   In particular, it guarantees that for any system (X, c), there is a canonical map in Caus[C] from (X,c) into the associated first-order system (X, {$d_X$}*) which is given by scalar multiplication (i.e. “renormalising”).

   A recurring theme in the paper is to start with a map between higher-order systems, use flatness to reduce the problem to first-order systems, then apply precausal axiom (4) to produce a factorisation.

   A big part of the story of causality is about factorisation. If a process factors in a certain way, this might not necessarily say certain causal relationships exist, but it does rule out certain possibilities, since there might be e.g. no way for information to flow from a certain input to a certain output. If you can rule out enough possibilities, you might be able to say something meaningful about the possibilities that are left. In statistical inference, this is basically the heart of the “constraint-based approach” to discovering causal relationships from data.

   But if you are using your scalpel correctly, I shouldn’t be telling you this. :)

3. Indeed, $C_c$ is the (wide) subcategory of C consisting just of those morphisms which satisfying the “causality postulate”, namely $d_B \circ f = d_A$. This gives a “partial” section to the projection of Caus[C] down to C (which I tend to think of as a forgetful functor, since it forgets the constraint c from the pair (X,c)).

   I think this section will already exist if you just have precausal axioms (C1) and (C3). Hence, its probably pretty easy to cook up examples which do have such a section, but are not precausal. For example, the category Rel of sets and relations (with tensor = cartesian product) only satisfies a weaker form of axiom (C4), called (C4’) in the paper, but still looks like a very interesting example to work with.

   Annoyingly, flatness breaks the “natural” choice for giving the forgetful functor left and right adjoints, namely sending A to (A, {}) and (A, C(I,A)), respectively. Neither of these sets are flat in general.