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: community: our work

Topic: Rémy Tuyéras

Rémy Tuyéras (Jul 08 2024 at 02:27):

Logical independence versus Probabilistic independence

Recently, I found a formula that clarifies the link between stochastic and logical independence, but I'm still struggling to escape the measure theory aspect. Ideally, my goal would be to abstract both concepts of independence in a single setting.

For anyone reading this: I am potentially looking for insights or references that could help clarify the content below in terms of category theory. Any direction or references would be welcome.

Logical independence

For a given set of axioms $B$ (say written in a logic $\mathcal{L}$ which uses propositional logic as a basis), define $\neg B:= \{\neg \varphi~|~\varphi \in B\}$.

One says that a set $B$ of axioms in $\mathcal{L}$ is independent from another set $A$ of axioms in $\mathcal{L}$ if we can find two models $\mathcal{M}$ and $\mathcal{M}'$ such that:

$\mathcal{M} \vDash A \cup \neg B$

$\mathcal{M}' \vDash A \cup B$

Stochastic independence

Let $(\Omega,\mathcal{E},P)$ be a measure space for a probability measure $P:\mathcal{E} \to [0,1]$.

For every pair $(A,B)$ of events $A \in \mathcal{E}$ and $B \in \mathcal{E}$, we define $\delta(A,B) = P(A\cap B)-P(A)P(B)$. We say that the events $A$ and $B$ are independent if the formula $\delta(A,B) = 0$ holds.

Proposition. The formula $\delta(A,B) = P(A \cap B)P(A^c \cap B^c) - P(A \cap B^c)P(A^c \cap B)$ holds.
proof. Write $P(A) = P(A \cap B) + P(A \cap B^c)$ and $P(B) = P(B \cap A) + P(B \cap A^c)$ and insert these expressions in the expression for $\delta(A,B)$. Expand, then factor out $P(B \cap A)$ and finally observe that
$P(A^c \cap B^c) = 1- P(B \cap A) -P(B \cap A^c)-P(A \cap B^c)$
$\square$

Now, our goal is to reformulate the expression above. For this, we can use the product probability measure $P_2:\mathcal{E}\otimes \mathcal{E}\to [0,1]$, which is generated by the images $P_2(X \times Y) = P(X)P(Y)$ for every $(X,Y) \in \mathcal{E} \times \mathcal{E}$. Also, for every pair $(X,Y)$ of events in $\mathcal{E}\times\mathcal{E}$, let us denote $X \oplus Y = (X \cap Y^c) \times (X^c \cap Y)$.

Our new notations reduce the expression of $\delta(A,B)$ to this:

$\delta(A,B) = P_2\big(A \oplus B^c\big) - P_2\big(A \oplus B\big)$

In other words, two events $A$ and $B$ are independent if the probability of finding a configuration in $\Omega \otimes \Omega$ that validates the event $A \oplus B^c$ is equal to the probability of finding a configuration in $\Omega \otimes \Omega$ that validates the event $A \oplus B$.

Conclusion and question

There seems to be an analogy between stochastic and logical independence here. I tried to come up with an algebraic definition of stochastic independence by requiring a bijection $A \oplus B^c \cong A \oplus B$, but this hasn't helped me escape the probability measure context.

Does anyone have intuitions on this or know some references that have explored this?

Eric M Downes (Jul 08 2024 at 04:02):

How about $\Sigma$-algebra instead of measure theory?

Every [[sigma algebra]] is a boolean algebra with countable joins, and in which every non-bottom element is a member of a maximal filter closed under countable meets... IIRC thats the same as "complete". Books on boolean algebras should have this, and it looks like the connection you are making, at least from a distance. I believe you could phrase $p$ just as a monotonic (along inclusions) map from the lattice of subsets to the total order on $\mathbb{R}$. In logic the appropriate codomain is then just $\mathbb{B}$ I guess. A rewrite in terms of monotonic-maps of locales should be immediate, and that at least escapes (explicit) measure theory to something category-adjacent.

Matteo Capucci (he/him) (Jul 08 2024 at 07:11):

Unfortunately a measure is not just a map of lattices, since it maps antichains of the algebra to sums in R. That's the fundamental quirk that messes up measure theory (and makes it useful, really)

Eric M Downes (Jul 08 2024 at 07:20):

Thanks, Matteo. If you impose inclusion-exclusion as an extra assumption, which already holds for the [edit: finite] rank functions of modular lattices, is that insufficient?

