From Set-theoretic Coinduction to Coalgebraic Coinduction: some results, some problems

✍ Scribed by Marina Lenisa

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 241 KB
• Volume: 19
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(05)80265-8

✦ Synopsis

We investigate the relation between the set-theoretical description of coinduction based on Tarski Fixpoint Theorem, and the categorical description of coinduction based on coalgebras. In particular, we introduce set-theoretic generalizations of the coinduction proof principle, in the spirit of Milner's bisimulation "up-to", and we discuss categorical counterparts for these. Moreover, we investigate the connection between these and the equivalences induced by T -coiterative functions. These are morphisms into final coalgebras, satisfying the T -coiteration scheme, which is a generalization of the corecursion scheme. We show how to describe coalgebraic Fbisimulations as set-theoretical ones. A list of examples of set-theoretic coinductions which appear not to be easily amenable to coalgebraic terms are discussed.