Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

January 25, 2011

Coalgebraic Tangles

Posted by David Corfield

I’m sinking in a sea of administrative duties at the moment, so for a bit of sanity I thought I’d jot down the glimmer of a thought I had.

We spoke back here about the term model for a set of ground terms, XX, and a set of term constructors, Σ\Sigma, as the initial algebra for the functor F:Y→X+Σ(Y)F: Y \to X + \Sigma(Y). For example, the set of finite sequences of 1s is the term algebra for F:Y→1+YF: Y \to 1 + Y. More interesting examples involve trees.

Dually, there are coterms, which correspond to the behaviours of a system which unpacks an element into a term-constructor and collection of elements. These form the terminal coalgebra for a functor. So in the case of F:Y→1+YF: Y \to 1 + Y, coterms will be possibly infinite streams of 1s, each of which is unpacked, if not empty, into a 1 and another stream. Elements correspond to the extended natural numbers, i.e., the natural numbers with the infinite stream adjoined. In the case of trees, we find potentially infinitely deep trees, such as the trace trees of computations.

Now, the new thought. Tangles are like higher-dimensional pieces of syntax, as shown by their use, for example, in calculating with representations of quantum groups. This works through their forming the free braided monoidal category on a dualizable object. So, question: could there not be dually a system of ‘coterm’ tangles with possibly infinitely many subtangles?

One small hint that there’s something to this: a nice example of an initial algebra/terminal coalgebra pair was given by Tom here. It’s the dyadic rationals in the interval [0,1][0, 1], and the real interval [0,1][0, 1], as devised by Peter Freyd. There’s a completion process going on.

Now there’s a link from rationals to tangles in the form of Conway’s rational tangles, week 228 and week 229, where each two-stranded tangle may be assigned a rational in an isotopy-invariant way. Is there a ‘completion’? Well, Louis Kauffman and Sofia Lambropoulou tell us in On the classification of rational tangles that

each non-rational real number (algebraic or transcendental) can be associated to an infinite tangle…all the approximants of which are rational tangles. (p. 24)

There it is. Now I really must get back to my admin.

Posted at January 25, 2011 11:41 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2346



21 Comments & 0 Trackbacks

Re: Coalgebraic Tangles

I may be speaking to myself, but to continue with some more loosely connected thoughts, Kauffman and Lambropoulou’s account of rational tangles works through continued fractions. There’s a continued fraction coalgebra studied in The continuum as a final coalgebra by Pavlovic and Pratt.

Rutten treats the stream behaviour of an infinite multivariate weighted automaton as a continued fraction in sec. 17 of Elements of Stream Calculus (An Extensive Exercise in Coinduction). Does this mean there’s a tangle-shaped form of these stream behaviours?

Given that “Coalgebra is an abstract framework for the uniform study of different kinds of dynamical systems”, as Alexandra Silva claims, it may be interesting that there are connections between knots and dynamics, e.g., Ghrist’s “Chaotic” knots and “wild” dynamics, where

there must be knotted orbits of arbitrarily long length (under any fixed metric); hence, there are “asymptotically wild” knots within the flow.

And dynamically-defined wild knots are studied by Hinojosa.

Finally, nothing escapes the Café. I see John Armstrong was asking back here

How can we bring wild tangles into the categorical picture?

Coalgebraically?

Posted by: David Corfield on January 26, 2011 10:27 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

” Given that “Coalgebra is an abstract framework for the uniform study of different kinds of dynamical systems”, as Alexandra Silva claims …”

Do you know what is being meant by this? And if you do, could you possibly expand on this a bit?

Posted by: Eugene Lerman on January 26, 2011 3:21 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

This is a line you hear very often from the coalgebra people, e.g., in the paper Universal coalgebra: a theory of systems by Rutten.

For F(X)=1+XF(X) = 1 + X, coalgebras are sets of states which after a step either terminate or enter the next state.

