Predicates and Quantifiers in Discrete Mathematics

---

---

Predicates and Quantifiers are used to build logical expressions involving variables. Predicates help in making statements about objects, while quantifiers specify the scope of these statements. Together, they allow mathematicians to express ideas about groups of objects rather than just individual elements.

In this chapter, we will touch upon the basics of predicates and quantifiers, explain their types, and provide examples to see their use in mathematical reasoning. We will also understand how predicates are different from statements and how quantifiers modify their meanings.

Predicates in Discrete Mathematics

We know the idea of predicate a little. A predicate is a logical expression that contains variables and becomes a statement when specific values are substituted for those variables. So predicates describe properties or conditions that elements of a set can satisfy.

Example of a Predicate

Consider we have a predicate P(x) that states, "x is a prime number".

• If we replace x with 2, the predicate P(2) becomes the statement, "2 is a prime number" which is True.
• Similarly, if we substitute x = 4, the predicate P(4) becomes "4 is a prime number" which is False.

In both the cases, by substituting specific values for x, the predicate becomes a definite statement that can be either True or False.

Difference between a Predicate and a Statement

Predicates and Statements are quite similar and that’s why they become confusing. A statement is a sentence that is either True or False. However, a predicate has a variable and is not a statement until the variable is replaced with a specific value. For example:

• Predicate − "n is a prime number."
• Statement − "7 is a prime number."

Without assigning a value to the variable n, the predicate is incomplete and does not hold a truth value. Only when we provide a value for n, like in the case of "7 is a prime number," does the predicate become a true or false statement.

Quantifiers in Discrete Mathematics

The next part is the quantifiers. These are symbols or words that define the extent to which a predicate is true for a set of elements.

In mathematics, we use two main types of quantifiers:

• Universal quantifier (denoted by ∀), meaning "for all."
• Existential quantifier (denoted by ∃), meaning "there exists."

Universal Quantifier ( ∀ )

From the name itself we can understand this. The universal quantifier is used when we want to declare that a predicate is true for every possible value of a variable. It is read as "for all" or "for every."

Let us understand with examples. Consider the following statement −

$$\mathrm{\forall x \ (x \:\geq\: 0)}$$

It means, "For all values of x, x is greater than or equal to zero." In the domain of natural numbers (0, 1, 2, ...), this statement is True.

Existential Quantifier ( ∃ )

Another type of quantifier is the existential quantifier. It is used when we want to say that there is at least one value of a variable for which a predicate is true. It is read as "there exists" or "there is."

For example, consider the following statement −

$$\mathrm{\exists x \ (x \:\lt\: 0)}$$

This means "There exists an x such that x is less than zero." In the domain of natural numbers, this statement is false because no natural number is less than zero. However, in the domain of real numbers, this statement is true.

Combining the Quantifiers

We can combine these two quantifiers for better use cases. Let us look at how this works by checking the following examples –

Example of Universal and Existential Quantifiers

Consider the statement −

$$\mathrm{\forall x \ \exists y \ (y \:\lt\: x)}$$

This reads, "For every x, there exists a y such that y is less than x."

If we are working within the domain of natural numbers (0, 1, 2, ...), this statement is false because for x = 0, there is no natural number y such that y < 0. However, if we change the domain to real numbers, this statement becomes true, since for any real number x, there exists a real number y that is smaller.

Example of Nested Quantifiers

Now, let us look at a more complex statement with nested quantifiers −

$$\mathrm{\exists x \ \forall y \ (y \:\geq\: x)}$$

This reads, "There exists an x such that for all y, y is greater than or equal to x."

In the domain of natural numbers, this statement is true because the number x = 0 satisfies this condition. No matter which number y we choose, it will always be greater than or equal to 0.

Negation of Quantifiers

When we negate quantified statements, the type of quantifier changes. The negation of a universal quantifier becomes an existential quantifier, and the negation of an existential quantifier becomes a universal quantifier.

Following are the rules of negation −

• ¬∀xP(x) is equivalent to ∃x¬P(x), meaning "It is not true that for all x, P(x) is true" is the same as "There exists an x such that P(x) is false."
• ¬∃xP(x) is equivalent to ∀x¬P(x), meaning "There does not exist an x such that P(x) is true" is the same as "For all x, P(x) is false."

Example of Negating a Universal Quantifier

Consider the following statement −

$$\mathrm{\forall x \ (x \:\geq\: 0)}$$

The negation of this statement would be −

$$\mathrm{\neg\: \forall x \ (x \:\geq\: 0),\: \text{ which is equivalent to } \exists x \ (x \:\lt\: 0)}$$

This negation reads, "There exists an x such that x < 0" In the domain of real numbers, this is true, as there are negative numbers.

Example of Negating an Existential Quantifier

Consider the following statement −

$$\mathrm{\exists x \ (x \:>\: 10)}$$

The negation of this statement would be −

$$\mathrm{\neg\: \exists x \ (x \:>\: 10),\: \text{ which is equivalent to } \forall x \ (x \:\leq\: 10)}$$

This negation reads, "For all x, x is less than or equal to 10." If we are in the domain of natural numbers, this is false because numbers greater than 10 exist.

Implicit Quantifiers

In some cases, the quantifiers in a sentence are implied rather than explicitly stated. For example, when we say −

"If a shape is a square, then it is a rectangle"

Although this is not written with quantifiers, it is understood that we mean −

"For all shapes, if the shape is a square, then it is a rectangle"

Here, the universal quantifier "for all shapes" is implicit.

Similarly, when we use predicates, it is often assumed that the variables are universally quantified unless otherwise stated. For instance, when we define a predicate P(n) to mean "n is prime," we assume that n is universally quantified.

Using Predicates and Quantifiers in Proofs

Predicates and quantifiers are often used in formal proofs to express general statements about numbers, sets, or other mathematical objects. The combination of these tools allows for precision and clarity in mathematical reasoning.

Conclusion

In this chapter, we explained the importance of predicates and quantifiers in discrete mathematics. Predicates allow us to describe the properties of objects, while quantifiers help define the scope of these descriptions.

We presented the concept of two main quantifiers, universal and existential. Additionally, we understood how to negate quantified statements and saw how implicit quantifiers work in certain cases.