Quantifiers in first-order logic

first-order-logiclogicquantifiers

The universal $(\forall)$ and existential $(\exists)$ quantifiers are the normal quantifiers which one comes across frequently. Others like uniqueness quantifier $(\exists !)$ are also there. But in this case, it can be expressed as a combination of the previous two.

Questions: Are there any more examples of quantifiers? Do universal and existential quantifiers form a minimal exhaustive set for all the possible quantifiers? Is there even anything like "all the possible quantifiers"?

For logical connectives, we can be sure that $\{ \wedge ,\neg\}$ is such a set. So is the singleton set containing Sheffer stroke. But here we also have a way to check as we have all the possible truth tables. Is there a way to check for quantifiers as well?

Best Answer

In principle, we could make up arbitrarily many distinct quantifiers. $\forall x\colon \phi(x)$ and $\exists x\colon \phi(x)$ make certain statements about the class $C:=\{\,x\mid \phi(x)\,\}$: One says that $C$ is the all-class (or that its complement is empty), the other says that $C$ is not empty. And $\exists!$ say that $C$ is a singleton. We could introduce quantifiers for quite arbitrary statements about $C$, but the most natural would perhaps be about cardinality of $C$: Stating that $C$ or its complement has at least $n$, at most $n$, more than $n$, less than $n$, or exactly $n$ elements for a fixed finite or infinitie cardinality $n$ come to mind. Of these, those with finite cardinalities are readily constructed from $\exists$ and $\forall$ (just like we do with $\exists!$).

However, any quantifiers about infinite cardinalities are problematic in a first order theory (i.e., when we can only "speak" about the objects of our universe, but not about sets of objects of our universe): There are no suitable rules of inference accompanying them. A proof of $\exists x,\phi(x)$ can consist of constructing a sing $a$ with $\phi(a)$. What should a proof of $\exists^\infty x,\phi(x)$ with $\exists^\infty$ intended to mean "there are infinitely many" look like? By exhibiting infinitely many $a_n$ with $\phi(a_n)$? You cannot do that in a first-order theory per se.

Nevertheless, outside first order formalism, some such quantifiers are very common: A very useful one is "almost all" which in the context of natural numbers is understood to mean "all but finitely many". "Almost all" $n$ have property $\phi$ is then a shortcut for $\exists n_0\in\Bbb N\colon \forall n\in \Bbb N\colon n>n_0\to \phi(n)$, a construct very common in the introduction of limits. Note how the very properties of the set of natural numbers allow us to express "all but finitely many". (In other contexts, such as measure theory, we use "almost all" with a different meaning, namely "up to a set of measure $0$")