Download PDF - Compactness and Löwenheim-Skolem properties in categories of pre-institutionsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Compactness and Löwenheim-Skolem properties in categories of pre-institutions

Authors 1, 2

Affiliations

  1. University of Pisa, Dip. Informatica, Corso Italia 40, I-56125 Pisa, Italy
  2. University of Twente, Fac., Informatica, P. O. Box 217, NL-7500AE Enschede, The Netherlands

Abstract

The abstract model-theoretic concepts of compactness and Löwenheim-Skolem properties are investigated in the "softer" framework of pre-institutions [18]. Two compactness results are presented in this paper: a more informative reformulation of the compactness theorem for pre-institution transformations, and a theorem on natural equivalences with an abstract form of the first-order pre-institution. These results rely on notions of compact transformation, which are introduced as arrow-oriented generalizations of the classical, object-oriented notions of compactness. Furthermore, a notion of cardinal pre-institution is introduced, and a Löwenheim-Skolem preservation theorem for cardinal pre-institutions is presented.

Bibliography

  1. H. Andréka, I. Németi and I. Sain, Abstract model theoretic approach to algebraic logic, manuscript, Mathematical Institute, Budapest, 1984.
  2. E. Astesiano and M. Cerioli, Commuting between institutions via simulation, Univ. of Genova, Formal Methods Group, Technical Report no. 2, 1990.
  3. G. Bernot and M. Bidoit, Proving the correctness of algebraically specified software: Modularity and Observability issues, in: M. Nivat, C. M. I. Rattray, T. Rus and G. Scollo (eds.), AMAST '91, Algebraic Methodology and Software Technology, Workshops in Computing, Springer, London 1992, 216-239.
  4. C. C. Chang and H. J. Keisler, Model Theory, third ed., North-Holland, Amsterdam 1990.
  5. H.-D. Ebbinghaus, Extended logics: the general framework, in: J. Barwise and S. Feferman (eds.), Model-Theoretic Logics, Springer, Berlin 1985, 25-76.
  6. H.-D. Ebbinghaus, J. Flum and W. Thomas, Mathematical Logic, Springer, New York 1984.
  7. H. Ehrig, M. Baldamus, F. Cornelius and F. Orejas, Theory of algebraic module specification including behavioural semantics and constraints, in: M. Nivat, C. M. I. Rattray, T. Rus and G. Scollo (eds.), AMAST '91, Algebraic Methodology and Software Technology, Workshops in Computing, Springer, London 1992, 145-172.
  8. A. J. M. van Gasteren, On the Shape of Mathematical Arguments, Lecture Notes in Comput. Sci. 445, Springer, Berlin 1990.
  9. J. A. Goguen and R. Burstall, Introducing institutions, in: E. Clarke and D. Kozen (eds.), Logics of Programs, Lecture Notes in Comput. Sci. 164, Springer, Berlin 1984, 221-256.
  10. S. MacLane, Categories for the Working Mathematician, Graduate Texts in Math. 5, Springer, New York 1971.
  11. J.-A. Makowski, Compactness, embeddings and definability, in: J. Barwise and S. Feferman (eds.), Model-Theoretic Logics, Springer, Berlin 1985, 645-716.
  12. V. Manca and A. Salibra, On the power of equational logic: applications and extensions, in: H. Andréka, J. D. Monk and I. Németi (eds.), Algebraic Logic, Colloq. Math. Soc. János Bolyai 54, North-Holland, Amsterdam 1991, 393-412.
  13. V. Manca, A. Salibra and G. Scollo, Equational type logic, Theoret. Comput. Sci. 77 (1990), 131-159.
  14. V. Manca, A. Salibra and G. Scollo, On the expressiveness of equational type logic, in: C. M. I. Rattray and R. G. Clark (eds.), The Unified Computation Laboratory: Modelling, Specifications and Tools, Oxford Univ. Press, Oxford 1992, 85-100.
  15. J. Meseguer, General logics, in: H.-D. Ebbinghaus et al. (eds.), Logic Colloquium '87, North-Holland, Amsterdam 1989, 275-329.
  16. M. P. Nivela and F. Orejas, Initial behaviour semantics for algebraic specifications, in: D. T. Sannella and A. Tarlecki (eds.), Recent Trends in Data Type Specification, Lecture Notes in Comput. Sci. 332, Springer, Berlin 1988, 184-207.
  17. F. Orejas, M. P. Nivela and H. Ehrig, Semantical constructions for categories of behavioural specifications, in: H. Ehrig, H. Herrlich, H.-J. Kreowski and G. Preuß (eds.), Categorical Methods in Computer Science - with Aspects from Topology, Lecture Notes in Comput. Sci. 393, Springer, Berlin 1989, 220-245.
  18. A. Salibra and G. Scollo, A soft stairway to institutions, in: M. Bidoit and C. Choppy (eds.), Recent Trends in Data Type Specification, Lecture Notes in Comput. Sci. 655, Springer, Berlin 1993, 310-329.
  19. D. T. Sannella and A. Tarlecki, Specifications in an arbitrary institution, Inform. and Comput. 76 (1988), 165-210.
Banach Center Publications
1993/28/1
Export to PBN, Opens in new tab
Pages:
67-94
Main language of publication
English
Published
1993
Exact and natural sciences