(just to state things explicitly: every distributive lattice is modular, rank functions are monotonic maps from graded posets to $\mathbb{Z}$, which morally at least seems generalizable, IE for two lattice elements is $p(x\vee y)+p(x\wedge y)=p(x)+p(y)$ where $p$ is a rank function, and IE has higher-order expressions as well, with alternating signs like Euler's Characteristic, as well as a generalization due to Rota for arbitrary posets.)

Eric M Downes (Jul 08 2024 at 07:21):

Oh sorry that's only the finite case.

Eric M Downes (Jul 08 2024 at 07:30):

I have not understood this paper by Peter May, so I may be missing badly, but it discusses inclusion-exclusion in the deepest and broadest context of which I am aware, and seems broadly applicable. And I believe IE is sufficient to get antichains to map to sums, so even if the lattice is not finite modular and you don't have IE for a rank function for free, maybe the category you want to generalize to is triangulated, and that could help.

Sam Staton (Jul 08 2024 at 07:59):

I might be misunderstanding this discussion, but if not, one nice angle is effect algebras. These sort-of generalize Boolean algebras by thinking in terms of partial operations.

On a finite set $n$, a probability measure is the same thing as an effect algebra homomorphism $P(n)\to [0,1]$. Here $P(n)$ is regarded with the partial monoid structure given by disjoint union, and $[0,1]$ is regarded with the partial monoid structure given by addition where it is possible.

It's not as ad hoc as it might sound because these things fully embed in presheaves on finite Boolean algebras.

For the infinitary case, there are $\sigma$-effect algebras which have the analogous correspondence, since every $\sigma$-algebra is also a $\sigma$-effect algebra.

Matteo Capucci (he/him) (Jul 08 2024 at 09:33):

Eric M Downes said:

Thanks, Matteo. If you impose inclusion-exclusion as an extra assumption, which already holds for the [edit: finite] rank functions of modular lattices, is that insufficient?

(just to state things explicitly: every distributive lattice is modular, rank functions are monotonic maps from graded posets to $\mathbb{Z}$, which morally at least seems generalizable, IE for two lattice elements is $p(x\vee y)+p(x\wedge y)=p(x)+p(y)$ where $p$ is a rank function, and IE has higher-order expressions as well, with alternating signs like Euler's Characteristic, as well as a generalization due to Rota for arbitrary posets.)

The main problem is that $(\overline\R,+)$ is not a lattice since $+$ is not idempotent. This problem aside, asking explicitly for an inclusion-exclusion relation does work (you can concot a suitable version for the countable case) but then your just asking explicitly for it, not hiding it in the underlying structure :(

Eric M Downes (Jul 08 2024 at 09:53):

(I think you need the codomain to be an ordered ring, not a lattice for monotone maps from a lattice to express independence (as in, have the possibility of being homomorphic on meet), but maybe I misunderstand what Remy is trying to do here, and admittedly I have not looked into this in detail.)

Regarding asking for IE explicitly -- yeah totally its not elegant, but the purpose was to allow us to abstract away from measure theory, and I was suggesting doing that by using lattices + IE as the latter plays well with lattices, and is an example of a kind of categorical trace discussed in the May paper. (The effect algebras Sam Stanton suggested seem like they are nearly lattices, and quite interesting.)

Rémy Tuyéras (Jul 08 2024 at 23:00):

@Eric M Downes @Matteo Capucci (he/him) @Sam Staton Thanks for the feedback! It will take me some time to go through it all (got a pretty busy week :grimacing:), but that's the kind of feedback I was looking for!

Rémy Tuyéras (Jul 18 2024 at 10:38):

This Saturday, I will be flying to Tokyo to give a talk at the FHE & MPC Tokyo Residency, organized by the Ethereum community. Ethereum is also hosting the EDCON 2024 in Tokyo during that time.

At the residency, I will present my paper on Constructing a Fully Homomorphic Encryption Scheme with the Yoneda Lemma. The audience will have diverse math backgrounds, though most will not be familiar with category theory.

In a few lines, asymmetric cryptography has been relying on the commutativity of the Yoneda Lemma to produce cryptosystems with sound correctness. For example:

1. In ElGamal, you take a (commutative) group $G$, choose a secret key $x \in \mathbb{Z}$ and publish the power $g^x$ for some publicly known $g \in G$. To encrypt a message $m \in G$, choose a homomorphism of the form $h:f \mapsto f^y$ and send the ciphertext $(h(g),m\cdot h(g^x))$.

   How do you decrypt this ciphertext? If you have the secret key $x$, you can compute $m = m\cdot h(g^x) \cdot (h(g)^{x})^{-1}$.

2. With lattic-based frameworks, you take an $R$-module $M$, choose a secret key $x \in M^n$ and publish a vector of the form $Ax+e$ for some publicly known $(n,N)$-matrix $A$ and (forgettable) small random vector $e \in M^N$. To encrypt a message $m \in M$, choose a homomorphism of the form $h:f \mapsto y^Tf$ and send the ciphertext $(h(A),m + h(Ax+e))$.

   How do you decrypt this ciphertext? If you have the secret key $x$, you can compute $m \simeq m+h(Ax+e)-h(A)x$.

Conclusion: the main ingredients to the decryption algorithms are the commutativity equations:

• $h(g^x) = h(g)^x$ and
• $h(Ax) = h(A)x$.

Now where is Yoneda? Well, for a given limit sketch $T$, the Yoneda Lemma gives us an isomorphism

$\mathsf{Hom}(T(d,-),X) \cong X(d)$

representing any morphism $g:T(d,-) \to X$ as some map "$x \mapsto \langle g, x\rangle$" for some representative $g \in X(d)$. And for every morphism $h:X \to Y$, it also gives us the naturality property

$h(\langle g, x\rangle) = \langle h(g), x\rangle,$

which is basically recovering the commutative ingredient needed to decrypt in ElGamal and lattice-based systems. After noticing that, you can write down what you need to recover most FHE cryptosystems using the Yoneda Lemma. As a direct application, you can choose arbitrary theories $T$ and see what kind of cryptosystem you get.

Rémy Tuyéras (Sep 18 2025 at 11:07):

Hello all, it has been a while.

I wanted to share an update that connects directly to higher category theory and agent systems.

TL;DR. I have been building Summoner, a Python SDK with a Rust server that orchestrates multi-agent systems using the language of category theory and higher structures (2-categories, weak higher categories). The client–server layer can be modeled as a localization of models

$[T,\mathbf{Set}] \to \mathbf{Mod}(T) \hookrightarrow [T,\mathbf{Set}]$

for a Lawvere theory $T$.

Context

If you have explored multi-agent frameworks such as LangChain, CrewAI, LangGraph, MCP, or Google's A2A:

• LangChain / CrewAI: application frameworks where you compose behaviors as a graph.
• LangGraph: a graph engine/DSL for stateful agent workflows on top of LangChain.
• Google A2A: a client-server protocol that exchanges JSON-encoded actions (JSON-RPC by default).
• MCP: a one-client/many-server protocol for model-to-tool requests and data connections.

Summoner aims to unify these views in a single language grounded in categories and higher structure, while keeping the ergonomics of decorator-based Python.

From decorators to arrows

In MCP-style stacks you often register a tool by decorating a function:

@mcp.tool("signal_X")
def process(the_input):
    # ...
    return my_output

Semantically, when the server supplies an input tagged signal_X, the system applies process:

$(\texttt{the\_input}, \texttt{signal\_X}) \xrightarrow{\;\texttt{process}\;} \texttt{my\_output}.$

This is simple and local; many users start here.

What graph-based frameworks look like in practice

Graph frameworks then ask you to wire nodes and edges explicitly. For readers who have not used them, the code often looks like:

workflow = SomeFramework()

def agent_behavior(...):
    # define some agent behavior
    ...

def another_agent_behavior(...):
    ...

# associate objects with functions
workflow.add_node("object_A", agent_behavior)
workflow.add_node("object_B", another_agent_behavior)

# draw the edge
workflow.add_edge("object_A", "object_B")

This is workable for small demos. At scale it becomes heavy on bookkeeping: keeping names synchronized with functions, reviewing edge lists for correctness, and debugging topologies instead of focusing on agent behavior.

Summoner: routes as arrows, flows as automata

Summoner combines decorator ergonomics with categorical structure.

You program routes that you read as labeled arrows and higher cells. Objects are routable names, and arrows are routable labels between them. You write handlers with decorators, and the runtime treats incoming messages as transitions in a small automaton generated by those routes.

Objects $A, B$:

# Object-activated behaviors
@agent.receive(route="object_A")
def on_A(input_A):
    ...

@agent.receive(route="object_B")
def on_B(input_B):
    ...

Arrows $f, g: A \to B$ as labeled routes (read $A \xRightarrow{f} B$):

# A ==[ arr_f ]==> B
@agent.receive(route="object_A --[ arr_f ]--> object_B")
def on_f(payload):
    ...

# A ==[ arr_g ]==> B
@agent.receive(route="object_A --[ arr_g ]--> object_B")
def on_g(payload):
    ...

A 2-cell $\eta: f \Rightarrow g$ as a route between arrows:

# f =={ eta }==> g
@agent.receive(route="arr_f =={ eta }==> arr_g")
def on_eta(event):
    ...

Custom arrow notation

You can customize the surface grammar of arrows to match the structure you want to emphasize, including double-category-style notations:

flow = agent.flow().activate()
flow.add_arrow_style(stem="-", brackets=("[", "]"), separator=",", tip=">")
flow.add_arrow_style(stem="=", brackets=("{", "}"), separator=",", tip=")")

# Use your preferred notations in routes:
@agent.receive(route="object_A --[ arr_f ]--> object_B")
def on_f(...): ...

@agent.receive(route="arr_f =={ eta }==) arr_g")
def on_eta(...): ...

Semantics sketch

Operationally, routes generate the path category of the underlying graph, and message handling interprets this free category into an effects category (for example, the Kleisli category of an async monad). Equivalently, one can view this using the underlying localization of a (higher) Lawvere theory, where:

• a message $m$ is an element $m \in F(t)$;
• the route = t label is a type in the theory;
• computing the underlying model of $F: T \to \mathbf{Set}$ amounts to building transfinite closures over pairs $(m,t)$, yielding $F'(t)$ for a localized model $F': T \to \mathbf{Set}$.

I would welcome feedback on a functorial account, naturality properties, or an open-systems perspective using cospans and pushouts for wiring. A merge operator already exists to compute colimits of the route graph.

What this enables in practice. Using this route language, we have implemented end-to-end agent workflows: protocol handshakes (challenge–response with nonces and replay protection), capability and version negotiation, and multi-round coordination (bids/asks, quorum/commit).

Happy to discuss, and to align the notation with whatever categorical lens the community prefers.

This project is also the base for a startup I founded with two colleagues, but the work remains open source. If you want to see more:

• The project: https://github.com/Summoner-Network
• Code examples: https://github.com/Summoner-Network/summoner-agents
• Docs: https://github.com/Summoner-Network/summoner-docs
• Website: https://summoner.org/

John Baez (Sep 18 2025 at 11:08):

Cool! Since you called this software Summoner, I momentarily read

This is workable for small demos.

as

This is workable for small demons.

David Michael Roberts (Sep 19 2025 at 00:13):

@Rémy Tuyéras cool! I was looking for a license for your codebase, but it wasn't leaping out to me. What are you using?

Rémy Tuyéras (Sep 19 2025 at 16:16):

@John Baez @David Michael Roberts Thanks for the feedback!

@David Michael Roberts we are under Apache-2.0. I have added LICENSE files across the repos.

David Michael Roberts (Sep 19 2025 at 21:43):

Thanks!

Rémy Tuyéras (Feb 12 2026 at 18:42):

Hello CT community! I have some news on my project Summoner, which I think could interest category theorists that are currently exploring applications to the industry.

1) AI-first businesses are increasingly exploring graph-like structures...

...and category theory could be next!

Understanding the impact of decisions in a business process is high-stakes. Since LLM-based agents do not reliably anticipate the operational impact of their choices, many AI-first companies are turning toward graph-structured representations to make decision traces, dependencies, and alternatives explicit.

The main trigger that helped push this framing is the "context graphs" article from Foundation Capital: AI’s trillion-dollar opportunity: Context graphs

After that, a large number of articles flooded the AI business space, for example:

• https://www.linkedin.com/pulse/how-do-you-build-context-graph-jaya-gupta-xicwe/
• https://subramanya.ai/2026/01/14/context-graphs-are-a-trillion-dollar-opportunity-but-who-captures-it/
• and many more

At Summoner, we see a natural next step after graphs: compositional and/or higher structures. Once you start taking graphs seriously, you quickly run into questions about how you represent not only decisions, but also revisions, exceptions, and amendments, and how these interact with the rest of the process. This is where the internal category-theoretic language becomes useful.

This is also the direction we have been taking on the business side: leveraging the internal category-theoretic language of Summoner to provide analytics on decisions and their dependencies, including counterfactual comparisons of "what happened" versus "what could have happened".

Concretely, we have recently demonstrated how businesses can leverage two-level category-like structures to analyze the impact of AI agents’ decisions on business operations: mini demo here

gif

These structures can be compared to 2-categories, if you infer a whiskering-style logic for composing decisions and amendments between decisions. In that framing, you can reason about "arrows between arrows", and track how amendments propagate through an execution trace.

2) Intro seminar

We are organizing an intro seminar to the Summoner platform and how to get started with agents. If time allows, we will also explore the underlying graph/category structure of the Summoner SDK and how it supports robust agent orchestration.

Register here if you are interested to learn more: https://luma.com/g3rcz6gg

3) Community

