Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-28T15:52:13.611Z Has data issue: false hasContentIssue false
  • English
  • Français

The Härtig quantifier: a survey

Published online by Cambridge University Press:  12 March 2014

Heinrich Herre ,
Michał Krynicki ,
Alexandr Pinus  and
Jouko Väänänen
Heinrich Herre
Affiliation:
Sektion Informatik, Universität Leipzig, O-7010 Leipzig, Germany
Michał Krynicki
Affiliation:
Institute of Mathematics, University of Warsaw, 00-901 Warsaw, Poland
Alexandr Pinus
Affiliation:
Novosibirsk Electrotechnical Institute, Novosibirsk, USSR
Jouko Väänänen
Affiliation:
Department of Mathematics, University of Helsinki, 00100 Helsinki, Finland
Get access Rights & Permissions [Opens in a new window]

Abstract

A fundamental notion in a large part of mathematics is the notion of equicardinality. The language with Härtig quantifier is, roughly speaking, a first-order language in which the notion of equicardinality is expressible. Thus this language, denoted by LI, is in some sense very natural and has in consequence special interest. Properties of LI are studied in many papers. In [BF, Chapter VI] there is a short survey of some known results about LI. We feel that a more extensive exposition of these results is needed.

The aim of this paper is to give an overview of the present knowledge about the language LI and list a selection of open problems concerning it.

After the Introduction (§1), in §§2 and 3 we give the fundamental results about LI. In §4 the known model-theoretic properties are discussed. The next section is devoted to properties of mathematical theories in LI. In §6 the spectra of sentences of LI are discussed, and §7 is devoted to properties of LI which depend on set-theoretic assumptions. The paper finishes with a list of open problem and an extensive bibliography. The bibliography contains not only papers we refer to but also all papers known to us containing results about the language with Härtig quantifier.

Contents. §1. Introduction. §2. Preliminaries. §3. Basic results. §4. Model-theoretic properties of LI. §5. Decidability of theories with I. §6. Spectra of LI-sentences. §7. Independence results. §8. What is not yet known about LI. Bibliography.

