Predicate Logic - Nested Quantifiers

Quantifiers, as we learned in the previous chapter, are extremely useful in representing numerous mathematical assertions in logic, as well or translating many day-to-day sentences into logical expressions.

However, still there is a wide array of stuff not able to be captured by single, straightforward, quantifiers.

For instance, how to express 'There is some integer ::x::, such that for any integer ::y::, ::x + y = y::', in logic?

We can't just use one quantifier to say this, because the latter part of the sentence makes a quantification itself. What we need is a mixture of quantifications.

This is what this chapter is all about — we aim to learn nested quantifications.

First, what we'll see is how to combine two universal quantifiers together to capture much more numerous stuff in logic including axioms/theorems out there, regarding integers.

Suppose you want to say the following:

Surely one way is as follows:

We universally quantify the latter part of the sentence, which is itself a quantification. Although, this isn't technically invalid, it's once again imprecise.

In logic, our aim is to extract out the semantics (i.e the meaning) of any given sentence to the highest amount of precision, notationally.

The translation above is valid, but misses to extract out the knowledge conveyed in the latter part of the sentence. To fully extract all of it, we can't just rely on one quantification.

Can we?

What we need is double quantification. Let's see how to do it:

Step 1 is to identify the things being quantified in the sentence.

What do you think is being quantified in 'Every student in this class has been enrolled in every course offered at this institute.'?

Well, firstly we see 'every student' which means that we're trying to quantify students. Secondly, we have 'every course', which implies the quantification of courses.

So, the domain of each of the two quanfications is decided.

Step 2 is to construct predicate functions for the underlying sentence. For the sentence above, we just need one predicate.

Can you think why is this the case? Because there is no connective in the sentence.

So the predicate function would just be:

Note a couple of things over here. We've omitted the parts 'in this class' and 'in this institute'. This is because the respective domains we'd be using would take into account all these details.

For example, the domain of ::x:: here would be all students in this class. By that means, when we say that 'for every student ::x::', we are effectively saying that 'all students in this class'. This is just some natural logic in action — certain things are implicity understood.

Alright, time to now state the main expression, given that we have all the prerequisites with us:

We'd read this as 'For every student ::x::, given any course ::y::, ::x:: is enrolled in ::y::.'

Hopefully, not that difficult!

Let's try one more example.

This is a bit more involved compared to the first one, but only as far as the structure of the sentence. Once we understand what's being specified in the sentence, it would just be a matter of seconds before we translate it into a logical expression.

The sentence is saying that given any two positive integers ::x:: and ::y::, their sum is going to be positive.

We can select any integer as ::x:: and any integer as ::y::, and the assertion would hold (if the original sentence is true). In other words, all possible combinations satisfy the stated assertions. The things quantified are integers ::x:: and ::y::, hence we arrive at the following.

The (binary) predicate is straightforward:

The domain for each variable is the set of positive integers i.e. the domain is ::\Z^+::.

Altogether, we arrive at the following expression:

Note that we could just inline the statement given in the predicate function here next to the quantification expression. Often times, doing so is desirable, since mathematical properties can already be expressed succintly as compared to general English sentences, which would otherwise complicate the quantification expression had they been inlined in them, as follows.

But yes, it's not invalid to use predicate functions in expressing simple mathematical assertions — it's just something not required!

In the case above, we did one simplification; that is, we took the domain as the set of positive integers. However, think on what would the logical expression be if we were specifically given the domain as the set of integers.

Sounds like a good task!

Next up in line, we ought to understand the combination of two existential quantifiers.

Given the sentence below, write its equivalent logical expression.

As before, step one is to understand the meaning of the sentence and extract out the objects that are being quantified.

Here, we can easily see that newspapers are being quantified as well as the people in the neighbourhood. The predicate would be:

Blending this function with quantifiers, we get:

This simply says that 'For some newspaper ::x::, there is some person ::y::, such that ::x:: has been delivered to ::y::.'

Note that the statement is not saying that some newspapers have been delivered to only one person in the neighbourhood. Rather, it's saying that there is at least one person who has received the newspapers. Maybe, many of his friends, in the neighbourhood also received some newspapers.

Time for yet another interesting quantifier combination.

How to convert this sentence into the glyphs of mathematical logic? Well, it looks fairly easy!

The statement is simply trying to say that 'for every person ::x:: in this class, that person has an A in some subject ::y::.'

Now, does it look ever easier to convert?

As before, we'll need just one predicate function owing to the fact that there is no connective in the original sentence. This predicate would be:

The domains are also pretty straightforward — for ::x::, we've got all students in the class, while for ::y::, we've got all subjects. Altogether, we get the following:

We'd read this as 'For every student ::x::, there is some subject ::y::, such that ::x:: has an A in ::y::.'

One extremely crucial thing to realise over here is, that unlike with the two quantifier combinations we saw above that used the same quantifier, we can't change the order of quantifiers here. Doing so we'd end up simply expressing a completing different sentence!

Let's see an example...

Below we'll shift the positions of the quantifiers in the expression above, and see what difference does it make.

This statement is sayinig that there is some subject ::y::, such that given any student ::x::, ::x:: has an A in ::y::. This means that all students have an A in the same subject(s). However, the previous sentence said something totally different.

It said that every student has an A in some subject. Every student is strong in some particular subject(s).

But the expression above says that there is some very easy subject (or subjects) in which every single student has aced his/her exam.

Be careful with these quantifications where the inner quantifier is different from the outer one — where you've got a mixture of two different quantifiers!