We are trying to build a community around robust orchestration for the emerging AI economy. I strongly believe category theorists have a real role to play here, from high-level design all the way to implementation details.

If you have been thinking about how category theory (or your current work) could interact with AI systems and with the economic/organizational layer that is forming around them, I think you should join us.

And even if you do not work on AI directly but like the ideas of the project, please consider supporting it by giving us a few GitHub stars. That genuinely helps with visibility and fundraising.

You can explore the docs: link

And the category-based examples are here: link

Rémy Tuyéras (Aug 22 2026 at 14:53):

Hello,

I recently got some new research results on a connection I have been exploring between Transformers and Category Theory (preprint). The paper is written for the ML/Transformer community because the contribution is experimental, but the construction itself has a fairly direct categorical interpretation.

The basic idea is to associate a lexical vocabulary $\mathcal{W}$ (e.g. $\texttt{"The"},\texttt{" king"},\dots$) with compositional paths over a small alphabet $K$ (e.g. $1,2,3,\dots$). Each lexical entry is assigned injectively to a path of length $S$:

$\phi:\mathcal{W}\hookrightarrow K^S.$

From a category-theoretic perspective, I think of the admissible coordinate paths as morphisms in a small category $\mathcal{C}$. On the lexical side, lexical units can also be viewed as morphisms whose composition is admissible concatenation. For example:

