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: theory: applied category theory

Topic: Coalgebras and convergence of sequences

Nathaniel Virgo (Apr 11 2021 at 01:58):

Recently, I keep ending up in a situation where I have a sequence defined by a coalgebra, and I want to be able to talk about whether it converges to some value. I'm working in a probability context, but I think the principle is quite general, so I'll formulate the question in terms of a simpler example. (Apologies if this means I need to move the goalposts later.)

So, suppose my objects are $\mathbb{R}^n$ for $n\in \mathbb{N}$, my morphisms are smooth maps, and I think of this as a monoidal category where the monoidal product is the Cartesian product of the underlying spaces. Then suppose I have a morphism $f\colon X \to X\otimes A$, for some $X=\mathbb{R}^m$ and $A=\mathbb{R}^n$, along with an element $x_0\colon 1 \to X$. This defines a sequence where the $k^\text{th}$ element is given by

image.png

The interpretation is that $X$ is the hidden state of a "machine" that repeatedly produces outputs in $A$.

The question is simply whether there's a nice category-theoretic way to say whether this sequence converges to some fixed value in $A$, i.e. $\lim_{k\to\infty} a_k = a_\infty$ for some element $a_\infty\colon 1\to A$. Ideally, I'd like to be able to say this without needing to assume that the internal state $X$ converges to a fixed value.

Or even more usefully, if I have two such sequences, defined by $(x_0\colon 1\to X, f\colon X\to X\otimes A)$ and $(y_0\colon 1\to Y, f\colon Y\to Y\otimes A)$, is there a way to say that their output sequences become asymptotically close to each other?

My hope is to be able to say this in a fairly general way, that's not too dependent of the specifics of the category I described, so that we can talk about convergence of sequences in "any category where that makes sense", if it's possible to do that. Is there a way that this can be done?

Nathaniel Virgo (Apr 11 2021 at 02:14):

After posting this it occurred to me that if the category is enriched in $\mathrm{Top}$ then these sequences of morphisms are actually sequences in a topological space, namely $\operatorname{Hom}(1,X)$, so I can just ask whether they converge in the usual sense. I guess the question is whether there are necessary and/or sufficient conditions for this that can be expressed as properties of the morphisms $f$ and $x_0$ in the original category. In other words, how much can be said about convergence of sequences in a category without needing to explicitly construct the enrichment?

Mike Shulman (Apr 11 2021 at 03:44):

I don't know how you could say anything about whether a sequence converges without knowing what the topology is with respect to which you're asking about convergence.

Nathaniel Virgo (Apr 11 2021 at 04:19):

I guess I was imagining it would be implied by the structure of the category somehow. For example, in this case I specified that the maps are smooth, which implies they're continuous with respect to the usual topology on $\mathbb{R}^n$, so in some sense the category "knows" about that topology, and I was hoping that would be enough to say something.

Nathaniel Virgo (Apr 11 2021 at 05:02):

Or to put it another way, you have to specify a topology to talk about convergence, but there's very often a natural choice of which topology is relevant. It doesn't seem completely implausible to me that one could say something like "we say $(x_0,f)$ converges iff there exists an object such that...", in such a way that in this example it would be the same as saying the sequence $x_1, x_2,\dots$ converges in $\mathbb{R}^n$, but in some other case it would mean it converges in some other topology. I've no idea how plausible that is, but it seemed like it might be worth asking in case something like it has been worked out.

Jules Hedges (Apr 11 2021 at 08:53):

This is purely a guess, but metric coinduction might be what you need? https://arxiv.org/abs/0908.2793

Nathaniel Virgo (Apr 11 2021 at 09:37):

Sounds like it might be! I'll look into this.

Jules Hedges (Apr 11 2021 at 09:40):

It probably depends on what you need. If your sequence converges because your transition function $f$ is a contraction mapping on metric spaces, then this is probably what you need. If your sequence converges for some other reason, then probably not

Mike Shulman (Apr 11 2021 at 18:12):

Well, there is synthetic topology, which can be interpreted internally in a sufficiently structured category.

Eigil Rischel (Apr 13 2021 at 18:14):

You may also be interested in the characterization of the real numbers due to Escardo-Simpson: https://ieeexplore.ieee.org/document/932488
If $m(x,y)$ is the midpoint of $x,y$, then given any coalgebra like $a: X \to X \times [0,1]$, there is a unique $u: X \to [0,1]$ so that $u(x) = m((u \times 1_{[0,1]})(a(x)))$, namely $u(x)$ is the "iterated midpoint" $\sum_{n=1} \frac{1}{2^n}a_n$, if $a_n$ is the sequence generated by $x$.

Nathaniel Virgo (Apr 14 2021 at 01:55):

Oh, that looks great too! There are some really useful ideas in that paper. Thank you very much!

Nathaniel Virgo (Apr 14 2021 at 02:10):

A bit off topic, but I wonder how their "abstract convex bodies" relate to algebras of the distribution monad, which are also an abstract formulation of convex things. In fact I guess you could define the distribution monad in terms of their "free convex bodies", which seems pretty interesting.

Eigil Rischel (Apr 14 2021 at 07:11):

Well, of course the distribution monad is defined in terms of the real numbers (a distribution being a finitely-supported function $X \to [0,1]$, so I guess there could easily be a connection of some sort.