Lindström quantifier
Encyclopedia
In mathematical logic
, a Lindström quantifier is a generalized polyadic quantifier
. They are a generalization of first-order quantifiers, such as the existential quantifier, the universal quantifier, and the counting quantifiers.They were introduced by Per Lindström in 1966.
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 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.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, a Lindström quantifier is a generalized polyadic quantifier
Generalized quantifier
In linguistic semantics, a generalized quantifier is an expression that denotes a property of a property, also called a higher-order property. This is the standard semantics assigned to quantified noun phrases, also called determiner phrases, in short: DP...
. They are a generalization of first-order quantifiers, such as the existential quantifier, the universal quantifier, and the counting quantifiers.They were introduced by Per Lindström in 1966.
Generalization of first-order quantifiers
In order to facilitate discussion, some notational conventions need explaining. The expressionfor 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 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 aswhere
for an n-tuple
of variables.