$\texttt{"The"}\circ\texttt{" king"}=\texttt{"The king"}.$

The encoding then extends as a functor, with

$\phi(f\circ g)=\phi(f)\circ\phi(g).$

Since the representation is injective on lexical morphisms, it is faithful on the represented lexical category.

The important distinction from a monoid encoding is that composition is constrained: not every coordinate can compose arbitrarily with every other coordinate. A lexical identity is itself represented by a composable path

$\phi(w)=c_1\circ c_2\circ\cdots\circ c_S.$

The paper has two results that seem particularly interesting from the point of view of category theory.

1. Using $\mathcal{C}$ instead of $\mathcal{W}$

Instead of training a Transformer on the atomic morphisms $w\in\mathcal{W}$, we train it autoregressively on the factors $c_i$. It therefore generates a composition

$c_1\circ c_2\circ\cdots\circ c_n$

one morphism at a time. Blocks of these morphisms correspond to lexical morphisms. For example,

$[c_1\circ c_2\circ c_3]\circ[c_4\circ c_5\circ c_6]\circ\cdots$

can be lifted back, on the image of $\phi$, to

$\texttt{"The"}\circ\texttt{" king"}\circ\cdots.$

Experimentally, learning this factorized categorical representation gives substantially better held-out BPB than learning the corresponding atomic lexical representation.

