×

Presenting functors on many-sorted varieties and applications. (English) Zbl 1252.18009

Summary: This paper studies several applications of the notion of a presentation of a functor by operations and equations. We show that the technically straightforward generalisation of this notion from the one-sorted to the many-sorted case has several interesting consequences. First, it can be applied to give equational logic for the binding algebras modelling abstract syntax. Second, it provides a categorical approach to algebraic semantics of first-order logic. Third, this notion links the uniform treatment of logics for coalgebras of an arbitrary type \(T\) with concrete syntax and proof systems. Analysing the many-sorted case is essential for modular completeness proofs of coalgebraic logics.

MSC:

18C05 Equational categories
03G30 Categorical logic, topoi
08C05 Categories of algebras
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramsky, S., Domain theory in logical form, Ann. Pure Appl. Logic, 51, 1-77 (1991) · Zbl 0737.03006
[2] Adámek, J.; Koubek, V., On the greatest fixed point of a set functor, Theor. Comput. Sci., 150, 57-75 (1995) · Zbl 0874.18001
[3] Adámek, J.; Rosický, J., Locally Presentable and Accessible Categories (1994), CUP · Zbl 0795.18007
[5] Adámek, J.; Trnková, V., Automata and Algebras in Categories (1990), Kluwer · Zbl 0698.18001
[6] Aizenštat, A. Y., Defining relations of finite symmetric semigroups, Math. Sb. N. S., 45, 261-280 (1958)
[7] Blackburn, P.; de Rijke, M.; Venema, Y., Modal Logic (2001), CUP · Zbl 0988.03006
[11] Cîrstea, C.; Pattinson, D., Modular construction of complete coalgebraic logics, Theor. Comput. Sci., 388, 1-3, 83-108 (2007) · Zbl 1126.03020
[16] Gabbay, M. J.; Mathijssen, A., One-and-a-halfth-order logic, J. Logic Comput., 18, 4, 521-562 (2008) · Zbl 1158.03006
[17] Halmos, P., Algebraic logic I. Monadic Boolean algebras, Comp. Math., 12, 217-249 (1955)
[18] Halmos, P., Algebraic Logic (1962), Chelsea Publishing · Zbl 0101.01101
[19] Heifetz, A.; Mongin, P., Probabilistic logic for type spaces, Games Econom. Behav., 35, 31-53 (2001) · Zbl 0978.03017
[20] Henkin, L.; Monk, J. D.; Tarski, A., Cylindric Algebra (1971), North Holland Publishing Company · Zbl 0214.01302
[22] Jacobs, B., Many-sorted coalgebraic modal logic: a model-theoretic study, Theor. Inform. Appl., 35, 31-59 (2001) · Zbl 0984.03019
[26] Kurz, A., Coalgebras and their logics, SIGACT News, 37, 57-77 (2006)
[27] Kurz, A.; Pattinson, D., Coalgebraic modal logic of finite rank, Math. Struct. Comput. Sci., 15, 453-473 (2005) · Zbl 1135.18300
[28] Kurz, A.; Petrisan, D., On universal algebra over nominal sets, Math. Struct. Comput. Sci., 20, 285-318 (2010) · Zbl 1193.08004
[32] Ouellet, R., Inclusive first-order logic, Stud. Logic, 40, 13-28 (1981) · Zbl 0468.03043
[33] Ouellet, R., A categorical approach to polyadic algebras, Stud. Logic, 41, 317-327 (1982) · Zbl 0556.03047
[34] Pattinson, D., Coalgebraic modal logic: soundness, completeness and decidability of local consequence, Theor. Comput. Sci., 309, 177-193 (2003) · Zbl 1052.03009
[35] Pigozzi, D.; Salibra, A., The abstract variable-binding calculus, Stud. Logic, 55, 1, 129-179 (1995) · Zbl 0836.03038
[36] Robinson, D., A Course in the Theory of Groups (1996), Springer
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.