Coalgebras over Lawvere Metric Spaces

Talk at the Logic Seminar of the University of Ottawa organised by Richard Blute, Feb 2022.

Abstract: Coalgebras are a model of dynamic systems that is particularly relevant if generalisations of bisimulation (observational/behavioural equivalence/preorder/metric) are of importance. We survey coalgebras as models of dynamical systems, Lawvere metric spaces, coalgebras over Lawvere metric spaces, hint their motivations in applications to computer science and introduce some of the open mathematical questions in the area.

---

(… draft …)

---

Table of Contents

(the writeup contains much more material than the 50min presentation)

• background:
  • coalgebras over sets
  • coalgebraic logic over sets
  • generalizing to ordered sets
• generalizing from orders to quantales
• extending functors to quantale enriched categories
• the logic of quantale enriched categories

References

Bill Lawvere: Metric Spaces, Generalized Logic, and Closed Categories, 1973.
The collected works of F. W. Lawvere.

G.M. Kelly: Basic Concepts of Enriched Category Theory, Cambridge University Press, Lecture Notes in Mathematics 64, 1982. Also in TAC Reprints 10, 2005.

Peter Aczel: Non-well-founded sets. CSLI 1988.

Jan J. M. M. Rutten: Relators and Metric Bisimulations. CMCS 1998.

Peter Aczel, Nax Paul Mendler: A Final Coalgebra Theorem. Category Theory and Computer Science 1989

James Worrell: Coinduction for recursive data types: partial orders, metric spaces and Omega-categories. CMCS 2000

Jipsen and Galatos: RESIDUATED LATTICES OF SIZE UP TO 6, 2017

Adriana Balan, Alexander Kurz, Jiri Velebil: Extending set functors to generalised metric spaces, Logical Methods in Computer Science 15 (2019).

…

Topics that didn't make it into the talk …

Jan Rutten's theory of universal coalgebra that develops the theory of coalgebras parametrically in the functor

$T:Set\to Set$

Moss's coalgebraic logic and Pattinson's predicate liftings (dblp for coalgebraic logic)

Examples of coalgebras for functors

$T:Set\to Set$ other than the powerset functor such as streams, automata, languages, Markov chains, certain kind of games, etc

Examples of base categories

$\mathcal{X}$ other than

$Set$ or

$Pre$ or or

$Pos$ or

$\mathrm{\Omega }$-cat such as various topological spaces, nominal sets, vector spaces, etc

Applications of coalgebras to the semantics of programming languages such as operational semantics of process algebras via bialgebras, infinitary lambda-calculus, …

Applications of coalgebras over Lawvere metric spaces to semantics of programming languages … Breugel and Worrell etal … Dal Lago and Gavazzo etal

…

(the coalgebra community has been prolific, there is so much more out there that I regret now that I started to make a list … apologies to everybody else)