Generalized quantifier

Model theory

Definition

In first-order logic, there are two quantifiers ${\displaystyle \mathrm{\forall },\mathrm{\exists }}$. They have a fixed meaning in model-theoretic semantics (that is, set-theoretic semantics) of first-order logic, as follows.

Given a first-order language, a model ${\displaystyle \mathcal{M}}$ of the language, and an interpretation ${\displaystyle I}$ of the variables, we write ${\displaystyle \mathcal{M}{\models }_I\mathrm{\forall }x\psi }$ to mean "a quantified formula ${\displaystyle \mathrm{\forall }x\psi }$ is modelled by the model ${\displaystyle \mathcal{M}}$ with the interpretation ${\displaystyle I}$". By definition,$${\displaystyle \mathcal{M}{\models }_I\mathrm{\forall }x\psi ⟺\mathrm{\forall }a\in M,\mathcal{M}{\models }_{I[a/x]}\psi }$$where ${\displaystyle M}$ is the universe of the model ${\displaystyle \mathcal{M}}$.

Similarly,$${\displaystyle \mathcal{M}{\models }_I\mathrm{\exists }x\psi ⟺\mathrm{\exists }a\in M,\mathcal{M}{\models }_{I[a/x]}\psi }$$This can be written in set-theoretic notation as$${\displaystyle \begin{array}{cc}\mathcal{M}{\models }_I\mathrm{\forall }x\psi & ⟺\{a\in M:\mathcal{M}{\models }_{I[a/x]}\psi \}\in \{M\}\\ \mathcal{M}{\models }_I\mathrm{\exists }x\psi & ⟺\{a\in M:\mathcal{M}{\models }_{I[a/x]}\psi \}\in \{S\in \mathcal{P}(M):S\ne \mathrm{\varnothing }\}\end{array}}$$where ${\displaystyle \mathcal{P}}$ denotes the power set operation.

This may appear somewhat circular, as set theory is usually formalized in a first-order logic (as in ZFC set theory). However, if one takes such a set theory as a given base, then one can build other first-order logics over this base set theory. This is the typical perspective taken in model theory.

Next, we consider ${\displaystyle \mathrm{\forall },\mathrm{\exists }}$ themselves as symbols that are being modelled. This is similar to how equality itself interpreted as a binary relation symbol in first-order logic with equality. Then we rewrite again:$${\displaystyle \begin{array}{cc}\mathcal{M}{\models }_I\mathrm{\forall }x\psi & ⟺\{a\in M:\mathcal{M}{\models }_{I[a/x]}\psi \}\in {\mathrm{\forall }}^{\mathcal{M}}\\ \mathcal{M}{\models }_I\mathrm{\exists }x\psi & ⟺\{a\in M:\mathcal{M}{\models }_{I[a/x]}\psi \}\in {\mathrm{\exists }}^{\mathcal{M}}\end{array}}$$where ${\displaystyle {\mathrm{\forall }}^{\mathcal{M}}:=\{M\}}$ is the model of the symbol ${\displaystyle \mathrm{\forall }}$ in the model ${\displaystyle \mathcal{M}}$, and ${\displaystyle {\mathrm{\exists }}^{\mathcal{M}}:=\{S\in \mathcal{P}(M):S\ne \mathrm{\varnothing }\}}$ is the model of the symbol ${\displaystyle \mathrm{\exists }}$ in the model ${\displaystyle \mathcal{M}}$.

Therefore, we can define the model of a generalized quantifier as follows. Given a first-order language augmented with generalized quantifiers ${\displaystyle Q_1,Q_2,\dots }$, a model ${\displaystyle \mathcal{M}}$ of the language models each ${\displaystyle Q_n}$ as a set ${\displaystyle Q_n^{\mathcal{M}}\subset \mathcal{P}(M)}$, such that$${\displaystyle \mathcal{M}{\models }_I{Q}_{n}x\psi ⟺\{a\in M:\mathcal{M}{\models }_{I[a/x]}\psi \}\in Q_n^{\mathcal{M}}}$$More generally, a quantifier ${\displaystyle Q}$ may quantify over k variables. Then its model is a set ${\displaystyle Q^{\mathcal{M}}\subset \mathcal{P}(M^k)}$. The type of such a quantifier is ${\displaystyle ⟨k⟩}$.

Equivalently, since a subset of ${\displaystyle M^k}$ can be regarded as a k-ary relation on ${\displaystyle M}$, a quantifier over k variables can be regarded as a predicate for k-ary relations on ${\displaystyle M}$.

