Predicate Logic - Quantifiers

In the last chapter, we learnt what are predicates in first-order logic, and how they can be used in propositional function to create proposition, given specific subjectds. Now it's time to extend all that we've learnt with the concept of quantification i.e. asserting something regarding a group of objects, in contrast to one particular object.

As always, instead of directly defining a concept we would gather around all the intuition needed to arrive at it. In some way, this enables you to connect to the essence of the concept more than you would if you were first shown the concept and then its applications.

Anyways, let's get to quantifiers.

Suppose you were given the statement:

Determine the subject and the predicate here. Well, 'Alex' is the subject while 'is working' is the predicate. Not really difficult to guess! Let's consider another such statement.

Once again, '' is the subject and '' is the predicate.

Now let's consider another example.

Now what? Well 'is working' is still the predicate, but what about 'everyone'. We can't call it the subject based on what we learnt in the previous chapter — it is a specific entity. How to express 'Everyone is working' in terms of notation. Surely, the following can't work.

Even if we could have said that 'Everyone' was a subject, in that case also ::\text{W(Everyone)}:: would be imprecise. We couldn't reason a statement like ::\text{W(Alex)}:: from the statement ::\text{W(Everyone)}:: purely notationally.

But let's say, we know all the people whom we are concerned with in the word everyone. For instance, if we are in a class of three students and someone asked us whether everyone is working, by the word 'everyone' we would simply referring to all the 3 students. So if we know our domain, we would write the following.

... in order to say that everyone is working.

In this case, our domain was manageable, and therefore we represented everyone separately. But what if we have a huge domain? For example, how can we notationally express the following:

We could never reach the end of the infinite domain! Clearly, we need a more compact notation to express such statements. This is where the universal quantifier comes in.

It's denoted using the symbol ::\forall:: (an upside-down A). A universal quantification is expressed as follows.

We read this as 'for every ::x::, ::P(x):: holds'. But where do we get the value of every ::x::. This is what the domain is for.

Let's solve our old problem of saying 'Everyone is working' in the class of the three students Alex, Sandra and Joe.

First we specify that the domain of discourse is the set ::\{\text{Alex, Sandra, Joe}\}::. This will be used in our quantification. Next, we see that to say a given person is working, we'd need the predicate function below:

Now to say that everyone is working, we'll write the following quantification expression:

This is read as 'For every student ::x::, ::x:: is working.' This is equivalent to ::\text{W(Alex)} \wedge \text{W(Sandra)} \wedge \text{W(Joe)}:: which says that 'Alex is working, Sandra is working and Joe is working.'

Sometimes, we could directly specify the universe of discourse next to the universal quantifier. For instance, suppose we ought to express the following:

Taking the following predicate functions,

::E(x):: : ::x:: is even
::O(x):: : ::x:: is odd

...we could write.

Note that the part ' ::\forall x \space \epsilon \space \Z::' says that 'for every element ::x:: in the set ::\Z::'.

Often times, it might be cumbersome to separately mention the universe of discourse, such as when working with assertions in mathematics. In such cases, we're better off at inlining the domain within the quantification expression.

The universal quantification operation produces a proposition. That is, given a domain for ::x:: and a predicate function ::P::, ::\forall x P(x):: is a proposition.

Universal quantification can be used to express a lot more than we otherwise could in propositional calculus. However, still somethings are left out. For those, we have the existential quantifier.

Suppose you want to notationally express the following:

given the same predicate, and domain of discourse as before.

How would you do so? Well, three items are manageable so let's just go ahead and express the sentence fully.

Here, we're simply saying that either Alex is working or Sandra is working or Joe is working. In any way, there is someone in the class who is working.

The question is can you express this statement using the universal quantifier?

Clearly no!

This is because we are making an assertion regarding at least one person — it might not apply for everyone (though it could!). What else to use?

Well, we use the existential quantifier.

It's denoted using the symbol ::\exists:: (a horizontal reflection of E). It's expressed as follows:

We read this as 'For some ::x::, ::P(x):: holds.'

Let's rewrite the previous sentence 'Someone is working' using an existential quantifier:

Recall that the domain is the set ::\{\text{Alex, Sandra, Joe}\}::, while the predicate function is ::P(x):: : ::x:: is working.

This expression is stating that 'For some person ::x::, that person is working.'

All the syntactic rules that apply to universal quantification also apply to existential quantification. That is, we could inline the domain of discourse ::S:: as shown below:

Let's see how good are we at existentially quantifying statements.

Uptil this point, the quantifications we've seen have been around just one atomic expression i.e. ::P(x)::. Many English sentences can be modeled this way, but when we use connectives in the sentences, then we need to use them in our logical expressions as well to truly capture the semantics of the actual sentences.

Next up, we'll consider a couple of sentences and convert them into quantified logical expressions.

For each of the following sentences, we ought to determine a predicate function and the domain of discourse.