Coalgebraic predicate logic

Tadeusz Litak*, Dirk Pattinson, Katsuhiko Sano, Lutz Schröder

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
PublisherSpringer Verlag
Number of pages13
EditionPART 2
ISBN (Print)9783642315848
Publication statusPublished - 2012
Externally publishedYes
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: 9 Jul 201213 Jul 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume7392 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/TerritoryUnited Kingdom


Dive into the research topics of 'Coalgebraic predicate logic'. Together they form a unique fingerprint.

Cite this