Lindström quantifier

In mathematical logic, a Lindström quantifier is a generalized polyadic quantifier. Lindström quantifiers generalize first-order quantifiers, such as the existential quantifier, the universal quantifier, and the counting quantifiers. They were introduced by Per Lindström in 1966. They were later studied for their applications in logic in computer science and database query languages.

Generalization of first-order quantifiers

In order to facilitate discussion, some notational conventions need explaining. The expression

\phi ^{A,x,{\bar {a}}}=\{x\in A\colon A\models \phi [x,{\bar {a}}]\}

for A an L-structure (or L-model) in a language L, φ an L-formula, and ${\bar {a}}$ a tuple of elements of the domain dom(A) of A.^{[clarification needed]} In other words, $\phi ^{A,x,{\bar {a}}}$ denotes a (monadic) property defined on dom(A). In general, where x is replaced by an n-tuple ${\bar {x}}$ of free variables, $\phi ^{A,{\bar {x}},{\bar {a}}}$ denotes an n-ary relation defined on dom(A). Each quantifier $Q_{A}$ 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

A\models \forall x\phi [x,{\bar {a}}]\iff \phi ^{A,x,{\bar {a}}}\in \forall _{A}

A\models \exists x\phi [x,{\bar {a}}]\iff \phi ^{A,x,{\bar {a}}}\in \exists _{A},

where $\forall _{A}$ is the singleton whose sole member is dom(A), and $\exists _{A}$ 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 $Q_{A}x_{1}x_{2}y_{1}z_{1}z_{2}z_{3}(\phi (x_{1}x_{2}),\psi (y_{1}),\theta (z_{1}z_{2}z_{3}))$ is defined semantically as

A\models Q_{A}x_{1}x_{2}y_{1}z_{1}z_{2}z_{3}(\phi ,\psi ,\theta )[a]\iff (\phi ^{A,x_{1}x_{2},{\bar {a}}},\psi ^{A,y_{1},{\bar {a}}},\theta ^{A,z_{1}z_{2}z_{3},{\bar {a}}})\in Q_{A}

^{[clarification needed]}

where

\phi ^{A,{\bar {x}},{\bar {a}}}=\{(x_{1},\dots ,x_{n})\in A^{n}\colon A\models \phi [{\bar {x}},{\bar {a}}]\}

for an n-tuple ${\bar {x}}$ of variables.

Lindström quantifiers are classified according to the number structure of their parameters. For example $Qxy\phi (x)\psi (y)$ is a type (1,1) quantifier, whereas $Qxy\phi (x,y)$ is a type (2) quantifier. An example of type (1,1) quantifier is Hartig's quantifier testing equicardinality, i.e. the extension of {A, B ⊆ M: |A| = |B|}.^{[clarification needed]} 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 as Lindström's theorem, which intuitively states that first-order logic is the "strongest" logic having both properties.

Algorithmic characterization

References

Lindstrom, P. (1966). "First order predicate logic with generalized quantifiers". Theoria. 32 (3): 186–195. doi:10.1111/j.1755-2567.1966.tb00600.x.
L. Hella. "Definability hierarchies of generalized quantifiers", Annals of Pure and Applied Logic, 43(3):235–271, 1989, doi:10.1016/0168-0072(89)90070-5.
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.
Burtschick, Hans-Jörg; Vollmer, Heribert (1999), Lindström Quantifiers and Leaf Language Definability, ECCC TR96-005
Westerståhl, Dag (2001), "Quantifiers", in Goble, Lou (ed.), The Blackwell Guide to Philosophical Logic, Blackwell Publishing, pp. 437–460.
Antonio Badia (2009). Quantifiers in Action: Generalized Quantification in Query, Logical and Natural Languages. Springer. ISBN 978-0-387-09563-9.

External links

Dag Westerståhl, 2011. 'Generalized Quantifiers'. Stanford Encyclopedia of Philosophy.