Quantifiers and Negation of Quantified Statements

---

Quantifiers and Negation of Quantified Statements

---

1. Quantifiers

Quantifiers are symbols used in predicate logic to express the quantity of elements in a domain for which a propositional function is true. They convert propositional functions into propositions.

There are two main types:

---

a) Universal Quantifier ( ∀ )

Denoted as:

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

Read as: “For all $x$, $P(x)$ is true”

• This statement is true if $P(x)$ is true for every $x$ in the domain.
• It is false if there is at least one value of $x$ for which $P(x)$ is false.

Example:
Let $P(x): x + 1 > x$, over domain $\mathbb{Z}$
Then $\forall x \, P(x)$: True

---

b) Existential Quantifier ( ∃ )

Denoted as:

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

Read as: “There exists an $x$ such that $P(x)$ is true”

• This statement is true if there is at least one value of $x$ in the domain for which $P(x)$ is true.
• It is false if $P(x)$ is false for every value of $x$.

Example:
Let $Q(x): x^2 = 16$, over domain $\mathbb{Z}$
Then $\exists x \, Q(x)$: True (since $x = 4$ or $x = -4$ work)

---

2. Negation of Quantified Statements

To negate quantified statements, you switch the quantifier and negate the predicate.

---

a) Negation of Universal Quantifier

$$\neg (\forall x \, P(x)) \equiv \exists x \, \neg P(x)$$

Meaning: "It is not true that P(x) is true for all x"
⇨ "There exists at least one x for which P(x) is false"

---

b) Negation of Existential Quantifier

$$\neg (\exists x \, P(x)) \equiv \forall x \, \neg P(x)$$

Meaning: "It is not true that there exists an x for which P(x) is true"
⇨ "For every x, P(x) is false"

---

3. Examples of Negating Quantified Statements

Example 1:

Statement:

$$\forall x \in \mathbb{N}, \ x + 1 > x$$

Negation:

$$\exists x \in \mathbb{N} \text{ such that } x + 1 \leq x$$

---

Example 2:

Statement:

$$\exists x \in \mathbb{Z}, \ x^2 = -1$$

Negation:

$$\forall x \in \mathbb{Z}, \ x^2 \neq -1$$

This negated statement is true because no integer squared gives −1.

---

Example 3 (Verbal Form):

Original: “All students passed the exam.”
Negation: “Some students did not pass the exam.”

Original: “There exists a number that is both even and prime.”
Negation: “No number is both even and prime.”

---

4. Quantifier Order Matters

Changing the order of quantifiers changes the meaning.

Example:

• $\forall x \, \exists y \, (x < y)$: For every $x$, there is a $y$ greater than $x$ (True in $\mathbb{R}$)
• $\exists y \, \forall x \, (x < y)$: There is a single $y$ that is greater than all $x$ (False in $\mathbb{R}$)

---