×

The hierarchy theorem for generalized quantifiers. (English) Zbl 0864.03028

Authors’ summary: “The concept of a generalized quantifier of a given type was defined in [12] [P. Lindström, “First order predicate logic with generalized quantifiers”, Theoria 32, 186-195 (1966; Zbl 1230.03072)]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity type \(t\) there is a generalized quantifier which is not definable in the extension of a first-order logic by all generalized quantifiers of type smaller than \(t\). This was proved for unary similarity types by Per Lindström (D. Westerståhl, personal communication) with a counting argument. We extend his method to arbitrary similarity types.”
It remains to remark that, moreover, any extensions of the basic result mentioned above are proved in the paper.
Let \(t\) be an arbitrary type. Then there is a monotone generalized quantifier \(Q\) of type \(t\) which is not definable in the extension of first-order logic by all generalized quantifiers of type lower than \(t\).
For each type \(t\) there is a generalized quantifier \(Q\) of this type such that \(Q\) is not definable in the extension of second-order logic by all generalized quantifiers of typ lower than \(t\).
Finally, for each type \(t\) there is a class \(Q\) of ordered structures of type \(t\) such that \(Q\) is not definable on the class of ordered structures in the extension of first-order logic by all classes of ordered structures of type lower than \(t\).

MSC:

03C80 Logic with extra quantifiers and operators
03C13 Model theory of finite structures
03C30 Other model constructions

Citations:

Zbl 1230.03072
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1093/logcom/5.2.213 · Zbl 0815.03021 · doi:10.1093/logcom/5.2.213
[2] DOI: 10.1016/0012-365X(77)90116-9 · Zbl 0389.05006 · doi:10.1016/0012-365X(77)90116-9
[3] DOI: 10.1007/BF01305232 · Zbl 0785.68043 · doi:10.1007/BF01305232
[4] Model-theoretic logics (1985)
[5] Dynamics, polarity and quantification pp 173– (1994)
[6] Handbook of philosophical logic IV pp 1– (1989)
[7] Logic and abstraction 1 pp 317– (1986)
[8] Set theory and hierarchy theory 14 pp 117– (1977)
[9] Comment. Math. Univ. Carol.
[10] Theoria 32 pp 186– (1966)
[11] DOI: 10.1305/ndjfl/1093870519 · Zbl 0543.03020 · doi:10.1305/ndjfl/1093870519
[12] DOI: 10.1016/0168-0072(94)00025-X · Zbl 0826.03017 · doi:10.1016/0168-0072(94)00025-X
[13] Quantifiers: Logics, models and computation II pp 79– (1995)
[14] DOI: 10.1016/0168-0072(89)90070-5 · Zbl 0683.03020 · doi:10.1016/0168-0072(89)90070-5
[15] Information and Computation (1992)
[16] Mathematical logic in Latin America pp 83– (1980)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.