Lindström quantifier

<h2 id="generalization-of-first-order-quantifiers">Generalization of first-order quantifiers</h2>
In order to facilitate discussion, some notational conventions need explaining. The expression

ϕ
          
            A
            ,
            x
            ,
            
              
                
                  a
                  ¯
                
              
            
          
        
        =
        {
        x
        ∈
        A
        :
        A
        ⊨
        ϕ
        [
        x
        ,
        
          
            
              a
              ¯
            
          
        
        ]
        }
      
    
    {\displaystyle \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 
 
 
 
 
 
 
 a
 ¯
 
 
 
 
 
 {\displaystyle {\bar {a}}}
 
 a tuple of elements of the domain dom(A) of A. In other words, 
 
 
 
 
 ϕ
 
 A
 ,
 x
 ,
 
 
 
 a
 ¯
 
 
 
 
 
 
 
 {\displaystyle \phi ^{A,x,{\bar {a}}}}
 
 denotes a (<a href="/facts/Monadic_(arity)/zSVuwHvP">monadic</a>) property defined on dom(A). In general, where x is replaced by an n-tuple 
 
 
 
 
 
 
 x
 ¯
 
 
 
 
 
 {\displaystyle {\bar {x}}}
 
 of free variables, 
 
 
 
 
 ϕ
 
 A
 ,
 
 
 
 x
 ¯
 
 
 
 ,
 
 
 
 a
 ¯
 
 
 
 
 
 
 
 {\displaystyle \phi ^{A,{\bar {x}},{\bar {a}}}}
 
 denotes an n-ary relation defined on dom(A). Each quantifier 
 
 
 
 
 Q
 
 A
 
 
 
 
 {\displaystyle 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
        ⊨
        ∀
        x
        ϕ
        [
        x
        ,
        
          
            
              a
              ¯
            
          
        
        ]
        
        ⟺
        
        
          ϕ
          
            A
            ,
            x
            ,
            
              
                
                  a
                  ¯
                
              
            
          
        
        ∈
        
          ∀
          
            A
          
        
      
    
    {\displaystyle A\models \forall x\phi [x,{\bar {a}}]\iff \phi ^{A,x,{\bar {a}}}\in \forall _{A}}

A
        ⊨
        ∃
        x
        ϕ
        [
        x
        ,
        
          
            
              a
              ¯
            
          
        
        ]
        
        ⟺
        
        
          ϕ
          
            A
            ,
            x
            ,
            
              
                
                  a
                  ¯
                
              
            
          
        
        ∈
        
          ∃
          
            A
          
        
        ,
      
    
    {\displaystyle A\models \exists x\phi [x,{\bar {a}}]\iff \phi ^{A,x,{\bar {a}}}\in \exists _{A},}

where 
 
 
 
 
 ∀
 
 A
 
 
 
 
 {\displaystyle \forall _{A}}
 
 is the singleton whose sole member is dom(A), and 
 
 
 
 
 ∃
 
 A
 
 
 
 
 {\displaystyle \exists _{A}}
 
 is the set of all non-empty subsets of dom(A) (i.e. the <a href="/facts/Power_set/FVuf8PDD">power set</a> 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 if and only if 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
 
 
 )
 )
 
 
 {\displaystyle 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
 ⊨
 
 Q
 
 A
 
 
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 
 y
 
 1
 
 
 
 z
 
 1
 
 
 
 z
 
 2
 
 
 
 z
 
 3
 
 
 (
 ϕ
 ,
 ψ
 ,
 θ
 )
 [
 a
 ]
 
 ⟺
 
 (
 
 ϕ
 
 A
 ,
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 ,
 
 
 
 a
 ¯
 
 
 
 
 
 ,
 
 ψ
 
 A
 ,
 
 y
 
 1
 
 
 ,
 
 
 
 a
 ¯
 
 
 
 
 
 ,
 
 θ
 
 A
 ,
 
 z
 
 1
 
 
 
 z
 
 2
 
 
 
 z
 
 3
 
 
 ,
 
 
 
 a
 ¯
 
 
 
 
 
 )
 ∈
 
 Q
 
 A
 
 
 
 
 {\displaystyle 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}}
 
 
where

ϕ
          
            A
            ,
            
              
                
                  x
                  ¯
                
              
            
            ,
            
              
                
                  a
                  ¯
                
              
            
          
        
        =
        {
        (
        
          x
          
            1
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
        ∈
        
          A
          
            n
          
        
        :
        A
        ⊨
        ϕ
        [
        
          
            
              x
              ¯
            
          
        
        ,
        
          
            
              a
              ¯
            
          
        
        ]
        }
      
    
    {\displaystyle \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 
 
 
 
 
 
 
 x
 ¯
 
 
 
 
 
 {\displaystyle {\bar {x}}}
 
 of variables.
Lindström quantifiers are classified according to the number structure of their parameters. For example 
 
 
 
 Q
 x
 y
 ϕ
 (
 x
 )
 ψ
 (
 y
 )
 
 
 {\displaystyle Qxy\phi (x)\psi (y)}
 
 is a type (1,1) quantifier, whereas 
 
 
 
 Q
 x
 y
 ϕ
 (
 x
 ,
 y
 )
 
 
 {\displaystyle 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|}. An example of a type (4) quantifier is the <a href="/facts/Henkin_quantifier/MUVt3u7k">Henkin quantifier</a>.

<h2 id="expressiveness-hierarchy">Expressiveness hierarchy</h2>
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 <a href="/facts/Lexicographical_order/xQANy8Br">lexicographically ordered</a> 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.

<h2 id="as-precursors-to-lindstrms-theorem">As precursors to Lindström's theorem</h2>
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 <a href="/facts/Compactness_theorem/8tHVkdeK">compactness</a>, whereas adding a "there exist uncountably many" quantifier to first-order logic results in a logic no longer satisfying the <a href="/facts/L%25C3%25B6wenheim%25E2%2580%2593Skolem_theorem/pb72J40H">Löwenheim–Skolem theorem</a>. In 1969 Lindström proved a much stronger result now known as <a href="/facts/Lindstr%25C3%25B6m%2527s_theorem/SW9KFVMw">Lindström's theorem</a>, which intuitively states that first-order logic is the "strongest" logic having both properties.

<h2 id="algorithmic-characterization">Algorithmic characterization</h2>

<ul><li>Lindstrom, P. (1966). "First order predicate logic with generalized quantifiers". <a href="/facts/Theoria_(philosophy_journal)/AtdhRAYk">Theoria</a>. 32 (3): 186–195. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1111%2Fj.1755-2567.1966.tb00600.x">10.1111/j.1755-2567.1966.tb00600.x</a>.</li>
<li>L. Hella. "Definability hierarchies of generalized quantifiers", <a href="/facts/Annals_of_Pure_and_Applied_Logic/tR1Pk1tr">Annals of Pure and Applied Logic</a>, 43(3):235–271, 1989, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0168-0072%2889%2990070-5">10.1016/0168-0072(89)90070-5</a>.</li>
<li>L. Hella. "Logical hierarchies in PTIME". In Proceedings of the 7th <a href="/facts/IEEE_Symposium_on_Logic_in_Computer_Science/j7qwgDmc">IEEE Symposium on Logic in Computer Science</a>, 1992.</li>
<li>L. Hella, K. Luosto, and J. Vaananen. "The hierarchy theorem for generalized quantifiers". <a href="/facts/Journal_of_Symbolic_Logic/lfXVXcoy">Journal of Symbolic Logic</a>, 61(3):802–817, 1996.</li>
<li>Burtschick, Hans-Jörg; Vollmer, Heribert (1999), Lindström Quantifiers and Leaf Language Definability, <a href="/facts/Electronic_Colloquium_on_Computational_Complexity/6Tl8NPAM">ECCC</a> <a href="https://eccc.weizmann.ac.il/report/1996/005/">TR96-005</a></li>
<li>Westerståhl, Dag (2001), "Quantifiers", in Goble, Lou (ed.), The Blackwell Guide to Philosophical Logic, Blackwell Publishing, pp. 437–460.</li>
<li>Antonio Badia (2009). Quantifiers in Action: Generalized Quantification in Query, Logical and Natural Languages. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-09563-9.</li></ul>
<h2 id="further-reading">Further reading</h2>
<ul><li>Jouko Väänanen (ed.), Generalized Quantifiers and Computation. 9th European Summer School in Logic, Language, and Information. ESSLLI’97 Workshop. Aix-en-Provence, France, August 11–22, 1997. Revised Lectures, Springer <a href="/facts/Lecture_Notes_in_Computer_Science/1UeA77BC">Lecture Notes in Computer Science</a> 1754, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-66993-0</li></ul>
<h2 id="external-links">External links</h2>
<ul><li>Dag Westerståhl, 2011. '<a href="http://plato.stanford.edu/entries/generalized-quantifiers/">Generalized Quantifiers</a>'. <a href="/facts/Stanford_Encyclopedia_of_Philosophy/LDuL5HW4">Stanford Encyclopedia of Philosophy</a>.</li></ul>

Lindström quantifier open-in-new

Lindström quantifier