A 2-Categorical Framework for the Syntax and Semantics of Many-Sorted Equational Logic

Juan Climent Vidal,

Juan Soliveres Tur

Abstrakt

For, not necessarily similar, single-sorted algebras Fujiwara defined, through the concept of family of basic mappingformulas between single-sorted signatures, a notion of morphism which generalizes the ordinary notion of homomorphism between algebras. Subsequently he also defined an equivalence relation, the relation of conjugation, on the families of basic mapping-formulas. In this article we extend the theory of Fujiwara to the, not necessarily similar, many-sorted algebras, by defining the concept of polyderivor between many-sorted signatures under which are subsumed the standard signature morphisms, the derivors of Goguen-Thatcher-Wagner, and the basic mapping-formulas of Fujiwara.

Słowa kluczowe: Many-sorted set, many-sorted algebra, Ehresmann-Grothendieck construction, Kleisli category for a monad, many-sorted term, clone, many-sorted algebraic theory, Hall algebra, B´enabou algebra, polyderivor, transformation of polyderivors
References
[1] J. B´enabou, Structures algebriques dans les categories, Cahiers de topologie et g´eometrie diff´erentielle 10 (1968), pp. 1–126. 
[2] G. Birkhoff and J. D. Lipson, Heterogeneous algebras, J. Combinatorial Theory 8 (1970), pp. 115–133. 
[3] F. Borceux and G. Janelidze, Galois theories, Cambridge University Press. Cambridge Studies in Advanced Mathematics 72. Cambridge, 2001.
[4] J. Climent and J. Soliveres, The completeness theorem for monads in categories of sorted sets, Houston Journal of Mathematics 31 (2005), pp. 103–129.
[5] J. Climent and J. Soliveres, On the completeness theorem of many-sorted equational logic and the equivalence between Hall algebras and B´enabou theories, Reports on Mathematical Logic 40 (2006), pp. 127–158.
[6] P. Cohn, Universal algebra, D. Reidel Publishing Company, Dordrecht: Holland / Boston: U.S.A. / London: England, 1981.
[7] Ch. Ehresmann, Cat´egories et structures, Dunod, Paris, 1965.
[8] T. Fujiwara, On mappings between algebraic systems, Osaka Math. J., 11 (1959), pp. 153–172.
[9] T. Fujiwara, On mappings between algebraic systems, II, Osaka Math. J. 12 (1960), pp. 253–268.
[10] K. G¨odel, Eine interpretation des intuitionistischen Aussagenkalku¨ls, Ergebnisse eines mathematischen Kolloquiums 4 (1933), pp. 39–40.
[11] J. Goguen and R. Burstall, Introducing institutions. In E. Clarke and D. Kozen, editors, Logics of programs. Proceedings of the fourth workshop held at CarnegieMellon University (Pittsburgh, Pa., June 6–8, 1983). Springer-Verlag, Berlin, 1984, pp. 221–256.
[12] J. Goguen and J. Meseguer, Completeness of many-sorted equational logic, Houston Journal of Mathematics 11 (1985), pp. 307–334.
[13] J. Goguen, J. Thatcher and E. Wagner, An initial algebra approach to the specification, correctness, and implementation of abstract data types, IBM Thomas J. Watson Research Center, Tecnical Report RC 6487, October 1976.
[14] G. Gr¨atzer, Universal algebra, 2nd ed., Springer-Verlag, New York · Heidelberg · Berlin, 1979.
[15] A. Grothendieck, Cat´egories fibr´ees et descente (Expos´e VI). In A. Grothendieck, editor, Revˆetements ´Etales et Groupe Fondamental (SGA 1), Springer-Verlag, Berlin · Heidelberg · New York, 1971, pp. 145–194.
[16] P.J. Higgins, Algebras with a scheme of operators, Mathematische Nachrichten 27 (1963), pp. 115–132.
[17] N. Jacobson, Structure of rings. Amer. Math. Soc. Colloq. Pub., vol. 37. Revised edition. American Math. Soc., Providence, R. I., 1968.
[18] H. Kleisli, Every standard construction is induced by a pair of adjoint functors, Proc. Amer. Math. Soc. 16 (1965), pp. 544–546.
[19] F. W. Lawvere, Functorial semantics of algebraic theories, Dissertation. Columbia University, 1963.
[20] M. Lazard, Lois de groupes et analyseurs, Ann. Sci. Ecole Norm. Sup. 72 (1955), pp. 299–400.
[21] S. Mac Lane, Categories for the working mathematician. 2nd ed., Springer-Verlag, New York · Berlin · Heidelberg, 1998.
[22] G. Matthiessen, Theorie der Heterogenen Algebren, Mathematik-Arbeits-Papiere, Nr. 3, Universit¨at, Bremen, 1976.
[23] E. Post. Introduction to a general theory of elementary propositions, Amer. J. Math. 43 (1921), pp. 163–185.
[24] E. Post, The two-valued iterative systems of mathematical logic. Annals of Math. Studies, no. 5., Princeton Univ. Press, Princeton, N. J., 1941.
[25] A. Tarlecki, R. Burstall and J. Goguen, Some fundamental algebraic tools for the semantics of computation: Part 3. Indexed categories, Theoretical Computer Science 91 (1991), pp. 239–264.

Czasopismo ukazuje się w sposób ciągły on-line.
Pierwotną formą czasopisma jest wersja elektroniczna.