Type
Survey/expository paper
Information
The Journal of Symbolic Logic , Volume 56 , Issue 4 , December 1991 , pp. 1153 - 1183
Copyright
Copyright © Association for Symbolic Logic 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[Ap]Apelt, H., Axiomatische Untersuchungen über einige mit der Presburgerschen Arithmetik verwandte Systeme, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 131–168.CrossRefGoogle Scholar
[Bal]Barwise, J., Axioms for abstract model theory, Annals of Mathematical Logic, vol. 7 (1974), pp. 221–265.CrossRefGoogle Scholar
[Ba2]Barwise, J., Admissible sets and structures, Springer-Verlag, Berlin, 1975.CrossRefGoogle Scholar
[BF]Barwise, J. and Feferman, S. (editors), Model-theoretic logics, Springer-Verlag, Berlin, 1985.Google Scholar
[Bu]Baudisch, A., Theorien von Klassen abelscher Gruppen mit verallgemeinerten Quantoren, Habilitationsschrift, Humboldt Universität, Berlin, 1977.Google Scholar
[Bul]Baudisch, A., Theorien abelscher Gruppen mit einem einstelligen Prädikat, Fundamenta Mathematical vol. 83 (1974), pp. 121–127.CrossRefGoogle Scholar
[Bu2]Baudisch, A., The theory of abelian groups with the quantifier (≤ x), Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 23 (1977), pp. 447–462.CrossRefGoogle Scholar
[Bu3]Baudisch, A., The theory of abelian p-groups with the quantifier I is decidable, Fundamenta Mathematicae, vol. 108 (1980), pp. 183–197.CrossRefGoogle Scholar
[BSTW]Baudisch, A., Seese, D., Tuschik, P., and Weese, M., Decidability and generalized quantifiers, Akademie-Verlag, Berlin, 1980.Google Scholar
[BS]Bell, J. and Slomson, A., Models and ultraproducts, North-Holland, Amsterdam, 1969.Google Scholar
[Ca]Caicedo, X., Back-and-forth systems for arbitrary quantifiers, Mathematical logic in Latin America (Arruda, A.et al., editors), North-Holland, Amsterdam, 1980, pp. 83–102.Google Scholar
[Ch]Chlebus, B., Decidability and definability results concerning well-orderings and some extensions of first-order logic, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 26 (1980) pp. 529–536.CrossRefGoogle Scholar
[Co 1]Cowles, J., Field theories in the logic with the Härtig quantifier, Abstracts of Papers Presented to the American Mathematical Society, vol. 1 (1980), p. 175. (Abstract)Google Scholar
[Co2]Cowles, J., The Henkin quantifier and real closed fields, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 27 (1981), pp. 549–555.CrossRefGoogle Scholar
[Di]Dickmann, M., Large infinitary languages: model theory, North-Holland, Amsterdam, 1975.Google Scholar
[DJ]Devlin, K. and Jensen, R., Marginalia to a theorem of Silver, Lecture Notes in Mathematics, vol. 499, Springer-Verlag, Berlin, 1975, pp. 115–142.Google Scholar
[ELTT]Ershov, Y., Lavrov, I., Taǐmanov, A., and Taǐtslin, M., Elementary Theories, Russian Mathematical Surveys, vol. 20 (1965), no. 4, pp. 35–105.Google Scholar
[Fi]Fischer, U., Hanf- und Löwenheimzahl der Härtig Logik, Diplomarbeit, Universität Freiburg, Freiburg, 04 1988.Google Scholar
[Fe]Feferman, S., Two notes on abstract model theory. I: Properties invariant on the range of definable relations between structures, Fundamenta Mathematicae, vol. 82 (1974), pp. 153–165.CrossRefGoogle Scholar
[Fr]Friedman, H., Beth's theorem in cardinality logics, Israel Journal of Mathematics, vol. 14 (1973), pp. 205–212.CrossRefGoogle Scholar
[Fu]Fuhrken, G., A remark on the Härtig quantifier, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 18 (1972), pp. 227–228.CrossRefGoogle Scholar
[GH]Gostanian, R. and Hrbáček, K., On the failure of the weak Beth property, Proceedings of the American Mathematical Society, vol. 58 (1976), pp. 245–249.CrossRefGoogle Scholar
[Hä]Härtig, K., Über einen Quantifikator mit zwei Wirkungsbereichen, Colloquium on the foundations of mathematics, mathematical machines and their applications (Kalmár, L., editor), Akadémiai Kiadó, Budapest, 1962, pp. 31–36.Google Scholar
[Ha1]Hauschild, K., Generalized Härtig quantifiers, Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, vol. 28 (1980), pp. 523–528.Google Scholar
[Ha2]Hauschild, K., Zum Vergleich von Härtigquantor und Rescherquantor, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 27 (1981), pp. 255–264.CrossRefGoogle Scholar
[HR1]Hauschild, K. and Rautenberg, W., Universelle Interpretierbarkeit in Verbänden, Wissenschaftliche Zeitschrift der Humboldt-Universität zu Berlin, vol. 19 (1970), pp. 575–577.Google Scholar
[HR2]Hauschild, K., Interpretierbarkeit und Entscheidbarkeit in der Graphentheorie, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 17 (1971), pp. 47–55.Google Scholar
[HW]Hauschild, K. and Wolter, H., Über die Kategorisierbarkeit gewisser Körper in nichtelementaren Logiken, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 15 (1969), pp. 157–162.CrossRefGoogle Scholar
[He1]Herre, H., Entscheidungsprobleme für Theorien in Logiken mit verallgemeinerten Quantoren, Habilitationsschrift, Humboldt-Universität, Berlin, 1975.Google Scholar
[He2]Herre, H., Decidability of theories in logics with additional monadic quantifiers, Proceedings of the symposiums on mathematical logic in Oulu '74 and Helsinki '75 (Miettinen, S. and Väänänen, J., editors), Reports from the Department of Philosophy, University of Helsinki, vol. 2, 1977, pp. 77–80.Google Scholar
[He3]Herre, H., Miscellaneous results and problems in extended model theory, Workshop on extended model theory, Berlin, 1980, Report R-Math-03/81, Institut für Mathematik, Akademie der Wissenschaften der DDR, Berlin, 1981, pp. 20–65.Google Scholar
[HP]Herre, H. and Pinus, A., Zum Entscheidungsproblem für Theorien in Logiken mit monadischen verallgemeinerten Quantoren, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 24 (1978), pp. 375–384.CrossRefGoogle Scholar
[Is1]Issel, W., Semantische Untersuchungen über Quantoren. I, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 15 (1969), pp. 353–358.CrossRefGoogle Scholar
[Is2]Issel, W., Semantische Untersuchungen über Quantoren. II, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 16 (1970), pp. 281–296.CrossRefGoogle Scholar
[Is3]Issel, W., Semantische Untersuchungen über Quantoren. III, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 16 (1970), pp. 421–438.CrossRefGoogle Scholar
[Je]Jech, T., Set theory, Academic Press, New York, 1978.Google Scholar
[Ko]Kotlarski, H., On the existence of well-ordered models, Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 22 (1974), pp. 459–462.Google Scholar
[KK]Krawczyk, A. and Krynicki, M., Ehrenfeucht games for generalized quantifiers, Set theory and hierarchy theory (Marek, W.et al., editors), Lecture Notes in Mathematics, vol. 537, Springer-Verlag, Berlin, 1976, pp. 145–152.Google Scholar
[Kr1]Krynicki, M., On the expressive power of the language using the Henkln quantifier, Essays on mathematical and philosophical logic (Hintikka, J.et al., editors), Reidel, Dordrecht, 1979, pp. 259–265.CrossRefGoogle Scholar
[Kr2]Krynicki, M., On some applications of games for Härtig quantifier, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 33 (1987), pp. 359–370.CrossRefGoogle Scholar
[KL]Krynicki, M. and Lachlan, A., On the semantics of the Henkln quantifier, this Journal, vol. 44 (1979), pp. 184–200.Google Scholar
[Li1]Lindström, P., First-order predicate logic with generalized quantifiers, Theoria, vol. 32 (1966), pp. 186–195.CrossRefGoogle Scholar
[Li2]Lindström, P., On extensions of elementary logic, Theoria, vol. 32 (1969), pp. 245–249.Google Scholar
[Ma]Magidor, M., On the role of supercompact and extendible cardinals in logic, Israel Journal of Mathematics, vol. 10 (1971), pp. 147–157.CrossRefGoogle Scholar
[MSS]Makowsky, A., Shelah, S., and Stavi, J., ⊿-logics and generalized quantifiers, Annals of Mathematical Logic, vol. 10 (1976), pp. 155–192.CrossRefGoogle Scholar
[Mo]Montague, R., Reductions of higher-order logic, The theory of models (Addison, J.et al., editors), North-Holland, Amsterdam, 1965, pp. 251–264.Google Scholar
[Mo1]Mostowski, A., On a generalization of quantifiers, Fundamenta Mathematicae, vol. 44 (1957), pp. 12–36.CrossRefGoogle Scholar
[Mo2]Mostowski, A., Craig's interpolation theorem in some extended system of logic, Logic, methodology and philosophy of science III, North-Holland, Amsterdam, 1968, pp. 87–103.CrossRefGoogle Scholar
[Pil]Pinus, A., Cardinality of models for theories in a calculus with a Härtig quantifier, Siberian Mathematical Journal, vol. 17 (1978), pp. 949–955.Google Scholar
[Pi2]Pinus, A., Hanf number for the calculus with the Härtig quantifier, Siberian Mathematical Journal, vol. 20 (1979), pp. 315–316.CrossRefGoogle Scholar
[Re]Rescher, N., Plurality quantification, this Journal, vol. 27 (1969), pp. 373–374.Google Scholar
[Se1]Schiemann, I., Eine Axiomatisierung des monadischen Prädikatenkalkülus mit verallgemeinerten Quantoren, Wissenschaftliche Zeitschrift der Humboldt-Universität zu Berlin, vol. 26 (1977), pp. 647–657.Google Scholar
[Sc2]Schiemann, I., Untersuchungen zu Logiken mit Lindström-Quantoren, Doctoral Dissertation, Humboldt-Universität, Berlin, 1987.Google Scholar
[Se1]Seese, D., Entscheidbarkeits- und Definierbarkeitsfragen der Theorie “netzartiger” Graphen. I, Wissenschaftliche Zeitschrift der Humboldt-Universität zu Berlin, vol. 21 (1972), pp. 513–517.Google Scholar
[Se2]Seese, D., A remark to the undecidability of well-orderings with the Härtig quantifier, Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 26 (1978) p. 951.Google Scholar
[Se3]Seese, D., Decidability and generalized quantifiers, Logic Colloquium '77 (Macintyre, A.et al., editors), North-Holland, Amsterdam, 1978, pp. 229–237.CrossRefGoogle Scholar
[Si]Silver, J., Some applications of model theory in set theory, Annals of Mathematical Logic, vol. 3 (1971), pp. 45–110.CrossRefGoogle Scholar
[S1]Slomson, A., The monadic fragment of predicate calculus with the Chang quantifier and equality, Lecture Notes in Mathematics, vol. 70, Springer-Verlag, Berlin, 1968, pp. 279–301.Google Scholar
[St]Stavi, J., Compactness properties of infinitary and abstract languages. I: General results, Logic Colloquium '77 (Macintyre, A.et al., editors), North-Holland, Amsterdam, 1978, pp. 265–275.Google Scholar
[SV]Stavi, J. and Väänänen, J., Reflection principles for the continuum (to appear).Google Scholar
[Ta]Tarski, A., The concept of truth in formalized languages, Logic, semantics, methamatematics. Papers from 1923 to 1938, Clarendon Press, Oxford, 1956, pp. 152–278.Google Scholar
[TMR]Tarski, A., Mostowski, A., and Robinson, R., Undecidable theories, North-Holland, Amsterdam, 1953.Google Scholar
[Tu1]Tuschik, P., Elimination of cardinality quantifiers, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 28 (1982), pp. 75–81.CrossRefGoogle Scholar
[Tu2]Tuschik, P., Untersuchung linearer Ordungen in der Logik mit Malitzquantoren, Habilitationsschrift, Humboldt-Universität, Berlin, 1982.Google Scholar
[Vä1]Väänänen, J., Two axioms of set theory with applications to logic, Annales Academiae Scientiarum Fennicae Series A. I Dissertationes Mathematica, vol. 20 (1978), pp. 1–19.Google Scholar
[Vä2]Väänänen, J., Abstract logic and set theory. I: Definability, Logic Colloquium '78 (Boffa, M.et al., editors), North-Holland, Amsterdam, 1979, pp. 391–421.Google Scholar
[Vä3]Väänänen, J., On Hanf numbers of unbounded logics, Proceedings from 5th Scandinavian Logic Symposium (Jensen, F.et al., editors), Aalborg University Press, Aalborg, 1979, pp. 309–328.Google Scholar
[Vä4]Väänänen, J., On logic with the Härtig quantifier, this Journal, vol. 44 (1979), pp. 465–466.Google Scholar
[Vä5]Väänänen, J., Remarks on free quantifier variables, Essays on mathematical and philosophical logic (Hintikka, J.et al., editors), Reidel, Dordrecht, 1979, pp. 267–272.CrossRefGoogle Scholar
[Vä6]Väänänen, J., A quantifier for isomorphisms, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 26 (1980), pp. 123–130.CrossRefGoogle Scholar
[Vä7]Väänänen, J., Boolean-valued models and generalized quantifiers, Annals of Mathematical Logic, vol. 18 (1980), pp. 193–225.CrossRefGoogle Scholar
[Vä8]Väänänen, J., The Hanf number of , Proceedings of the American Mathematical Society, vol. 79 (1980), pp. 294–297.Google Scholar
[Vä9]Väänänen, J., Abstract logic and set theory. II: Large cardinals, this Journal, vol. 47 (1982), pp. 335–345.Google Scholar
[Vä10]Väänänen, J., Generalized quantifiers in models of set theory, Patras Logic Symposion (Metakides, G., editor), North-Holland, Amsterdam, 1982, pp. 359–371.CrossRefGoogle Scholar
[Vä11]Väänänen, J., ⊿-extension and Hanf numbers, Fundamenta Mathematicae, vol. 115 (1983), pp. 43–55.CrossRefGoogle Scholar
[Vä12]Väänänen, J., Set-theoretic definability of logics, in [BF], pp. 599–643.CrossRefGoogle Scholar
[We1]Weese, M., Entscheidbarkeit der Theorie der Booleschen Algebren in Sprachen mit Mächtigkeitsquantoren, Habilitationsschrift, Humboldt-Universität, Berlin, 1976.Google Scholar
[We2]Weese, M., The universality of Boolean algebras with the Härtig quantifier, Set theory and hierarchy theory (Marek, W.et al., editors), Lecture Notes in Mathematics, vol. 537, Springer-Verlag, Berlin, 1976, pp. 291–296.Google Scholar
[We3]Weese, M., The undecidability of well-ordering with the Härtig quantifier, Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 25 (1977), pp. 89–91.Google Scholar
[We4]Weese, M., Decidability with respect to the Härtig and Rescher quantifiers, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 27 (1981), pp. 569–576.CrossRefGoogle Scholar
[Ya1]Yasuhara, M., On categorical PC classes of an extended first-order language, Notices of the American Mathematical Society, vol. 9 (1962), p. 323. (Abstract)Google Scholar
[Ya2]Yasuhara, M., Incompleteness of Lp languages, Fundamenta Mathematicae, vol. 66 (1969), pp. 147–152.CrossRefGoogle Scholar