TY - GEN
T1 - Coalgebraic predicate logic
AU - Litak, Tadeusz
AU - Pattinson, Dirk
AU - Sano, Katsuhiko
AU - Schröder, Lutz
PY - 2012
Y1 - 2012
N2 - We propose a generalization of first-order logic originating in a neglected work by C.C. Chang: a natural and generic correspondence language for any types of structures which can be recast as Set-coalgebras. We discuss axiomatization and completeness results for two natural classes of such logics. Moreover, we show that an entirely general completeness result is not possible. We study the expressive power of our language, contrasting it with both coalgebraic modal logic and existing first-order proposals for special classes of Set-coalgebras (apart for relational structures, also neighbourhood frames and topological spaces). The semantic characterization of expressivity is based on the fact that our language inherits a coalgebraic variant of the Van Benthem-Rosen Theorem. Basic model-theoretic constructions and results, in particular ultraproducts, obtain for the two classes which allow for completeness-and in some cases beyond that.
AB - We propose a generalization of first-order logic originating in a neglected work by C.C. Chang: a natural and generic correspondence language for any types of structures which can be recast as Set-coalgebras. We discuss axiomatization and completeness results for two natural classes of such logics. Moreover, we show that an entirely general completeness result is not possible. We study the expressive power of our language, contrasting it with both coalgebraic modal logic and existing first-order proposals for special classes of Set-coalgebras (apart for relational structures, also neighbourhood frames and topological spaces). The semantic characterization of expressivity is based on the fact that our language inherits a coalgebraic variant of the Van Benthem-Rosen Theorem. Basic model-theoretic constructions and results, in particular ultraproducts, obtain for the two classes which allow for completeness-and in some cases beyond that.
UR - http://www.scopus.com/inward/record.url?scp=84875104981&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31585-5_29
DO - 10.1007/978-3-642-31585-5_29
M3 - Conference contribution
SN - 9783642315848
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 299
EP - 311
BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
PB - Springer Verlag
T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Y2 - 9 July 2012 through 13 July 2012
ER -