Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Lindström quantifier
Summary
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.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.