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!