More generally, a quantifier ${\displaystyle Q}$ is used as follows: $${\displaystyle Q{x}_{1,1},\dots ,x_{1,m_1};x_{2,1},\dots ,x_{2,m_2};\dots ;x_{n,1},\dots ,x_{n,m_n}({\psi }_1,\dots ,{\psi }_n)}$$It is modelled by an n-ary relation over ${\displaystyle m_1}$-ary relation, ${\displaystyle m_2}$-ary relation, ..., ${\displaystyle m_n}$-ary relation over ${\displaystyle M}$. This general definition a generalized quantifier definition is sometimes called a Lindström quantifier.

Such a quantifier is said to have signature ${\displaystyle ⟨m_1,m_2,\dots ,m_n⟩}$. If its signature is of form ${\displaystyle ⟨1,1,\dots ,1⟩}$, then it is monadic, otherwise it is polyadic.

Examples

Of type ⟨1⟩:

• ${\displaystyle {\mathrm{\exists }}_{=1}}$ meaning "there exists exactly 1" is defined by ${\displaystyle {\mathrm{\exists }}_{=1}^{\mathcal{M}}:=\{\{a\}:a\in M\}}$
• And more generally, we can define ${\displaystyle {\mathrm{\exists }}_{=2},{\mathrm{\exists }}_{=3},\dots }$ by ${\displaystyle {\mathrm{\exists }}_{=2}^{\mathcal{M}}:=\{\{a,b\}:a\in M,b\in M,a\ne b\}}$, etc.
• ${\displaystyle {\mathrm{\exists }}_{\le n}}$ meaning "there exists at most n" is defined by ${\displaystyle {\mathrm{\exists }}_{\le n}^{\mathcal{M}}:=\{S:S\subset M,|S|\le n\}}$.
• ${\displaystyle {\mathrm{\exists }}_{\ge \omega }}$ meaning "there exists infinitely many" is defined by ${\displaystyle {\mathrm{\exists }}_{\ge \omega }^{\mathcal{M}}:=\{S:S\subset M,S\text{ is infinite}\}}$.
• The Rescher quantifier, meaning "more often than not" is defined by ${\displaystyle Q_R^{\mathcal{M}}:=\{S:S\subset M,|S|>|M\setminus S|\}}$.

Of type ⟨2⟩:

• ${\displaystyle W}$ meaning "is a well-ordering" is defined by ${\displaystyle W^{\mathcal{M}}:=\{S:S\subset M\times M,S\text{ is a well-ordering of }M\}}$. For example, ${\displaystyle Wxy,x<y}$ means "${\displaystyle <}$ is a well-ordering". Given a model ${\displaystyle \mathcal{M}}$ of ${\displaystyle Wxy,x<y}$, the structure ${\displaystyle (M,{<}^{\mathcal{M}})}$ is a well-ordered partially ordered set. Notably, well-ordering is not axiomatizable in standard first-order logic, thus showing that we have expanded the power of the logical language.

• Ramsey quantifier ${\displaystyle Q^2}$, defined by ${\displaystyle S\in (Q^2{)}^{\mathcal{M}}}$ iff there is an infinite ${\displaystyle A\subset M}$, such that ${\displaystyle \mathrm{\forall }x\ne y\in A,(x,y)\in S}$. For example, the infinite Ramsey theorem states that if one has an infinite set ${\displaystyle M}$, and draw an edge between any pair of points, and color each edge from one of a finite number of colors, then there exists an infinite clique of the same color. Let ${\displaystyle C_1,\dots ,C_m}$ be 2-ary relations, such that ${\displaystyle C_i(x,y)}$ means ${\displaystyle x\ne y}$ and the edge ${\displaystyle (x,y)}$ is colored with the i-th color. Then the infinite Ramsey theorem states that ${\displaystyle \underset{i=1}{\overset{m}{\bigvee }}{Q}^2(C_i)}$.

Of type ⟨n⟩:

• Ramsey quantifier ${\displaystyle Q^n}$, defined by ${\displaystyle S\in (Q^n{)}^{\mathcal{M}}}$ iff there is an infinite ${\displaystyle A\subset M}$, such that any size-n subset ${\displaystyle \{a_1,\dots ,a_n\}\subset A}$, we have ${\displaystyle (a_1,\dots ,a_n)\in S}$. The infinite Ramsey theorem can be stated with ${\displaystyle Q^n}$.

Of type ⟨1, 1⟩:

• "All" is defined by ${\displaystyle {\text{All}}^{\mathcal{M}}:=\{(A,B):A\subset B,B\subset M\}}$. For example, "all men are mortal" is written as ${\displaystyle \text{All }x,y,(\text{man}(x),\text{mortal}(y))}$. Similarly, "Some", "Not any", and "Not all" are of type ⟨1, 1⟩. In this way, the 4 types of sentences in term logic are naturally expressed in first-order logic with generalized quantifiers.
• Similarly, "at least 5", "exactly 3", "an even number of", "there are more than", .
• The Härtig quantifier, meaning "equally many".

