Non-deterministic Markov category, is it a thing? · learning: questions

So I'm working with a category where the objects are sequence types and the morphisms are processes that take these sequences and do stuff to them. I could write Seq A for "sequence of things of type A" but for brevity I will just write A because everything is a sequence. We have the obvious identity morphism. We have a discard morphism that just eats As and produces nothing (well, unit, I guess). And we have copy : A -> (A, A) that duplicates the stream. All of this is very nice and looks to me like something related to a Markov category. So far so good.

Now there is this other morphism that I'm calling merge : (A, B) -> A + B. This one takes a sequence of As and a sequence of Bs and produces a sequence of messages (I'm going to start calling them messages, because that's what they are) that can be either of type A or B.

p : Seq Int
p = (1,2,3,4,5,...)

q: Seq Char
q = (a,b,c,d,e,...)

then merge p q could produce (1,a,2,b,3,c,...) or (1,2,a,3,b,c,d,4,...) or anything like that, according to the order in which messages arrive.

This merge is a strange thing. It is not the inverse of copy. It produces a sum type. It is non-deterministic. And it turns out to be quite important for the setting in which I am working.

The question is... What is this thing? Is it a known thing? I feel that it must be. Does this merge do something upsetting that means we lose some nice property of monoidal categories?

John Baez (Mar 03 2026 at 00:51):

I don't know much about this but I'll feebly try to get the ball rolling. You seem to be working in some category of sets and "nondeterministic maps", where a nondeterministic map

f: A \to B

is a map

f: A \to PB

where

P

is the power set monad. This is a well-known category (the Kleisli category of the covariant power set monad), but I don't know if it's a Markov category. I guess it "should" be.

where

!A

is the set of all sequences of elements in

A

. This nondeterministic map sends a sequence

\alpha

A

and a sequence

\beta

B

to the set of all sequences in the disjoint union

A + B

that "at each stage pick an item from either the sequence

\alpha

or the sequence

\beta

, and always go forward through these sequences, and eventually pick every element of both sequences". (That's a rather crappy way to say it, neither very precise nor very intuitive, but there's a precise concept here.)

ww (Mar 03 2026 at 09:10):

Ah, I like the ! syntax. Yes, think that is an accurate description. I guess my question is: is that map known and studied? In particular, is it known to be badly behaved in some way that will foreseeably bite me (you can tell, I'm a bit suspicious of it even though it seems like an obvious thing to do...)

Tobias Fritz (Mar 03 2026 at 09:14):

If you take the full power set monad on Set, then the Kleisli category that you get is [[Rel]], because a map

A \to PB

is the same thing as a relation between

A

and

B

(and this identification is compatible with composition). This is not quite a Markov category because the discards are not natural (or equivalently the monoidal unit is not terminal), but a copy-discard category. If you use the nonempty powerset monad, then you get a subcategory of Rel consisting of the total relations. This is a Markov category that we also denote by SetMulti, because the morphisms can also be thought of as multivalued functions.

Tobias Fritz (Mar 03 2026 at 09:15):

So the question is whether in your form of non-determinism, something is guaranteed to happen, or whether your operations are allowed to output nothing at all. In the former case you probably indeed want a Markov category like SetMulti, whereas in the latter case you'll want a CD category like Rel.

Tobias Fritz (Mar 03 2026 at 09:22):

I don't know more about the merge of sequences, but it looks like an intriguing construction!

ww (Mar 03 2026 at 09:57):

Interesting. I suppose something is expected to happen and will happen unless there is an error or a bug. But then errors and bugs are also "something" and in practice can be treated as option. The only operation that is allowed to output nothing at all is discard which we need because sometimes a process will produce output that we do not want so we need somehow to throw it away.

Here we have processes (morphisms) that can do things like write to disk so without pulling in unnecessarily heavy ideas from languages like haskell, I guess this is a CD category not a Markov category. That's a pragmatic choice though, in principle a pure version might be possible.

Tobias Fritz (Mar 03 2026 at 11:38):

Just a minor addition: keep in mind that to "output nothing" is not the same as failing. Semantically, the relation

X \to I

that corresponds to successfully outputting nothing is the one which relates every element of

X

to the unique element of

I

, and it's the unique total relation of this type. A general relation

X \to I

is a subset of

X

, which one can think of as the subset of states on which it succeeds.

Tobias Fritz (Mar 03 2026 at 18:42):

One more observation: I wonder if it could be more fruitful to think of your merge as a morphism of type

!A \times !A \to !A

, meaning such that it only merges two sequences with elements from the same alphabet. (Combining this with the coproduct inclusions

A \to A+B \leftarrow B

still lets you do the general case, so you don't lose anything.) Then these relations seem to equip every object with a commutative and associative comultiplication. Am I getting this right?

Tobias Fritz (Mar 03 2026 at 18:42):

Now since domain and codomain of a relation can always be swapped, you can also think of

!A

as being equipped with a commutative and associative multiplication. Now perhaps it's interesting to see whether these structures interact in a way which satisfies the Frobenius law or the bialgebra law?

ww (Mar 04 2026 at 08:39):

interesting. yes, you're right. and we can always filter them out to separate them later.