5
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$")

$\endgroup$
  • $\begingroup$ I am studying logic for the first time. So can you explain simply why you said “By exhibiting infinitely many $a_n$ with $\phi (a_n)$? You cannot do that in a first-order theory per se.” $\endgroup$ – Atom Jun 3 at 13:19
  • $\begingroup$ Also, can you please explain what you mean by in a first-order theory, we can only “speak” about the objects of our universe, but not about sets of objects of our universe? $\endgroup$ – Atom Jun 3 at 13:23
2
$\begingroup$

There are plenty of other quantifiers (ignoring "natural language" examples like "many" which are hard to define):

  • Infinitely many $x$ are $\varphi$.

  • Uncountably many $x$ are $\varphi$.

  • The same number of $x$ are $\varphi$ as are $\psi$.

  • A cofinal set of $x$ (with respect to the ordering given by $\theta$) are $\varphi$.

and so on. These are called generalized quantifiers and their study is a key part of abstract model theory.

Interestingly, while it's generally easy to show that a generalized quantifier isn't first-order definable (usually via compactness), there is a precise sense in which $\{\forall,\exists\}$ is complete: namely, Lindstrom showed that adding any other quantifier to first-order logic which isn't reducible to those two results in a system which is either non-compact or fails to have the Lowenheim-Skolem property. (This is actually a much more general result, which saves us from having to precisely define "quantifier.")

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.