Hostname: page-component-7c8c6479df-94d59 Total loading time: 0 Render date: 2024-03-26T21:19:11.329Z Has data issue: false hasContentIssue false

On the semantics of the Henkin quantifier

Published online by Cambridge University Press:  12 March 2014

Michał Krynicki
Affiliation:
Institute of Mathematics, University of Warsaw, Poland
Alistair H. Lachlan
Affiliation:
Simon Fraser University, British Columbia, Canada

Extract

In [5] Henkin defined a quantifier, which we shall denote by QH: linking four variables in one formula. This quantifier is related to the notion of formulas in which the usual universal and existential quantifiers occur but are not linearly ordered. The original definition of QH was

Here (QHx1x2y1y2)φ is true if for every x1 there exists y1 such that for every x2 there exists y2, whose choice depends only on x2 not on x1 and y1 such that φ(x14, x2, y1, y2). Another way of writing this is

In [5] it was observed that the logic L(QH) obtained by adjoining QH defined as in (1) is more powerful than first-order logic. In particular, it turned out that the quantifier “there exist infinitely many” denoted Q0 was definable from QH because

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1979

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

[1]Barwise, K. J., Axioms for abstract model theory, Annals of Mathematical Logic, vol. 7 (1974), pp. 221265.CrossRefGoogle Scholar
[2]Bell, J. L. and Slomson, A. B., Models and ultraproducts, North-Holland, Amsterdam, 1969.Google Scholar
[3]Enderton, H.B., Finite partially ordered quantifiers, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 16 (1970), pp. 393397.Google Scholar
[4]Härtig, K., Uber einen Quantifikator mit zwei Wirkungsbereichen, Colloquium on the Foundations of Mathematics, Mathematical Machines and their Applications, Tihany (Hungary), 1962, Budapest/Paris, 1965, pp. 3136.Google Scholar
[5]Henkin, L., Some remarks on infinitely long formulas, Infinitistic methods, Pergamon Press, New York, and Polish Scientific Publishers, Warsaw, 1961, pp. 167183.Google Scholar
[6]Herre, H., Entscheidungsprobleme für Theorien in Logiken mit veralgemeinerten Quantoren, issertation zur Erlangung des akademischen Grades doctor Scientiae naturalis, Humboldt-Universität zu Berlin, 1974.Google Scholar
[7]Hintikka, K. J. J., Reductions in the theory of types, Acta Philosophica Fennica, vol. 8 (1955), pp. 61115.Google Scholar
[8]Hintikka, K. J. J., Quantifiers versus quantification theory, Linguistic Enquiry, vol. 5 (1974), pp. 153177.Google Scholar
[9]Issel, W., Semantische Untersuchungen über Quantoren I, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 15 (1969), pp. 353358.CrossRefGoogle Scholar
[10]Krynicki, M., O pewnych logikach z dodatkowym kwantyfikatorem, Master's Thesis, University of Warsaw, 1973.Google Scholar
[11]Krynicki, M., O pewnych rozszeneniach logiki Lωω, Doctoral Thesis, University of Warsaw, 1976.Google Scholar
[12]Lindstrom, P., On extensions of elementary logic, Theoria, vol. 35 (1969), pp. 111.CrossRefGoogle Scholar
[13]Löb, M. H., Decidability of the monadic predicate calculus with unary function symbols, this Journal, vol. 32 (1967), p. 563.Google Scholar
[14]Presburger, M., Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, Comptes-Rendus du I Congrès des Mathématiciens des Pays Slaves, Warsaw, 1929, pp. 92–101, 395.Google Scholar
[15]Slomson, A. B., The monadic fragment of predicate calculus with the Chang quantifier and equality, Proceedings of the Summer School in Logic, Leeds, 1967, Lecture Notes in Mathematics, no. 70, Springer-Verlag, Berlin, 1968, pp. 269301.Google Scholar
[16]Walkoe, W. J. Jr., Finite partially ordered quantifiers, this Journal, vol. 35 (1970), pp. 535555.Google Scholar
[17]Weese, M., The undecidability of the theory of well ordering with the quantifier. I (to appear).Google Scholar
[18]Yasuhara, A., Recursive function theory and logic, Academic Press, New York, 1971.Google Scholar
[19]Yasuhara, A., An axiomatic system for first-order languages with an equicardinality quantifier, this Journal, vol. 31 (1966), pp. 633640.Google Scholar
[20]Yasuhara, A., Incompleteness of Lp languages, Fundamenta Mathematicae, vol. 66 (1969), pp. 147152.CrossRefGoogle Scholar