Kurz, Alexander and Rosicky, Jiri - Strongly Complete Logics for Coalgebras

lmcs:1231 - Logical Methods in Computer Science, September 12, 2012, Volume 8, Issue 3
Strongly Complete Logics for Coalgebras

Authors: Kurz, Alexander and Rosicky, Jiri

Coalgebras for a functor model different types of transition systems in a uniform way. This paper focuses on a uniform account of finitary logics for set-based coalgebras. In particular, a general construction of a logic from an arbitrary set-functor is given and proven to be strongly complete under additional assumptions. We proceed in three parts. Part I argues that sifted colimit preserving functors are those functors that preserve universal algebraic structure. Our main theorem here states that a functor preserves sifted colimits if and only if it has a finitary presentation by operations and equations. Moreover, the presentation of the category of algebras for the functor is obtained compositionally from the presentations of the underlying category and of the functor. Part II investigates algebras for a functor over ind-completions and extends the theorem of J{\'o}nsson and Tarski on canonical extensions of Boolean algebras with operators to this setting. Part III shows, based on Part I, how to associate a finitary logic to any finite-sets preserving functor T. Based on Part II we prove the logic to be strongly complete under a reasonable condition on T.

Source : oai:arXiv.org:1207.2732
DOI : 10.2168/LMCS-8(3:14)2012
Volume: Volume 8, Issue 3
Published on: September 12, 2012
Submitted on: July 20, 2006
Keywords: Computer Science - Logic in Computer Science,Mathematics - Category Theory,F.3.2,F.4.1


Consultation statistics

This page has been seen 50 times.
This article's PDF has been downloaded 10 times.