Generalization of first-order quantifiers
In order to facilitate discussion, some notational conventions need explaining. The expression : for ''A'' an ''L''-structure (or ''L''-model) in a language ''L'', ''φ'' an ''L''-formula, and a tuple of elements of the domain dom(''A'') of ''A''. In other words, denotes a ( monadic) property defined on dom(A). In general, where ''x'' is replaced by an ''n''-tuple of free variables, denotes an ''n''-ary relation defined on dom(''A''). Each quantifier is relativized to a structure, since each quantifier is viewed as a family of relations (between relations) on that structure. For a concrete example, take the universal and existential quantifiers ∀ and ∃, respectively. Their truth conditions can be specified as : : where is the singleton whose sole member is dom(''A''), and is the set of all non-empty subsets of dom(''A'') (i.e. the power set of dom(''A'') minus the empty set). In other words, each quantifier is a family of properties on dom(''A''), so each is called a ''monadic'' quantifier. Any quantifier defined as an ''n'' > 0-ary relation between properties on dom(''A'') is called ''monadic''. Lindström introduced polyadic ones that are ''n'' > 0-ary relations between relations on domains of structures. Before we go on to Lindström's generalization, notice that any family of properties on dom(''A'') can be regarded as a monadic generalized quantifier. For example, the quantifier "there are exactly ''n'' things such that..." is a family of subsets of the domain of a structure, each of which has a cardinality of size ''n''. Then, "there are exactly 2 things such that φ" is true in A iff the set of things that are such that φ is a member of the set of all subsets of dom(''A'') of size 2. A Lindström quantifier is a polyadic generalized quantifier, so instead being a relation between subsets of the domain, it is a relation between relations defined on the domain. For example, the quantifier is defined semantically as : where : for an ''n''-tuple of variables. Lindström quantifiers are classified according to the number structure of their parameters. For example is a type (1,1) quantifier, whereas is a type (2) quantifier. An example of type (1,1) quantifier is Hartig's quantifier testing equicardinality, i.e. the extension of . An example of a type (4) quantifier is the Henkin quantifier.Expressiveness hierarchy
The first result in this direction was obtained by Lindström (1966) who showed that a type (1,1) quantifier was not definable in terms of a type (1) quantifier. After Lauri Hella (1989) developed a general technique for proving the relative expressiveness of quantifiers, the resulting hierarchy turned out to be lexicographically ordered by quantifier type: ::(1) < (1, 1) < . . . < (2) < (2, 1) < (2, 1, 1) < . . . < (2, 2) < . . . (3) < . . . For every type ''t'', there is a quantifier of that type that is not definable in first-order logic extended with quantifiers that are of types less than ''t''.As precursors to Lindström's theorem
Although Lindström had only partially developed the hierarchy of quantifiers which now bear his name, it was enough for him to observe that some nice properties of first-order logic are lost when it is extended with certain generalized quantifiers. For example, adding a "there exist finitely many" quantifier results in a loss of compactness, whereas adding a "there exist uncountably many" quantifier to first-order logic results in a logic no longer satisfying the Löwenheim–Skolem theorem. In 1969 Lindström proved a much stronger result now known asAlgorithmic characterization
References
* * L. Hella. "Definability hierarchies of generalized quantifiers", Annals of Pure and Applied Logic, 43(3):235–271, 1989, . * L. Hella. "Logical hierarchies in PTIME". In Proceedings of the 7th IEEE Symposium on Logic in Computer Science, 1992. * L. Hella, K. Luosto, and J. Vaananen. "The hierarchy theorem for generalized quantifiers". '' Journal of Symbolic Logic'', 61(3):802–817, 1996. * *. *Further reading
* Jouko Väänanen (ed.), ''Generalized Quantifiers and Computation. 9th European Summer School in Logic, Language, and Information. ESSLLI’97 Workshop. Aix-en-Provence, France, August 11–22, 1997. Revised Lectures'', SpringerExternal links
*Dag Westerståhl, 2011.