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: Chad Nester

Chad Nester (Feb 11 2024 at 16:09):

Hello everyone,

I've got a few new papers to advertise.

First, Protocol Choice and Iteration for the Free Cornering, together with @Niels Voorneveld. This extends the free cornering of a monoidal category to support additional protocol types, in particular branching protocols, in which one of the participants chooses which of two continuations will happen and the other must respond, and iterated protocols, in which the participants repeat all or part of a protocol some number of times, based on choices made during the process. If you have access to JLAMP you can get the "official" version, but frankly I think the preprint is more legible.

Chad Nester (Feb 11 2024 at 16:12):

Second, my PhD thesis, Partial and Relational Algebraic Theories has been successfully defended and is available from the university library. The thesis is a more careful development of the partial algebraic theories and relational algebraic theories from my published work.

I'll mention that only the first ~150 pages of the document on that website are the thesis monograph, with the rest being copies of my papers. It isn't that scary!

Evan Patterson (Feb 11 2024 at 20:04):

Congrats on the nice looking thesis! You should post it to arXiv (minus the copied papers). That will help people find it.

Matteo Capucci (he/him) (Feb 12 2024 at 07:58):

Congrats!

Chad Nester (Feb 12 2024 at 10:13):

Evan Patterson said:

Congrats on the nice looking thesis! You should post it to arXiv (minus the copied papers). That will help people find it.

I don't know whether or not I should do this. I'm planning to publish journal version of the two associated conference papers at some point using material from the thesis, so it might be better to wait. I don't really know.

Kevin Arlin (Feb 12 2024 at 21:20):

What downside are you envisioning?

Mike Shulman (Feb 12 2024 at 21:32):

I don't know what Chad is thinking, but my own thesis is put together from several papers, and I never put my thesis itself on the arXiv because I would rather that people read the papers instead, as they are more polished. However, this only works if the individual papers actually do get written.

Chad Nester (Apr 17 2024 at 15:31):

Tomorrow at 14:00 EEST (UTC+3) I'm giving a talk in Tallinn titled Elgot Categories and Abacus Programs. The talk will be broadcast via Zoom, and if you're interested in listening in send me a message here and I'll send you the details.

Abstract:
This talk concerns the categorical representation of the partial
recursive functions. Specifically, I will introduce Elgot
categories, which are a sort of structured rig category in which
all partial recursive functions are representable. Specifically, an
Elgot category is a (uniform) traced cocartesian rig category
with a distinguished isomorphism I+N→N for some object N.

I will construct an initial Elgot category, the morphisms of
which will coincide with the abacus programs of Lambek. Finally,
I will show that in this initial Elgot category, the class of
strongly representable partial functions is precisely the class
of partial recursive functions.

Chad Nester (Apr 17 2024 at 15:34):

I guess the main references are:

• Partial Recursive Functions and Finality by Plotkin.
• Deconstructing the Calculus of Relations with Tape Diagrams by Bonchi, Di Giorgio, and Santamaria.

Chad Nester (May 13 2024 at 13:18):

Today is my first day at my new job as a Research Fellow at the University of Tartu. It's a permanent position, which is exciting.

Chad Nester (May 24 2024 at 09:35):

Mike Shulman said:

I don't know what Chad is thinking, but my own thesis is put together from several papers, and I never put my thesis itself on the arXiv because I would rather that people read the papers instead, as they are more polished. However, this only works if the individual papers actually do get written.

I do eventually hope to publish the results from my MSc thesis :sweat_smile:

Chad Nester (May 24 2024 at 09:41):

In other news, I'll be attending a few conferences this summer:

• ACT/MFPS in Oxford, June 17-21. Here I'll give a talk about my thesis work on "Partial and Relational Algebraic Theories".
• CT in Santiago de Compostela, June 23-39.
• FSCD in Tallinn, July 10-13.

If you'll be at one or more of these and would like to talk about something specific, let me know and I can prepare a bit in advance :)

Chad Nester (Jul 02 2024 at 11:16):

On Monday, July 8th at 14:30 in Tallinn I'll be speaking at MSFP 2024 about my paper "Protocol Choice and Iteration for the Free Cornering" with Niels Voorneveld.

