- Lindström quantifier
In
mathematical logic , a Lindström quantifier is a generalized polyadic quantifier. They are a generalization of first-order quantifiers, such as theexistential quantifier , theuniversal quantifier , and thecounting quantifier s.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 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 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.
References
*cite journal | last = Burtschick | first = Hans-Jörg | coauthors = Heribert Vollmer | title = Lindström Quantifiers and Leaf Language Definability | journal = Electronic Colloquium on Computational Complexity | issue = TR96-005 | url = http://eccc.hpi-web.de/eccc-reports/1996/TR96-005/Paper.pdf | format = pdf | accessdate = 2006-11-20 | year = 1999
*Dag Westerståhl. Quantifiers, in "The Blackwell Guide to Philosophical Logic", ed. Lou Goble, Blackwell Publishing, 2001; pp. 437-460.
Wikimedia Foundation. 2010.