Why we have 2 quantifiers in predicate logic?

1.4k Views Asked by At

This might be a request for further philosophical clarification, rather than a mathematical question. You know, we are working with two kind of quantifiers $\forall x$ and $\exists x$. Somehow, we decided this language is enough for us. I can see that. For example, I can express further things like "There exists more than three elements in this set that satisfies predicate P". For example, I can try to express this as

$$\exists x, y, z, w .P(x) \land P(y) \land P(z) \land P(w)$$

I think this captures my initial statement. If I can find 4 elements that P is true for all of them, then I can say there exists more than three elements in this set that satisfies P. You see though, I needed to use 4 auxiliary variables to express this and if I wanted to say "there are more than 100 elements", I could not find enough symbols to identify my variables.

In a way, what I am trying to say is, yes two quantifiers are powerful to express whole of these kind of things but they are not nice to use when things get ugly. It is, as if, predicate logic is a designed language just like programming languages and somewhere along the way designers decided 2 quantifiers are enough to express mathematics.

My question is, why we have 2 quantifiers? Who decided that it is best? Why we don't have further syntax to express other notions? For example, I could explain "there exists more than 100 elements in the set that satisfies predicate P" as $$\exists_{>100}x.P(x)$$

why we don't have something like this? I can see that mathematics is the collective work of many geniuses and there is definitely a reason why my above suggestion is not used in mathematics. But what is the reason for things being as they are?

Edit: There are clarifications and suggestions for further notation in the comments. But what I am really asking is, what is the "design rationale" you should have in mind when deciding on available quantifiers for your logic? There are logics beside predicate logic and we might devise new ones in the future. How mathematicians tackle this problem of making available "just enough" quantifiers? For example, do they seek minimal number of quantifiers that makes their logic complete, or some similar things?

2

There are 2 best solutions below

1
On BEST ANSWER

If you just want quantifiers for counting there are things like $\exists^{=n}x$, $\exists^{>n}x$,$\exists^{\leq n} x$ which say that there exists exactly n, more than n and less than or equal to n elements such that.

As you seem to be aware of, the counting quantifiers meaning can already be expressed in predicate logic. If we wanted to include all counting quantifiers we would suddenly go from 2 to an infinite amount of quantifiers. It sure works, but having a system containing an infinite amount of redundant axioms seems a bit ... bad.

Note though that already having both $\forall x$ and $\exists x$ is a bit redundant since $\forall x \varphi$ is equivalent with $\neg \exists x \neg \varphi$, so we could actually make do with only a single quantifier if we wanted. The reason why we usualy include both quantifiers is because it good for translation purposes.

Now there are also other logics where you allow more quantifiers (which can not be expressed using $\forall$ and $\exists$) such as Least Fixpoint Logic, and there are logics where you allow less quantifiers, such as $FO^{<s}$. These are useful logics which have their applications in different contexts

One can ask why we are almost always using "normal" predicate logic when doing reasonings in mathematics, and one of the reasons for that I would argue is the fact that, According to Linströms theorem, it is the logic which satisfies both the Compactness theorem and the Löwenheim-Skolem theorem. If you do not know what these theorems say it is fine. These are fundamental theorems which essentially say how nice certain basic aspects of the logical reasoning are.

I hope this, somewhat is what you sought in an answer.

0
On

Using the minimum number possible is indeed one of the factors. In fact, many authors just use one quantifier (often the universal one) and view the other one as just a definition in terms of the quantifier that was included. For many proofs, every symbol in the logic requires its own case, and so reducing the number of logical symbols reduces the length of proofs that have to be written up. There was also a historical preference for minimalism - some authors prefer not to have redundant axioms, and so having a large number of redundant quantifiers might also have seemed avoidable.