Chad Nester (Mar 28 2025 at 12:34):

I've put up a new thing on the arXiv: https://arxiv.org/pdf/2503.21434

It's about representing the partial recursive functions in distributive monoidal categories. The short version is that you need to be traced on the coproduct, and to have an isomorphism $I+N \to N$ hanging around somewhere. I think it's fun.

Chad Nester (Sep 17 2025 at 14:42):

I'd like to ponder something out loud here:

Let $\mathsf{List}(A)$ be the set of lists with elements in $A$, defined as usual to be the initial algebra of the endofunctor $X \mapsto 1 + (A \times X)$ on $\mathsf{Set}$. In particular let's write the initial algebra as $\langle \mathsf{nil} \mid \mathsf{cons} \rangle : 1 + (A \times \mathsf{List}(A)) \to \mathsf{List}(A)$, so that out lists look like the ones from functional programming.

Let $W$ be a set, and suppose that we have partial functions $\mathsf{push} : A \times W \to W$ and $\mathsf{pop} = \langle \mathsf{head},\mathsf{tail} \rangle : W \to A \times W$ such that $\mathsf{push};\mathsf{pop} = 1_{A \times W}$. Note as an aside that an immediate consequence of this equation is that $\mathsf{push}$ is total.

There is a total function $h : W \to \mathsf{List}(A)$ defined by $h(x) = \begin{cases} \mathsf{nil} & \text{ if } \mathsf{pop}(x)\uparrow \\ \mathsf{cons}(\mathsf{head}(x),h(\mathsf{tail}(x))) & \text{ otherwise}\end{cases}$

So for each $x \in W$ we have a list, $h(x)$. We do not, however, seem to be able to construct an element of $W$ for each element of $\mathsf{List}(A)$. In particular, it is unclear what we would map $\mathsf{nil}$ to.

Nonetheless, I can do quite a few list-like things with $W$. So long as I'm happy to have my function become undefined the moment it attempts to inspect an "empty" element of $W$ (on which $\mathsf{pop}$ is undefined), there would seem to be nothing I cannot do.

Chad Nester (Sep 17 2025 at 14:45):

Ah: a problem with this is that $\mathsf{pop}$ may in fact be total, in which case $W$ is a stream and my $h$ isn't well-defined, since I never reach a $\mathsf{nil}$.

Chad Nester (Sep 17 2025 at 14:58):

I guess I have the same thing happening, but with $\mathsf{CoList}(A)$ instead of $\mathsf{List}(A)$. Here by $\mathsf{CoList}(A)$ I mean the terminal coalgebra of the endofunctor $X \mapsto 1 + (A \times X)$. So a colist is a "possibly finite stream" or equivalently a "possibly infinite list".

Chad Nester (Sep 17 2025 at 15:10):

I would imagine that $h : W \to \mathsf{CoList}(A)$ is injective, but not surjective. I think I probably need to work out some examples if I want to understand this...

Mike Shulman (Sep 17 2025 at 15:12):

I presume you meant your $h$ to be recursive on tail in the otherwise case.

Chad Nester (Sep 17 2025 at 15:12):

Yes, thank you. I've fixed it.

Mike Shulman (Sep 17 2025 at 15:13):

Of course, a partial function $\mathsf{pop} : W \to A\times W$ is the same as a total function $W \to 1 + (A \times W)$, so then your $h$ is exactly the unique map from a coalgebra to a terminal coalgebra.

Mike Shulman (Sep 17 2025 at 15:15):

In general that won't be injective or surjection, and I don't see see why the additional presence of push would make it injective.

Chad Nester (Sep 17 2025 at 15:17):

Hmm, we do know that $\mathsf{push}$ is injective because it is a section... which doesn't really seem to help here.

Chad Nester (Sep 17 2025 at 15:22):

Right: if $\mathsf{pop}$ is undefined on two distinct elements of $W$ then $h$ is not an injection.

Chad Nester (Sep 17 2025 at 15:48):

I think this might be a good way to talk about what's going on in Lisp with car/cdr and "improper lists"