Institution Morphisms

Institutions formalize the intuitive notion of logical system, including both syntax and semantics. A surprising number of different notions of morphisim have been suggested for forming categories with institutions as objects, and a surprising variet... Read more

Institutions formalize the intuitive notion of logical system, including both syntax and semantics. A surprising number of different notions of morphisim have been suggested for forming categories with institutions as objects, and a surprising variety of names have been proposed for them. One goal of this paper is to suggest a terminology that is both uniform and informative to replace the current rather chaotic nomenclature. Another goal is to investigate the properties and interrelations of these notions. Following brief expositions of indexed categories, twisted relations, and Kan extensions, we demonstrate and then exploit the duality between institution morphisms in the original sense of Goguen and Burstall, and the 'plain maps' of Meseguer, obtaining simple uniform proofs of completeness and cocompleteness for both resulting categories; because of this duality, we prefer the name 'comorphism' over 'plain map.' We next consider 'theoroidal' morphisms and comorphisims, which generalize signatures to theories, finding that the 'maps' of Meseguer are theoroidal comorphisms, while theoroidal morphisms are a new concept. We then introduce 'forward' and 'semi-natural' morphisms, and appendices discuss institutions for hidden algebra, universal algebra, partial equational logic, and a variant of order sorted algebra supporting partiality. Less