Skip to main content
SpringerLink
Log in

Partial algebras—survey of a unifying approach towards a two-valued model theory for partial algebras

  • Published:
algebra universalis Aims and scope Submit manuscript

Abstract

In this survey, with no proofs included, we collect some material scattered through recent papers and a planned monograph, which shows that partial algebras do have a two-valued first order model theory which is simpler and nicer than one might have expected it to be. In section 1 we comment and present some basic definitions. In section 2 a correct and complete two-valued first order logic is developed. In section 3 the three main concepts of “varieties” are presented, while sections 4 and 5 contain some additional axiomatizability results and some applications, respectively. Section 6 contains some additional remarks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • [ABN 80] H. Andréka, P. Burmeister and I. Németi.Quasivarieties of partial algebras—A unifying approach towards a two-valued model theory for partial algebras. Preprint Nr. 557, TH Darmstadt, 1980; also in: Studia Sci. Math. Hungar. to appear.

  • [AN 76] H. Andréka and I. Németi.Generalization of variety and quasivariety concept to partial algebras through category theory. Math. Inst. Hung. Acad. Sci. Preprint No. 5/1976. (To appear in Dissertationes Mathematicae (Rozprawy Mat.) No. 204.)

  • [AN 77] H. Andréka and I. Németi.A general axiomatizability theorem formulated in terms of cone-injective subcategories. In: Universal Algebra (Proc. Coll. Esztergom 1977), Colloq. Math. Soc. J. Bolyai Vol. 29, North-Holland P.C., Amsterdam, 1981, pp. 13–35.

    Google Scholar 

  • [AN 78] H. Andréka and I. Németi.Łos' lemma holds in every category. Studia Scientiarum Math. Hung.13, 1978, pp. 361–376.

    MATH  Google Scholar 

  • [AN 79] H. Andréka and I. Németi.Formulas and ultraproducts in categories. Beiträge zur Algebra und Geometrie,8, 1979, pp. 133–151.

    MATH  Google Scholar 

  • [AN 79a] H. Andréka and I. Németi.Injectivity in categories to represent all first order formulas. I. Demonstratio Math.12, 1979, pp. 717–732.

    MATH  MathSciNet  Google Scholar 

  • [ASa 81] H. Andréka and I. Sain.Connections between algebraic logic and initial algebra semantics of CF languages. I. In: Mathematical Logic in Computer Science (Proc. Salgótarián 1978) Colloq. Math. Soc. J. Bolyai Vol. 26, North-Holland P.C., Amsterdam, 1981, pp. 25–83.

    Google Scholar 

  • [BaH 76] B. Banaschewski and H. Herrlich.Subcategories defined by implications. Houston J. Math.2, 1976, pp. 149–171.

    MATH  MathSciNet  Google Scholar 

  • [BtNiRu] W. Bartol, D. Niwiński and L. Rudak.Completion varieties. Preprint, Math. Inst., Univ. of Warsaw.

  • [BeKaRe 81] K. Benecke, H. Kaphengst and H. Reichel.Partial algebras defined by generators and relations. Manuscript, 1981, submitted to Algebra Universalis.

  • [BeRe 81] K. Benecke and H. Reichel.Equational partiality. Manuscript, 1981, submitted to Algebra Univeralis.

  • [BgBrTuWi 81] J. A. Bergstra, M. Broy, J. V. Tucker and M. Wirsing.On the power of algebraic specifications. Mathematical Foundations of Computer Science nu'81 (Proc. Conf. Strbské Pleso 1981), LNCS 118, Springer Verlag, Berlin, 1981, pp. 193–204.

    Google Scholar 

  • [BoMuMi] A. Bertoni, G. Mauri and P. A. Miglioli.Model theoretic aspects of abstract data specification. Manuscript, U. Milano.

  • [Bi 35] G. Birkhoff.On the structure of abstract algebras. Proc. Cambridge Philos. Soc.31, 1935, pp. 433–454.

    Article  MATH  Google Scholar 

  • [BiLi 70] G. Birkhoff and J. D. Lipson.Heterogeneous algebras. J. Combinatorial Th.8, 1970, pp. 115–133.

    MATH  MathSciNet  Google Scholar 

  • [B 70] P. Burmeister.Free partial algebras. J. reine und angewandte Math.241, 1970, pp. 75–86.

    Article  MATH  MathSciNet  Google Scholar 

  • [B 71] P. Burmeister.Primitive Klassen partieller Algebren. Habilitationsschrift, Bonn, 1971.

  • [B 73] P. Burmeister.An embedding theorem for partial algebras and the free completion of a free partial algebra within a primitive class. Algebra Universalis3, 1973, pp. 271–279.

    MATH  MathSciNet  Google Scholar 

  • [B 82] P. Burmeister.Some “logical” principles to organize properties of homomorphisms of partial algebras. In preparation.

  • [B 83] P. Burmeister.Partial Algebras—Introduction to their Theory and Applications. Part I (of a planned monograph, whose second part will be written by H. Reichel).

  • [BJPa 78] P. Burmeister, R. John and A. Pasztor.On closed morphisms in the category of partial algebras. Contributions to General Algebra, Proc. Conf. Klagenfurt, 1978 (Ed. by H. Kautschitsch, W. B. Müller., W. Nöbauer), Verlag Joh. Heyn, 1978, pp. 69–76.

  • [Bsch 67] P. Burmeister and J. Schmidt.On the completion of partial algebras. Coll. Math.17, 1967, pp. 235–245.

    MATH  MathSciNet  Google Scholar 

  • [C 65] P. M. Cohn. Universal Algebra. Harper and Row, 1965.

  • [E 67] H.-D. Ebbinghaus.Über eine Prädikatenlogik mit partiell definierten Prädikaten und Funktionen und eine Anwendung auf die Gleichungstheorie. Dissertation, Münster, 1967.

  • [E 69] H.-D. Ebbinghaus.Über eine Prädikatenlogik mit partiell definierten Prädikaten und Funktionen. Arch. math. Logik12, 1969, pp. 39–53.

    Article  MATH  MathSciNet  Google Scholar 

  • [Ed 73] G. A. Edgar.The class of topological spaces is equationally definable. Algebra Universalis3, 1973, pp. 139–146.

    MATH  MathSciNet  Google Scholar 

  • [Ev 51] T. Evans.Embeddability and the word problem. J. London Math. Soc.26, 1951, pp. 64–71.

    MATH  MathSciNet  Google Scholar 

  • [Fl 81] I. Fleischer.Equational classes of partial algebras. Manuscript, 1981.

  • [FR 80] N. Francez and M. Rodeh.A distributed abstract data type implemented by a probabilistic communication scheme. Preprint, 1980, TECHNION Comp. Sci. Dept. Haifa.

  • [GoMe 81] I. A. Goguen and J. Meseguer.Completeness of many-sorted equational logic. Manuscript, 1981, to appear in SIGPLAN Notices.

  • [GoTWa 78] J. A. Goguen, J. W. Thatcher and E. G. Wagner.An initial algebra approach to the specification, correctness, and implementation of abstract data types. IBM Research Report RC-6487, 1976; and in:Current Trends in Programming Methodology, IV: Data Structuring (R. Yeh, ed.), Prentice Hall, 1978, pp. 80–144.

  • [G 79] G. Grätzer. Universal Algebra. 2nd ed., Springer-Verlag, 1979 (1st ed.: D. van Nostrand Co., 1968).

  • [Gu 81] R. Guitart.The theory of sketches (revisited). Journées Faisceaux et Logique (19th P.S.S.L.) U. Paris-Nord & S.M.F., Paris, 23 et 24 mai, 1981.

    Google Scholar 

  • [GuL 80] R. Guitart and C. Lair.Calcul syntaxique des modéles et calcul des formules internes. Diagrammes, Vol. 4, Dec. 1980.

  • [Ha 77] R. Hartwig.Pseudogleichungen in formalen Kalkülen über partiellen Algebren. Vorträge zu Grundlagen der Informatik, Heft 27/77, TU Dresden, 1977, pp. 13–22.

  • [He 63] H. Hermes.Einführung in die mathematische Logik. Teubner Verlag, Stuttgart, 1963 (English translation: Introduction to Mathematical Logic. Unitext, Springer-Verlag, 1973).

    MATH  Google Scholar 

  • [H 72] H. Herrlich.Perfect subcategories and factorizations. Coll. Math. Soc. János Bolyai 8. Topics in Topology, Keszthely (Hungary), 1972, pp. 387–403.

    MathSciNet  Google Scholar 

  • [HS 73] H. Herrlich and G. E. Strecker.Category Theory—An Introduction. Allyn and Bacon, 1973 (2nd ed.: Heldermann-Verlag).

  • [Hö 73] H. Höft.Weak and strong equations in partial algebras. Algebra Universalis3, 1973, pp. 203–215.

    MATH  MathSciNet  Google Scholar 

  • [Hoe 72] H.-J. Hoehnke.Superposition partieller Funktionen. Studien zur Algebra und ihre Anwendungen (Ed: Hoehnke), Akademie Verlag Berlin, 1972, pp. 7–26.

    Google Scholar 

  • [Hoe 76] H.-J. Hoehnke.On partial algebras. Preprint Akad. d. Wiss. d. DDR, Berlin, 1976. Published in: Universal Algebra (Proc. Coll. Esztergom 1977) Colloq. Math. Soc. J. Bolyai, Vol. 29, North-Holland P.C., Amsterdam, 1981, pp. 373–412.

  • [J 75] R. John.Gültigkeitsbegriffe für Gleichungen in partiellen Algebren. Dissertation, Darmstadt, 1975.

  • [J 75a] R. John.A note on implicational subcategories. Contributions to Universal Algebra (Proc. Coll. Szeged, 1975); Eds.: B. Csákány, J. Schmidt; Colloq. Math. Soc. J. Bolyai, Vol. 17, North-Holland P.C., Amsterdam, 1977, pp.213–222.

    Google Scholar 

  • [J 78] R. John.Gültigkeitsbegriffe für Gleichungen in partiellen Algebren. Math. Zeitschrift 159, 1978, pp. 25–35.

    Article  MATH  Google Scholar 

  • [Ka 81] H. Kaphengst.What is computable for abstract data types? Fundamentals of Computation Theory (Proc. Conf. Szeged, 1981), LNCS 117, Springer-Verlag, Berlin, 1981, pp. 173–181.

    Google Scholar 

  • [KaRe 77] H. Kaphengst and H. Reichel.Initial algebra semantics for non-context-free languages. Fundamentals of Comp. Sci. LNCS 56, Springer-Verlag, 1977, pp. 120–127.

    MATH  MathSciNet  Google Scholar 

  • [K 64] C. R. Karp.Languages with expressions of infinite length. North-Holland P. Co., 1964.

  • [Ke 70] R. Kerkhoff.Gleichungsdefinierbare Klassen partieller Algebren. Math. Annalen185, 1970, pp. 112–133.

    Article  MATH  MathSciNet  Google Scholar 

  • [Kl 52] S. C. Kleene.Introduction to Metamathematics. North-Holland P. Co., 1952 (5th reprint 1967).

  • [KoSp 68] S. Kochen and E. P. Specker.The problem of hidden variables in Quantum Mechanics. J. Math. Mech.17, 1968, pp. 58–87.

    MathSciNet  Google Scholar 

  • [Ku 77] I. Kupka.Partial algebras for representing semantics of information processing. Habilitationsschrift, Hamburg, 1977 (und Preprint am Fachbereich Informatik, Hamburg, 1980).

  • [LePa 80] D. Lehmann and A. Pasztor.On a conjecture of Meseguer. Preprint Techn. Dept. of Comp. Sci., Haifa, 1980; also under the title “Epis need not be dense” in Theoretical Computer Science17, 1982, pp. 151–162.

  • [Lj 76] E. S. Ljapin.Abstract characterization of partial groupoids of words with synonyms. Algebraic Theory of Semigroups (Proc. Coll. Szeged, 1976); Colloq. Math. Soc. J. Bolyai, Vol. 20, 1979, pp. 341–356.

    MATH  MathSciNet  Google Scholar 

  • [Mal 73] A. I. Mal'cev.Algebraic Systems. Springer-Verlag, 1973.

  • [Ma 71] W. Markwald.Prädikatenlogik mit partiell definierten Funktionen. Arch. math. Logik14, 1971, pp. 10–23.

    Article  MATH  MathSciNet  Google Scholar 

  • [Mo 76] J. D. Monk.Mathematical Logic. Springer-Verlag, 1976.

  • [Ms 51] A. Mostowski.On the rules of proof in the pure functional calculus of the first order. J. Symbolic Logic16, 1951, pp. 107–111.

    Article  MATH  MathSciNet  Google Scholar 

  • [N 78] I. Németi.From hereditary classes to varieties in abstract model theory and partial algebras. Beiträge zur Algebra und Geometrie7, 1978, pp. 69–78.

    MATH  Google Scholar 

  • [N 80] I. Németi.It is sometimes better to use partial algebras rather than total algebras in Computer Science. In preparation.

  • [N 81] I. Németi.Connections between cylindric algebras and initial algebra semantics of CF languages. II. In: Mathematical Logic in Computer Science (Proc. Sangótarján 1978) Colloq. Math. Soc. J. Bolyai, Vol. 26, North-Holland P.C., Amsterdam, 1981, pp. 561–605.

    Google Scholar 

  • [NSa 77] I. Németi and I. Sain.Cone-implicational subcategories and some Birkhoff-type theorems. In: Universal Algebra (Proc. Coll. Esztergom 1977), Colloq. Math. Soc. J. Bolyai, Vol. 29, North-Holland P.C., Amsterdam, 1981, pp. 535–578.

    Google Scholar 

  • [O 81] A. Obtułowicz.Theories classifying partial algebras. Submitted to: Proceedings Conf. on Category Theory, Gummersbach, 1981.

  • [Pa 79] A. Pasztor.Faktorisierungssysteme in der Kategorie der partiellen Algebren—Kennzeichnung von (Homo-)Morphismen. Dissertation, Darmstadt, 1979 (Hochschulverlag, Freiburg, 1979).

  • [Po 73] V. S. Poythress.Partial morphisms on partial algebras. Algebra Universalis3, 1973, pp. 182–202.

    Article  MATH  MathSciNet  Google Scholar 

  • [Re 78a] H. Reichel.Limit-colimit doctrines in Computer Science. Algebra and its Applications, Banach Center Semester, Warsaw, 1978. To appear in Banach Center Publications.

    Google Scholar 

  • [Re 78b] H. Reichel.Algebraic specifications of abstract data types. Algebra and its Applications. Banach Center Semester, Warsaw, 1978. To appear in Banach Center Publications.

    Google Scholar 

  • [Re 79] H. Reichel.Theorie der Äquoide. Dissertation B, Humboldt-Universität, Berlin, 1979.

    Google Scholar 

  • [Re 81] H. Reichel.Homomorphism theorem for equationally partial heterogeneous algebras. Manuscript, submitted to Algebra Universalis.

  • [Ru] L. Rudak.Completeness theorem for partial algebras with weak satisfaction. Manuscript, Math. Inst. U. Warsaw.

  • [Sa 77] I. Sain.On classes of algebraic systems closed with respect to quotients. Preprint Math. Inst. Hung. Acad. Sci. 1977; also in: Algebra and its applications, (Banach Center Semester Warsaw 1978), Banach Center Publ. Vol. 9, to appear.

  • [Sche 76] B. Schepull.Über Quasivarietäten von partiellen Algebren. Dissertation, Akad. d. Wiss. d. DDR, Berlin, 1976.

    Google Scholar 

  • [Sch 66] J. Schmidt.A general existence theorem on partial algebras and its special cases. Coll. Math.14, 1966, pp. 73–87.

    MATH  Google Scholar 

  • [Sch 70] J. Schmidt.A homomorphism theorem for partial algebras. Coll. Math.21, 1970, pp. 5–21.

    MATH  Google Scholar 

  • [Sr 77] P. Schreiber.Grundlagen der Mathematik. VEB Deutscher Verlag der Wissenschaften, Berlin 1977.

    MATH  Google Scholar 

  • [Sc 77] D. Scott.Identity and existence in intuitionistic logic. Durham Proceedings, 1977. Applications of Sheaves (ed. M. P. Fourman); LNM 753, Springer-Verlag, 1979, pp. 660–696.

  • [Sł 64] J. Słomiński.A theory of extensions of quasi-algebras to algebras. Rozprawy Matematyczne40, 1964.

  • [Sł 68] J. Słomiński.Peano-algebras and quasi-algebras. Dissertationes Mathematicae (Rozprawy Mat.)62, 1968.

  • [Th 66] H. Thiele.Wissenschaftstheoretische Untersuchungen in algorithmischen Sprachen I (Theorie der Graphschemata-Kalküle). VEB Deutscher Verlag der Wissenschaften, Berlin 1966.

    MATH  Google Scholar 

  • [Ti 81] J. Tiuryn.A survey of the logic of effective definitions. Preprint MIT/LCS/TR-246, MIT Laboratory for Computer Science, Cambridge, Massachusetts.

  • [W 78] H. Werner.Einführung in die allgemeine Algebra. B.I.-Hochschultaschenbücher, Band 120, 1978.

  • [Wo 72] B. Wojdyło,Categories of quasi-algebras. N. Copernicus University, Toruń, Preprint No. 2, 1972.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Technische Hochschule Darmstadt, Darmstadt, Federal Republic of Germany

    Peter Burmeister

Authors
  1. Peter Burmeister
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Burmeister, P. Partial algebras—survey of a unifying approach towards a two-valued model theory for partial algebras. Algebra Universalis 15, 306–358 (1982). https://doi.org/10.1007/BF02483730

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02483730

Keywords

Search

Navigation