The intuition is that an atomic model must choose $\texttt{"The"}$ in one step, whereas the constructive model factors the same lexical morphism:

$\texttt{"The"}\longleftrightarrow c_1\circ c_2\circ c_3.$

The factors $c_i$ are shared among many lexical morphisms. After generating $c_1$, the model has not yet committed to one lexical identity, but it has selected a family of possible factorizations, which subsequent compositions refine.

This is why I tend to think of the path as a kind of constructive proof of lexical identity, where the model reaches a lexical morphism by composing intermediate morphisms rather than selecting it atomically.

The statistical control used in the paper is particularly simple from a category-theoretic perspective: we apply a random permutation $\pi$ to the occupied paths in $\mathcal C$. The permutation preserves the same paths as a set but is not required to preserve composition. Thus, although $\phi$ is functorial, the reassigned map

$\phi_\pi=\pi\circ\phi$

is generally not. Experimentally, destroying this functorial structure substantially degrades learning.

2. Adapting the Transformer architecture

The paper also introduces Intuitionistic Language Models (ILMs), which modify the Transformer to explicitly use the factorization structure.

Full ILM distinguishes the roles of the factors $c_i$ through role-specific input embeddings and output heads, together with supervision adapted to incomplete prefixes of a factorization. This improves learning further relative to an ordinary Transformer on the same paths.

I do not yet have a clean category-theoretic formalization of this second construction. The closest picture I have is a structure in which each lexical morphism $f$ comes with a distinguished factorization

$f=c_1\circ c_2\circ\cdots\circ c_k,$

and the Transfomer architecture is explicitly aware of the role of each factor in that factorization.

I have been wondering whether some form of multi-factorization system, graded category, or category equipped with distinguished factorizations is the right language for this.

I would be very interested to hear whether this reminds anyone of an existing category-theoretic construction, especially one where morphisms come with distinguished reusable factorizations and where those factorizations can themselves be treated as the objects of sequential computation.