For F(X)=A+B×XF(X) = A + B \times X, coalgebras are sets of states which after a step either terminate and spit out an element in AA, or move to a new state and emit an element in BB.

Deterministic automata correspond to F(X)=X A×BF(X) = X^A \times B.

Then you can go probabilistic, F(X)=F(X) = set of distributions on XX: coalgebras are Markov chains.

This is, of course, coalgebra in the sense of coalgebra for an endofunctor.

Posted by: David Corfield on January 26, 2011 4:15 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

David, this may well be hijacking the discussion in the direction that you may not want to go, in which case I will cease and desist.

Here is a question that has been bothering me for some time. Suppose I have an object CC in a category 𝒞\mathcal{C}. What could reasonably be called a dynamical system on CC?

A discrete time dynamical system on CC could be defined as a sub-semigroup of End(C)End(C) generated by some element f∈End(C)f\in End(C), that is, an action of natural numbers. If the category 𝒞\mathcal{C} is nice enough, the object CC may have an action of [0,∞)[0, \infty) or even of ℝ\mathbb{R}, in which case we have a continuous time dynamical system. But in hybrid dynamical systems (see this paper, for example) time is neither discrete nor continuous.

Any thoughts?

Posted by: Eugene Lerman on January 26, 2011 10:19 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

Any distraction is very welcome. In Conceptual Mathematics p. 137, Lawvere and Schanuel say that objects in the category of sets and endomaps, i.e., pairs consisting of a set and an endomap, arise frequently as dynamical systems or automata. So it sounds like you’re thinking along the same lines. Lawvere also wrote a paper – Functorial Remarks on the General Concept of Chaos – on more general systems of objects equipped with an action of a monoid.

From the coalgebraic point of view, discrete dynamical systems are just coalgebras for the identity functor.

Posted by: David Corfield on January 27, 2011 8:54 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

Thanks. I thought such a point of view cannot be new.

What about graded monoids, with the integer grading keeping track of the order of iteration? Does that show up in the work of Lawvere? anyone else?

Posted by: Eugene Lerman on January 27, 2011 12:57 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

Yes, graded monoids have shown up in the theory of automata. See Hines (2003), “A Categorical Framework for Finite Automata”[1]. Basically, he uses graded categories are to model automata that can both read and write. If I understand properly, the idea is that an automata modifies its input as it progresses, and you can use the grading to keep track of the intermediate states of the computation.

It’s a pretty idea, but I’m not sure what it’s for – it seems too intensional to model sequential computation well. Perhaps it has some applications to concurrency.

[1] http://peterhines.net/Site/DOWNLOADS_files/MSCS.pdf

Posted by: Neel Krishnaswami on February 3, 2011 9:56 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

Graded monoids such as free monoids? I haven’t seen these used anywhere, except to the extent that Lawvere looks at arrows between the action monoids, and the codomain could be the natural numbers.

I wonder if category theory should be used in dynamical systems theory more seriously. It seems to crop up naturally enough in an outline, such as here, but it ends pretty quickly. Is anyone else doing anything approaching taking categories seriously?

Posted by: David Corfield on January 27, 2011 2:04 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

Graded monoids such as free monoids?

Yes, but a bit more general than free monoids. I want the following structure: a collection of sets {M n} n∈ℕ\{M_n\}_{n\in \mathbb{N}} (or a family of objects in your favourite category with binary products) graded by natural numbers ℕ\mathbb{N} together with a family of “compositions”

(1)∘ k.l:M k×M l→M k+l \circ_{k.l}: M_k \times M_l \to M_{k+l}

satisfying an appropriate notion of associativity. I think that amounts to an algebra over the multicategory of natural numbers, no?

Free monoids, I think, would be graded by word length.

These structures come up if one takes modularity seriously, as in this paper (shameless self-promotion), and tries to do it for discrete time systems.

Posted by: Eugene Lerman on January 27, 2011 4:51 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

That paper’s going to take some lengthy concentrated study, which unfortunately I can’t afford at the moment. If you want to write a guest post on the thinking behind it and the successor papers, of course, we’d be more than happy.