Operations

Quantifiers can be combined and modified to create more quantifiers, using operations upon quantifiers.

Relativization: An n-ary relation ${\displaystyle R}$ on a set ${\displaystyle M}$ can be relativized to a subset ${\displaystyle N\subset M}$, by defining ${\displaystyle R\upharpoonright N:=R\cap N^n}$. In other words, $${\displaystyle \mathrm{\forall }{a}_1,\dots ,a_n\in N,R\upharpoonright N(a_1,\dots ,a_n)⟺R(a_1,\dots ,a_n)}$$Using this operation, a quantifier ${\displaystyle Q}$ of type ${\displaystyle ⟨m_1,\dots ,m_n⟩}$ can be relativized to a quantifier ${\displaystyle Q_{\text{rel}}}$ of type ${\displaystyle ⟨1,m_1,\dots ,m_n⟩}$ by taking its first slot to be the set over which it relativizes:$${\displaystyle Q_{\text{rel}}^{\mathcal{M}}(N,R_1,\dots ,R_n):=Q^{\mathcal{M}}(R_1\upharpoonright N,\dots ,R_n\upharpoonright N)}$$Iteration: Given two ⟨1⟩ quantifiers ${\displaystyle Q,Q^{\prime }}$, we have a ⟨2⟩ quantifier ${\displaystyle Q\cdot Q^{\prime }}$. This is obtained by generalizing the construction for ${\displaystyle \mathrm{\forall },\mathrm{\exists }}$. Specifically, given a binary relation ${\displaystyle R}$, the sentence ${\displaystyle \mathrm{\forall }x\mathrm{\exists }y,R(x,y)}$ can be analyzed as ${\displaystyle (\mathrm{\forall }\cdot \mathrm{\exists })xy,R(x,y)}$, where ${\displaystyle \mathrm{\forall }\cdot \mathrm{\exists }}$ is a ⟨2⟩ quantifier obtained by iterating ${\displaystyle \mathrm{\forall }}$ to ${\displaystyle \mathrm{\exists }}$.

A model ${\displaystyle \mathcal{M}}$ models ${\displaystyle \mathrm{\forall }x\mathrm{\exists }y,R(x,y)}$ iff ${\displaystyle {\mathrm{\forall }}^{\mathcal{M}}(\{a\in M:{\mathrm{\exists }}^{\mathcal{M}}(R^{\mathcal{M}}(a,\cdot ))\})}$, where ${\displaystyle R^{\mathcal{M}}(a,\cdot )}$ is the 1-ary relation on ${\displaystyle M}$ obtained by plugging in ${\displaystyle a\in M}$ to the first slot of the 2-ary relation ${\displaystyle R}$ on ${\displaystyle M}$.

Generalizing, given two quantifiers ${\displaystyle Q,Q^{\prime }}$ of types ⟨1⟩, ⟨1⟩, they iterate to a type ⟨2⟩ quantifier:$${\displaystyle (Q\cdot Q^{\prime }{)}^{\mathcal{M}}(R^{\mathcal{M}}):=Q^{\mathcal{M}}(\{a\in M:Q^{\prime \mathcal{M}}(R^{\mathcal{M}}(a,\cdot ))\})}$$Given ${\displaystyle Q_1,\dots ,Q_n}$ quantifiers of types ${\displaystyle ⟨m_1⟩,\dots ,⟨m_n⟩}$, they iterate to ${\displaystyle Q_1\cdot \cdots \cdot Q_n}$, a ${\displaystyle ⟨m_1+\cdots +m_n⟩}$ quantifier.

Resumption: Given a quantifier ${\displaystyle Q}$ of type ${\displaystyle ⟨1,\dots ,1⟩}$, it can be resumed to a quantifier ${\displaystyle {\mathrm{Res}}_k(Q)}$ of type ${\displaystyle ⟨k,\dots ,k⟩}$, using the fact that a k-ary relation ${\displaystyle R}$ on a set ${\displaystyle M}$ is the same as a 1-ary relation on ${\displaystyle M^k}$:$${\displaystyle {\mathrm{Res}}_k(Q{)}^{\mathcal{M}}(R_1,\dots ,R_n)⟺Q^{\mathcal{M}}(R_1,\dots ,R_n)}$$Note that though they are formally the same, their types are different. One is To see it, consider the resumption of ${\displaystyle \mathrm{\exists }}$. The formula ${\displaystyle \mathrm{\exists }x,\text{first}(x)=\text{second}(x)}$ is a formula that is interpreted over a model for which "first" and "second" are defined, in particular models whose universes are of form ${\displaystyle M\times M}$, whereas ${\displaystyle {\mathrm{Res}}_2(\mathrm{\exists })x_1{x}_2,x_1=x_2}$ is a formula that is interpreted over a plain model.