Lindström quantifier

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 ¯ a tuple of elements of the domain dom(A) of A. In other words, ϕ A , x , a ¯ denotes a (monadic) property defined on dom(A). In general, where x is replaced by an n-tuple x ¯ of free variables, ϕ A , x ¯ , 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

where ∀ A is the singleton whose sole member is dom(A), and ∃ 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 a structure, each of which has a cardinality off 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 ( ϕ ( x 1 x 2 ) , ψ ( y 1 ) , θ ( z 1 z 2 z 3 ) ) is defined semantically as

where

for an n-tuple x ¯ of variables.

Lindström quantifiers are classified according to the number structure of their parameters. For example Q x y ϕ ( x ) ψ ( y ) is a type (1,1) quantifier, whereas Q x y ϕ ( 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|}. 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:

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.