Introduction to Quantifiers and First Order Predicate Logic

Propositional logic treats complete statements such as

$$p:\text{ The number 5 is prime}$$

as single units.

However, many mathematical statements contain variables and describe properties that may hold for some or all objects.

For example:

Every natural number is greater than or equal to zero.

or

There exists a prime number greater than 100.

To represent such statements formally, we use predicate logic, also called first-order logic.

The two most important ideas in predicate logic are:

• Predicates
• Quantifiers

---

Predicates

A predicate is a statement containing one or more variables whose truth value depends on the values assigned to those variables.

For example,

$$P(x): x>5$$

is a predicate.

It is not automatically true or false until a value is assigned to $x$.

If

$$x=8,$$

then

$$P(8): 8>5$$

is true.

If

$$x=3,$$

then

$$P(3): 3>5$$

is false.

Thus, a predicate becomes a proposition after its variables are given specific values or are bound by quantifiers.

---

Domain of Discourse

The domain of discourse, or simply the domain, is the collection of values that a variable is allowed to take.

Consider

$$P(x):x^2=4.$$

If the domain is the set of natural numbers,

$$\mathbb{N},$$

then only

$$x=2$$

satisfies the predicate.

If the domain is the set of integers,

$$\mathbb{Z},$$

then both

$$x=2$$

and

$$x=-2$$

satisfy it.

Therefore, the truth of a quantified statement may depend on the chosen domain.

---

Quantifiers

A quantifier specifies how many elements of a domain satisfy a predicate.

The two fundamental quantifiers are:

1. Universal Quantifier
2. Existential Quantifier

---

Universal Quantifier

The symbol

$$\forall$$

is called the universal quantifier.

It is read as:

for all

or

for every

If $P(x)$ is a predicate, then

$$\forall x\,P(x)$$

means:

$P(x)$ is true for every value of $x$ in the domain.

For example,

$$\forall x\in\mathbb{R},\quad x^2\ge0$$

means:

For every real number $x$, $x^2$ is greater than or equal to zero.

This statement is true.

---

Example

Let

$$P(x):x+0=x.$$

Over the set of real numbers,

$$\forall x\,P(x)$$

means

$$\forall x\in\mathbb{R},\quad x+0=x.$$

Since the statement is true for every real number,

$$\forall x\,P(x)$$

is true.

---

Existential Quantifier

The symbol

$$\exists$$

is called the existential quantifier.

It is read as:

there exists

or

there is at least one

The expression

$$\exists x\,P(x)$$

means:

There exists at least one value of $x$ in the domain for which $P(x)$ is true.

For example,

$$\exists x\in\mathbb{Z},\quad x^2=9$$

means:

There exists an integer whose square is 9.

Since

$$3^2=9$$

and

$$(-3)^2=9,$$

the statement is true.

---

Universal vs Existential Quantifier

Suppose

$$P(x):x>0$$

and the domain is

$$\mathbb{Z}.$$

Then

$$\forall x\,P(x)$$

means:

Every integer is greater than zero.

This is false.

But

$$\exists x\,P(x)$$

means:

There exists an integer greater than zero.

This is true.

Thus,

$$\forall$$

requires the predicate to hold for every element, whereas

$$\exists$$

requires it to hold for at least one element.

---

Truth of Quantified Statements

Universal Statement

A statement of the form

$$\forall x\,P(x)$$

is true only if $P(x)$ is true for every element of the domain.

To show that it is false, we only need to find one value for which $P(x)$ is false.

Such a value is called a counterexample.

---

Example

Consider

$$\forall x\in\mathbb{Z},\quad x^2>x.$$

Take

$$x=0.$$

Then

$$0^2>0$$

becomes

$$0>0,$$

which is false.

Therefore,

$$\forall x\in\mathbb{Z},\quad x^2>x$$

is false.

Here, $x=0$ is a counterexample.

---

Existential Statement

A statement of the form

$$\exists x\,P(x)$$

is true if we can find at least one value for which $P(x)$ is true.

For example,

$$\exists x\in\mathbb{Z},\quad x^2=16$$

is true because

$$x=4$$

satisfies the predicate.

---

Negation of Quantified Statements

The negation of quantified statements is extremely important.

The universal and existential quantifiers change into each other under negation.

---

Negation of Universal Quantifier

The negation of

$$\forall x\,P(x)$$

is

$$\boxed{ \neg(\forall x\,P(x)) \equiv \exists x\,\neg P(x) }$$

In words:

It is not true that $P(x)$ holds for every $x$

means

There exists at least one $x$ for which $P(x)$ does not hold.

---

Example

Consider:

Every student passed the examination.

Let

$$P(x):x\text{ passed the examination}.$$

The statement is

$$\forall x\,P(x).$$

Its negation is

$$\exists x\,\neg P(x).$$

Therefore:

There exists at least one student who did not pass the examination.

Notice that the negation is not:

No student passed.

That would be a much stronger statement.

---

Negation of Existential Quantifier

The negation of

$$\exists x\,P(x)$$

is

$$\boxed{ \neg(\exists x\,P(x)) \equiv \forall x\,\neg P(x) }$$

In words:

There does not exist an $x$ satisfying $P(x)$

means

Every $x$ fails to satisfy $P(x)$.

---

Example

Consider:

There exists a student who scored 100 marks.

Let

$$P(x):x\text{ scored 100 marks}.$$

The statement is

$$\exists x\,P(x).$$

Its negation is