Any scope for Lawvere’s notion of chaos in your work, which was also considered by Ralph Wojtowicz in Symbolic Dynamics and Unpredictability Defined by Right Adjointness?

Posted by: David Corfield on January 28, 2011 1:49 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

Any scope for Lawvere’s notion of chaos in your work, which was also considered by Ralph Wojtowicz in Symbolic Dynamics and Unpredictability Defined by Right Adjointness?

Not exactly sure what you mean by “scope for notion of chaos.” Maybe there is. We didn’t do anything very radical. We were more interested in understanding how modularity could lead to synchronicity.

Posted by: Eugene Lerman on January 29, 2011 2:03 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

I was just wondering whether any of Lawvere’s uses of adjoints, to characterise chaos or periodicity, find application in your construction.

Posted by: David Corfield on January 30, 2011 10:03 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

Since there are lots of limits in our set-up, there must be adjunctions as well, but there are not explicit. We haven’t thought about chaos.

There are no explicit periodic orbits either, and no explicit search for them. Perhaps looking for periodic orbits is an activity that’s too popular in dynamics. If you study a continuous time dynamical system, the first thing you do you look at equilibria and then what happens nearby. The next thing you do is you look for periodic orbits. If you find them, you try to figure out what happens near them. But there are interesting things that may be going on. It’s just that usually there is no systematic way to get you hands on it.

Perhaps I speak too confidently and incorrectly and someone reading this would shake his/her head and would be moved to set me straight.

In any case, in our set up, one can read off maps between dynamical systems from maps of graphs. So one gets subsystems from surjections of graphs and even retractions onto subsystems from retractions of graphs.

Posted by: Eugene Lerman on January 31, 2011 3:29 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

Right, that’s an algebra over the multicategory of natural numbers.

Another way to say the same thing is that it’s a lax monoidal functor from (ℕ,+,0)(\mathbb{N}, +, 0) (seen as a discrete monoidal category) to SetSet.

Yet another way is to see it as a one-object category enriched in the discrete monoidal category (ℕ,+,0)(\mathbb{N}, +, 0). Such an enriched category is sometimes called an ℕ\mathbb{N}-graded category (at least by me). They’ve been considered from time to time.

Yet another way is to see it as a monoid over ℕ\mathbb{N}, i.e. equipped with a monoid homomorphism to ℕ\mathbb{N}. More generally, an ℕ\mathbb{N}-graded category is a category over the one-object category ℕ\mathbb{N}.

The free category on a directed graph has a natural ℕ\mathbb{N}-grading. For if GG is a directed graph then we have the unique map G→1G \to 1, where 11 denotes the terminal graph; then applying the free category functor FF gives a functor F(G)→F(1)=ℕF(G) \to F(1) = \mathbb{N}. In particular, the free monoid on a set has a natural ℕ\mathbb{N}-grading.

Posted by: Tom Leinster on January 27, 2011 6:10 PM | Permalink | Reply to this

Re: Coalgebraic Tangles

Hi, David, Neel - a more recent view on that paper is some stuff I did on dynamical systems, from a category theory / domain theory point of view.

Machine semantics

I wasn’t entirely sure what it was for at the time either ;) but it ended up being useful in building quantum circuits:

Quantum circuit oracles for Abstract Machine computations

Not sure how relevant this is to the thread, but I’m glad someone’s taking an interest in it.

Posted by: Peter Hines on February 11, 2011 10:57 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

David wrote:

Tangles are like higher-dimensional pieces of syntax, as shown by their use, for example, in calculating with representations of quantum groups. This works through their forming the free braided monoidal category on a dualizable object. So, question: could there not be dually a system of ‘coterm’ tangles with possibly infinitely many subtangles?

Nice question!

I may be speaking to myself…

Well, we are always speaking first and foremost to ourselves. And when we do it quietly enough, it’s called ‘thinking’, and it’s generally regarded as a good thing.

