$\Delta (- \times A)$ -coalgebras vs $- \otimes A$ -coalgebras [efr-003T]

July 23, 2024
Eigil Fjeldgren Rischel

Both the endofunctor $\Delta (- \times A): \mathsf {Meas} \to \mathsf {Meas}$ , and the endofunctor $- \otimes A: \mathsf {Stoch} \to \mathsf {Stoch}$ express the idea of a stochastic transition system which produces an output in the measurable space $A$ at each step. (We could also have considered the similar endofunctor on $\mathsf {Set}$ , using a discrete probability monad, and its Kleisli category). In fact, in one sense, these are equivalent---since $\mathsf {Stoch}$ is the Kleisli category of $\Delta ,$ and $\otimes$ on objects is simply defined as the product measurable space, the sets $\mathsf {Stoch}(X,X \otimes A)$ and $\mathsf {Meas}(X, \Delta (X \times A))$ are by definition equal to each other.

The difference is in the category of coalgebras. A morphism between $\Delta (- \times A)$ -coalgebras must be deterministic---it must assign to each $x \in X$ a $y \in Y$ so that the obvious diagram commutes. In contrast, a morphism on $- \otimes A$ -algebras is a morphism in $\mathsf {Stoch}$ ---it must assign to each $x \in X$ a distribution on $Y$ , so that the two implied distributions on $A \times Y$ agree.

We can see the difference most clearly if we consider which properties are bisimulation invariant (i.e are properties of "behaviours"). We have seen that the terminal $- \otimes A$ -coalgebra is $A^\omega$ , so a behaviour in this sense is simply a distribution on streams---the questions we can ask are what the probability of a certain sequence of outputs is.

In contrast, of an element in a $\Delta (- \times A)$ -coalgebra, we can ask a question like this: "What is the probability that, after 10 steps, we will be in a state which produces output $a$ with probability at least $p$ "? In a $- \otimes A$ -coalgebra, we can ask "what is the probability that the output on the 11th step is $a$ ", or "what is the probability that, after 10 steps, the conditional probability of the next output being $a$ , conditional on the first 10 outputs, is at least $p$ ?"---but we cannot access the probabilities of an output given the future state directly, only the correlations that exist between the outputs.