E : P(x)
Propositional logic, as discussed in module 0023, is quite useful. However, it is not universally useful. Recall the conditional proposition example from that module:
If x < y, x ≤ y.
Although this is, intuitively, correct, it is not quite accepted as a proper proposition. The reason is that we don’t know what is x and what is y. You may say that x and y can be any numbers. But that is implicit! The question is, how can we say that properly?
Furthermore, there are other propositions that cannot be expressed without quantifiers. For example:
“I am the best.”
On the surface, this is sufficient. But that is only because we already understand the word “best”. “Best” implies that “no one is better”. Fine, we’ll rewrite the proposition using the explicit meaning of “best”:
“No one is better than I am.”
Here, we run into another problem. “No one” is not a particular subject, which is required in a proposition. Or, in logic term, we can say that the name “no one” is not bound to anyone explicitly. Now, we are really going for the obscure but necessary notation:
“It is not the case that (there exist person x such that x is better than I am).”
The parantheses are only there to help the grouping of phrases in this example. One may point out that x is, again, a name that is not bound. Well, x is bound by the phrase “there exist person x”.
Is this all very confusing? It is probably so, if this is the first time you encounter this kind of discussion. We’ll spend more time on examples first, then apply quantifiers to propositional logic.
Believe it or not, we use quantifiers everyday. Yes, the word “everyday” is a quantifier! We’ll explore the exact meaning of quantifiers in our everyday sentences.
Let’s think about the following sentence:
“Someone saved Tom from drowning.”
This means that an entity (a person, a dog, a dolphin, an angle,...) saved Tom from drowning. Better yet, we can say that there existed an entity x, such that x saved Tom.
“There existed an entity x, it is true that x saved Tom from drowning.”
The mathematical symbol to use here is ∃. We can now rewrite our sentence as follows, assuming P(x) means “x saved Tom” and E is a set of all entities:
∃x E : P(x)
The colon means “it is true that”. The symbol means the left hand side is in the right hand side.
Let’s think about the following sentence:
“Everyone in the room fainted.”
This means that if x is an entity in the room, x fainted. However, “everyone” is a name that is not bound to anything, so we cannot use it in a proposition. We need a way to bind a name, say x, to each entity in everyone:
“For all (x is an entity in the room), x fainted.”
The above sentence explicity bound x to be an entity in the room. Furthermore, the “for all” part says “it doesn’t matter whom in the room x is bound to, the predicate is still true.” The mathematical representation is as follows, assuming Er means the set of all entities in the room, and P(x) means “x fainted”:
∀x Er : P(x)
“No one” is a little different from the other two. It is a negation term. Let’s consider an example:
“No one can defeat me!”
This means that there does not exist a peron who “can defeat me.” Now, how can we bind a symbol to nobody?
We cannot.
However, we can use the “there exist” notation, and combine that with a negation. Here is how to do it in English:
“It is not true that there exist an entity x such that x can defeat me.”
In mathematical symbol, we have the following, assuming E means all the entities, and P(x) means “x can defeat me”:
¬(∃x E : P(x))
Note that we can also rearrange things a little, and use the “for all” notation instead. In English;
“For all entity x, it is not true that x can defeat me.”
In mathematical symbol, we have:
∀x E : ¬P(x))
Let us explore the following proposition (that is improper):
(x < y) → (x ≤ y)
It was improper because x and y are not bound. Now that we know about the “for all” and “there exist” concepts, we can bind x and y properly. Let I represent the set of integers, then we can write the following:
∀x I : (∀y I : (x < y) → (x ≤ y))
How do we say that an array is sorted in a non-decreasing order? Let us assume that the array is called a, and it has n elements.
∀i [0,n - 2] : ai ≤ ai+1
Note that [0,n - 2] is the set of all integers from 0 to n - 2, including 0 and n - 2.
How do we say that an array is not sorted in a non-decreasing order? Again, the array is a, and it has n elements:
∃i [0,n - 2] : ai > ai+1