Definition

In first-order logic, there are two quantifiers ${\displaystyle \forall ,\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}\forall x\psi }$ to mean "a quantified formula ${\displaystyle \forall x\psi }$ is modelled by the model ${\displaystyle {\mathcal {M}}}$ with the interpretation ${\displaystyle I}$". By definition,$${\displaystyle {\mathcal {M}}\models _{I}\forall x\psi \iff \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}\exists x\psi \iff \exists a\in M,\;{\mathcal {M}}\models _{I[a/x]}\psi }$$This can be written in set-theoretic notation as$${\displaystyle {\begin{aligned}{\mathcal {M}}\models _{I}\forall x\psi &\iff \{a\in M:{\mathcal {M}}\models _{I[a/x]}\psi \}\in \{M\}\\{\mathcal {M}}\models _{I}\exists x\psi &\iff \{a\in M:{\mathcal {M}}\models _{I[a/x]}\psi \}\in \{S\in {\mathcal {P}}(M):S\neq \emptyset \}\end{aligned}}}$$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 \forall ,\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{aligned}{\mathcal {M}}\models _{I}\forall x\psi &\iff \{a\in M:{\mathcal {M}}\models _{I[a/x]}\psi \}\in \forall ^{\mathcal {M}}\\{\mathcal {M}}\models _{I}\exists x\psi &\iff \{a\in M:{\mathcal {M}}\models _{I[a/x]}\psi \}\in \exists ^{\mathcal {M}}\end{aligned}}}$$where ${\displaystyle \forall ^{\mathcal {M}}:=\{M\}}$ is the model of the symbol ${\displaystyle \forall }$ in the model ${\displaystyle {\mathcal {M}}}$, and ${\displaystyle \exists ^{\mathcal {M}}:=\{S\in {\mathcal {P}}(M):S\neq \emptyset \}}$ is the model of the symbol ${\displaystyle \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 \iff \{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 \langle k\rangle }$.

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 Qx_{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 \langle m_{1},m_{2},\dots ,m_{n}\rangle }$. If its signature is of form ${\displaystyle \langle 1,1,\dots ,1\rangle }$, then it is monadic, otherwise it is polyadic.

Examples

Of type ⟨1⟩:

• ${\displaystyle \exists _{=1}}$ meaning "there exists exactly 1" is defined by ${\displaystyle \exists _{=1}^{\mathcal {M}}:=\{\{a\}:a\in M\}}$
• And more generally, we can define ${\displaystyle \exists _{=2},\exists _{=3},\dots }$ by ${\displaystyle \exists _{=2}^{\mathcal {M}}:=\{\{a,b\}:a\in M,b\in M,a\neq b\}}$, etc.
• ${\displaystyle \exists _{\leq n}}$ meaning "there exists at most n" is defined by ${\displaystyle \exists _{\leq n}^{\mathcal {M}}:=\{S:S\subset M,|S|\leq n\}}$.
• ${\displaystyle \exists _{\geq \omega }}$ meaning "there exists infinitely many" is defined by ${\displaystyle \exists _{\geq \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 \forall x\neq 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\neq y}$ and the edge ${\displaystyle (x,y)}$ is colored with the i-th color. Then the infinite Ramsey theorem states that ${\displaystyle \bigvee _{i=1}^{m}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}}$.^[3]

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".^[4]

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 \forall a_{1},\dots ,a_{n}\in N,R\upharpoonright N(a_{1},\dots ,a_{n})\iff R(a_{1},\dots ,a_{n})}$$Using this operation, a quantifier ${\displaystyle Q}$ of type ${\displaystyle \langle m_{1},\dots ,m_{n}\rangle }$ can be relativized to a quantifier ${\displaystyle Q_{\text{rel}}}$ of type ${\displaystyle \langle 1,m_{1},\dots ,m_{n}\rangle }$ 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'}$, we have a ⟨2⟩ quantifier ${\displaystyle Q\cdot Q'}$. This is obtained by generalizing the construction for ${\displaystyle \forall ,\exists }$. Specifically, given a binary relation ${\displaystyle R}$, the sentence ${\displaystyle \forall x\exists y,R(x,y)}$ can be analyzed as ${\displaystyle (\forall \cdot \exists )xy,R(x,y)}$, where ${\displaystyle \forall \cdot \exists }$ is a ⟨2⟩ quantifier obtained by iterating ${\displaystyle \forall }$ to ${\displaystyle \exists }$.

A model ${\displaystyle {\mathcal {M}}}$ models ${\displaystyle \forall x\exists y,R(x,y)}$ iff ${\displaystyle \forall ^{\mathcal {M}}(\{a\in M:\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'}$ of types ⟨1⟩, ⟨1⟩, they iterate to a type ⟨2⟩ quantifier:$${\displaystyle (Q\cdot Q')^{\mathcal {M}}(R^{\mathcal {M}}):=Q^{\mathcal {M}}(\{a\in M:Q'^{\mathcal {M}}(R^{\mathcal {M}}(a,\cdot ))\})}$$Given ${\displaystyle Q_{1},\dots ,Q_{n}}$ quantifiers of types ${\displaystyle \langle m_{1}\rangle ,\dots ,\langle m_{n}\rangle }$, they iterate to ${\displaystyle Q_{1}\cdot \dots \cdot Q_{n}}$, a ${\displaystyle \langle m_{1}+\dots +m_{n}\rangle }$ quantifier.

Resumption: Given a quantifier ${\displaystyle Q}$ of type ${\displaystyle \langle 1,\dots ,1\rangle }$, it can be resumed to a quantifier ${\displaystyle \operatorname {Res} _{k}(Q)}$ of type ${\displaystyle \langle k,\dots ,k\rangle }$, 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 \operatorname {Res} _{k}(Q)^{\mathcal {M}}(R_{1},\dots ,R_{n})\iff 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 \exists }$. The formula ${\displaystyle \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 \operatorname {Res} _{2}(\exists )x_{1}x_{2},x_{1}=x_{2}}$ is a formula that is interpreted over a plain model.

Monotonicity

Conservativity

A determiner D is said to be conservative if the following equivalence holds: $${\displaystyle D(A)(B)\leftrightarrow D(A)(A\cap B)}$$ For example, the following two sentences are equivalent.

1. Every boy sleeps.
2. Every boy is a boy who sleeps.

It has been proposed that all determiners—in every natural language—are conservative.^[2] The expression only is not conservative. The following two sentences are not equivalent. But it is, in fact, not common to analyze only as a determiner. Rather, it is standardly treated as a focus-sensitive adverb.

1. Only boys sleep.
2. Only boys are boys who sleep.