Title: Operations and Equation for Coalgebras

(joint work with J. Rosicky, appeared in Mathematical Structures in
Computer Science 15:149-166, 2005)

Abstract:

1.) Usually, coalgebras are given wrt a functor. We show that coalgebras
can also be given by operations and equations. This relies on work of
Linton from 1969 who showed how to specify algebras over an abribrary
base category and, for example, proved that a  category is monadic (over
some base category) if and only if it has a presentation by operations
and equations and has free algebras (thus generalising a theorem
well-known for algebras over Set). Since coalgebras over Set are (dual
to) algebras over Set^op, Lintons approach gives a notion of operations
and equations for coalgebras. We give some examples.

2.) Given an arbitrary functor U:A-->Set, we say that two elements a,a'
of two objects in A are *bisimilar* if they can be connected by
morphisms in A. We show that coalgebraic operations correspond to
predicate transformers that respect bisimulation and that coalgebraic
equations correspond to modal predicates.

3.) Given a functor U:A-->Set, an (n,m)-ary *implicit* (coalgebraic)
operation is a natural transformation Set(U-,n)-->Set(U-,m). We show
that classes of coalgebras closed under subcoalgebras, homomorphic
images and coproducts are precisely the classes definable by equations
in implicit operations. This theorem does not require the existence of
cofree coalgebras and therefore generalises previously known
Birkhoff-style theorems for coalgebras. It is the analogue for
coalgebras of Reiterman's famous theorem in universal algebra.