$$\forall x\,\neg P(x).$$

Therefore:

Every student did not score 100 marks.

More naturally:

No student scored 100 marks.

---

Quantifier Negation Laws

The two important laws are

$$\boxed{ \neg(\forall x\,P(x)) \equiv \exists x\,\neg P(x) }$$

and

$$\boxed{ \neg(\exists x\,P(x)) \equiv \forall x\,\neg P(x) }$$

These are similar in spirit to De Morgan's Laws.

---

Translating Statements Using Quantifiers

Quantifiers allow ordinary mathematical or English statements to be written formally.

Suppose the domain is the set of all people.

Let

$$S(x):x\text{ is a student}$$

and

$$H(x):x\text{ is hardworking}.$$

---

Every Student Is Hardworking

The statement

Every student is hardworking.

can be written as

$$\boxed{ \forall x\,(S(x)\rightarrow H(x)) }$$

The implication is important.

We do not write

$$\forall x\,(S(x)\land H(x))$$

because that would mean that every person in the entire domain is both a student and hardworking.

---

Some Student Is Hardworking

The statement

Some student is hardworking.

means that at least one person is both a student and hardworking.

Therefore,

$$\boxed{ \exists x\,(S(x)\land H(x)) }$$

---

No Student Is Hardworking

The statement

No student is hardworking.

can be written as

$$\boxed{ \forall x\,(S(x)\rightarrow\neg H(x)) }$$

or equivalently,

$$\boxed{ \neg\exists x\,(S(x)\land H(x)) }$$

---

Some Student Is Not Hardworking

This statement is represented by

$$\boxed{ \exists x\,(S(x)\land\neg H(x)) }$$

---

Free and Bound Variables

Variables in predicate logic can be either free or bound.

---

Bound Variable

A variable is bound if it lies within the scope of a quantifier.

For example,

$$\forall x\,(x+1>x)$$

Here, $x$ is bound by the universal quantifier.

Similarly, in

$$\exists y\,(y^2=4),$$

the variable $y$ is bound by the existential quantifier.

A formula in which every variable is bound represents a complete proposition with a definite truth value.

---

Free Variable

A variable is free if it is not controlled by any quantifier.

For example,

$$P(x):x>5$$

contains the free variable $x$.

Its truth value cannot be determined until a value of $x$ is specified.

Consider

$$\forall x\,(x+y>0).$$

Here,

• $x$ is bound,
• $y$ is free.

Therefore, the expression still depends on the value of $y$.

---

Scope of a Quantifier

The scope of a quantifier is the part of the formula to which the quantifier applies.

For example,

$$\forall x\,(P(x)\rightarrow Q(x))$$

has the entire expression

$$P(x)\rightarrow Q(x)$$

inside the scope of $\forall x$.

Parentheses are useful for making the scope clear.

For example,

$$\forall x\,(P(x)\lor Q(x))$$

is different in structure from an expression where only one component is quantified.

---

Quantifiers with Logical Connectives

Quantifiers often appear together with implication, conjunction, and disjunction.

Understanding their placement is important.

---

Universal Statements Commonly Use Implication

Suppose

$$P(x):x\text{ is a dog}$$

and

$$Q(x):x\text{ is an animal}.$$

The statement

Every dog is an animal

is represented as

$$\boxed{ \forall x\,(P(x)\rightarrow Q(x)) }$$

---

Existential Statements Commonly Use Conjunction

The statement

There exists a dog that is black

can be represented as

$$\boxed{ \exists x\,(D(x)\land B(x)) }$$

where

$$D(x):x\text{ is a dog}$$

and

$$B(x):x\text{ is black}.$$

This requires one object to satisfy both properties.

---

Useful Equivalences Involving Quantifiers

Some useful logical equivalences are:

$$\forall x\,(P(x)\land Q(x)) \equiv (\forall x\,P(x)) \land (\forall x\,Q(x))$$

This says that every object satisfies both properties exactly when every object satisfies the first property and every object satisfies the second.

Similarly,

$$\exists x\,(P(x)\lor Q(x)) \equiv (\exists x\,P(x)) \lor (\exists x\,Q(x)).$$

However, similar-looking expressions do not always distribute in the same way.

For example,

$$\exists x\,(P(x)\land Q(x))$$

does not generally mean the same thing as

$$(\exists x\,P(x)) \land (\exists x\,Q(x)).$$

The reason is that the two existential statements may be satisfied by different objects.

---

Example

Suppose the domain contains two people:

• Aman is a student but not a teacher.
• Ravi is a teacher but not a student.

Then

$$\exists x\,S(x)$$

is true, and

$$\exists x\,T(x)$$

is also true.

Therefore,

$$(\exists x\,S(x)) \land (\exists x\,T(x))$$

is true.

But

$$\exists x\,(S(x)\land T(x))$$

is false because no single person is both a student and a teacher.

---

Important Quantifier Formulae

The most important identities to remember are

$$\boxed{ \neg(\forall x\,P(x)) \equiv \exists x\,\neg P(x) }$$ $$\boxed{ \neg(\exists x\,P(x)) \equiv \forall x\,\neg P(x) }$$

Also,

$$\boxed{ \forall x\,(P(x)\land Q(x)) \equiv (\forall x\,P(x)) \land (\forall x\,Q(x)) }$$

and

$$\boxed{ \exists x\,(P(x)\lor Q(x)) \equiv (\exists x\,P(x)) \lor (\exists x\,Q(x)) }$$