But in this case you’re not speaking only to yourself. I believe you have an interesting idea. There should be a braided monoidal category with duals where the morphisms are wild tangles. If we consider ordinary ‘tame’ tangles, they’re morphisms in the free braided monoidal category with duals on one object. So maybe the wild tangles are morphisms in some sort of ‘cofree’ braided monoidal category with duals on one object. Unfortunately I don’t know what I mean by ‘cofree’ here… I’m just saying it because it resonates with your idea that wild tangles are ‘coalgebraic’.

Maybe you should try an easier example — a decategorified version. The free commutative monoid on one object is ℕ\mathbb{N}, the natural numbers. This should be the initial algebra for some functor. What’s the corresponding terminal coalgebra?

(I think I can guess, and it seems to put an interesting wrinkle into your question.)

Posted by: John Baez on January 31, 2011 9:57 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

I was just thinking how much I was missing you on the blog.

As for your easier example, that’s old hat, at least, for the functor F(X)=1+XF(X) = 1 + X. The terminal coalgebra is the extended natural numbers.

But I guess this would point us to the possibility of infinitely many strands in the tangle, rather than infinitely many caps, cups and crossings.

Posted by: David Corfield on January 31, 2011 10:47 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

David wrote:

I was just thinking how much I was missing you on the blog.

I miss talking to you, too! Sounds like you’re very busy these days. I’m just as chatty as ever. My interests have just shifted — even more than I expected — and this blog isn’t the right place to talk about what I enjoy now. My posts on ‘The Three-Fold Way’ are based on old work… but I’m dying to talk about new stuff like information geometry, Petri nets, plans for tackling environmental problems, Milankovitch cycles, stochastic resonance and so on. They’re all related, in cool ways! But they all seem hopelessly divergent from the core interests of the n-Category Café. So instead, I’m mainly hanging out on the Azimuth Forum and my other blog. If you ever want to talk, I’m right there.

Anyway: back to coalgebraic structures!

But I guess this would point us to the possibility of infinitely many strands in the tangle, rather than infinitely many caps, cups and crossings.

Right! Or infinitely many strands as well as infinitely many caps, cups and crossings. I think if we were smart, we choose which structures to add ‘freely’ and which to add ‘cofreely’.

Posted by: John Baez on February 1, 2011 6:22 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

Of course as we have discussed before, `Petri nets are monoids’ to quote the title of a well known article. (I taught Petri nets in Operational Research courses and the students liked them. From a pedagogic and `practical’ point of view they are great fun to use.) My query would be: would some of the stochastic and information based variants of Petri nets correspond to certain variants of symmetric monoidal categories as yet undefined? i.e., does the Meseguer et al work, from way back, and the links with linear logic, adapt to give insights into adaptations of the higher category theory that we know and love, to handle more dynamic and probabilistic areas. (I am thinking of other biological aspects as well as the environmental ones that fascinate John.)

All that then would feed back into the coalgebraic theme of this thread… but I am way out of my depth already.

Posted by: Tim Porter on February 3, 2011 6:46 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

Tim wrote:

My query would be: would some of the stochastic and information based variants of Petri nets correspond to certain variants of symmetric monoidal categories as yet undefined?

I’m writing a paper on this now — or at least something pretty similar. I’ll be blogging about it over on Azimuth in a while.

I don’t remember us talking here about Petri nets. Nor do I know the article “Petri nets are monoids”. I’ll have to find that!

Posted by: John Baez on February 6, 2011 10:16 AM | Permalink | Reply to this

Re: Coalgebraic Tangles

I’m nearly out the other side of the abyss of admin, and will be able to visit your blog more often.

I guess braids with infinitely many crossings would be the easiest place to start. Are there co-categories around? I never did properly get them. Is there the idea of unfolding a morphism into composable morphisms?

Posted by: David Corfield on February 1, 2011 5:22 PM | Permalink | Reply to this

Post a New Comment