Determine truth of quantified statements over a domain - Discrete Math

SECTION 1

Historical Context & Motivation

Mathematics has long grappled with the challenge of making precise statements about collections of objects. Ancient Greek mathematicians such as Euclid routinely made claims like "all prime numbers greater than 2 are odd," but the logical machinery to formalize and rigorously evaluate such assertions did not exist for millennia. The development of predicate logic and its quantifiers — the universal quantifier ∀ and the existential quantifier ∃ — gave mathematicians a precise language for expressing and verifying statements about every element, or at least one element, within a specified domain of discourse. Understanding how to determine the truth of such quantified statements is foundational to proof writing, algorithm verification, and the theoretical underpinnings of computer science.

~300 BCE • Aristotle's Syllogistic Logic

Aristotle introduced syllogisms that captured universal ("All A are B") and particular ("Some A are B") claims, laying the philosophical groundwork for quantification.

1879 • Frege's Begriffsschrift

Gottlob Frege published his Begriffsschrift, introducing the first formal system of predicate logic with explicit quantifier notation, enabling rigorous reasoning about variables ranging over domains.

1910–1913 • Principia Mathematica

Bertrand Russell and Alfred North Whitehead refined predicate logic in Principia Mathematica, standardizing the treatment of quantifiers and domains that is used in modern mathematics.

1930 • Gödel's Completeness Theorem

Kurt Gödel proved that every logically valid formula of first-order predicate logic is provable, confirming that the quantifier-based framework is complete for first-order reasoning.

The central question this lesson addresses is deceptively simple: given a quantified statement such as ∀x P(x) or ∃x P(x) and a specific domain D, how do we systematically determine whether the statement is true or false? The answer requires careful attention to the interplay between the predicate, the quantifier, and every element of the domain — a skill that is indispensable for constructing and evaluating mathematical proofs.

SECTION 2

Core Principles & Definitions

Before evaluating quantified statements, we must establish precise definitions for the key components. A predicate is a statement template P(x) that becomes a proposition once a specific value from the domain is substituted for x. The domain of discourse (often denoted D) is the set of all values that the variable x is allowed to take. A quantifier binds the variable to the domain and specifies how many elements must satisfy the predicate for the overall statement to be true. The two fundamental quantifiers are the universal quantifier ∀ ("for all") and the existential quantifier ∃ ("there exists").

Universal Quantification ∀x P(x)

True when P(x) holds for every element in the domain D. A single counterexample makes it false.

Existential Quantification ∃x P(x)

True when P(x) holds for at least one element in D. It is false only when no element satisfies P.

Domain of Discourse D

The universe of values x may take. Changing the domain can change the truth value of a quantified statement even when the predicate remains the same.

Counterexample

An element c ∈ D such that P(c) is false. A single counterexample disproves ∀x P(x). For ∃x P(x), you must show no witness exists to disprove it.

Witness

An element w ∈ D such that P(w) is true. Producing one witness proves ∃x P(x). For ∀x P(x), every element must be a witness.

✦

KEY TAKEAWAY

Think of the universal quantifier ∀ as a quality-control inspector on an assembly line: the statement passes only if every single item meets the standard. The existential quantifier ∃ is like a search warrant: you only need to find one piece of evidence to confirm the claim. The domain is the factory floor — or the jurisdiction — that determines which items get checked.

SECTION 3

Visual Explanation

The following diagram illustrates how the truth value of a quantified statement depends on checking the predicate against each element in the domain. On the left, a universal statement is shown: every element must satisfy the predicate for the statement to be true. On the right, an existential statement requires only one satisfying element. Observe how the domain D = {1, 2, 3, 4, 5} is tested against the predicate P(x): "x is even."

Left panel: ∀x P(x) is FALSE because elements 1, 3, and 5 are counterexamples (P(x) fails). Right panel: ∃x P(x) is TRUE because 2 is a witness (P(2) holds). Notice that finding even one failing element suffices to disprove the universal, while finding even one satisfying element suffices to prove the existential.

The key insight from this visualization is that evaluating ∀x P(x) over a finite domain is equivalent to computing the conjunction P(d₁) ∧ P(d₂) ∧ … ∧ P(dₙ), while evaluating ∃x P(x) is equivalent to computing the disjunction P(d₁) ∨ P(d₂) ∨ … ∨ P(dₙ). This connection between quantifiers and logical connectives is fundamental: a universal quantifier generalizes AND across the entire domain, and an existential quantifier generalizes OR.

SECTION 4

Mathematical Framework

We now formalize the evaluation procedure. Let D = {d₁, d₂, …, dₙ} be a finite domain of discourse and let P(x) be a predicate defined on D. The truth values of the two basic quantified statements are determined as follows.

UNIVERSAL QUANTIFICATION

∀x ∈ D, P(x) ≡ P(d₁) ∧ P(d₂) ∧ … ∧ P(dₙ)

True if and only if P evaluates to true for every element dᵢ in D. If any P(dᵢ) is false, the entire conjunction collapses to false.

EXISTENTIAL QUANTIFICATION

∃x ∈ D, P(x) ≡ P(d₁) ∨ P(d₂) ∨ … ∨ P(dₙ)

True if and only if P evaluates to true for at least one element dᵢ in D. The disjunction is false only when every P(dᵢ) is false.

NEGATION OF QUANTIFIERS (DE MORGAN'S LAWS FOR QUANTIFIERS)

¬(∀x P(x)) ≡ ∃x ¬P(x) ¬(∃x P(x)) ≡ ∀x ¬P(x)

Negating a universal statement yields an existential statement with the predicate negated, and vice versa. This is the quantifier analogue of De Morgan's laws for propositional logic.

VACUOUS TRUTH

If D = ∅, then ∀x ∈ D, P(x) is TRUE and ∃x ∈ D, P(x) is FALSE

Over the empty domain, the universal statement is vacuously true (there are no counterexamples) and the existential statement is false (there are no witnesses). This edge case is often tested in examinations.

For nested quantifiers, the order matters critically. The statement ∀x ∃y P(x, y) asserts that for every x there is some y (possibly depending on x) such that P(x, y) holds, whereas ∃y ∀x P(x, y) asserts that a single y works for all x simultaneously. In general, ∀x ∃y P(x, y) does not imply ∃y ∀x P(x, y), though the reverse implication always holds. Evaluating nested quantifiers over a finite domain amounts to nested loops: the outer quantifier determines the outer loop and the inner quantifier determines the inner loop.

SECTION 5

How the Domain Changes Truth Values

One of the most important lessons about quantified statements is that the same predicate with the same quantifier can yield different truth values depending on the domain. Consider the predicate P(x): "x² ≥ x." Over the domain D₁ = {2, 3, 4}, we have P(2) = T, P(3) = T, P(4) = T, so ∀x P(x) is true. But over D₂ = {0.5, 1, 2}, we have P(0.5) = F because 0.25 < 0.5, so ∀x P(x) is false. The diagram below systematically illustrates how the domain affects truth value for a single predicate.

Three domains tested against the same universally quantified predicate P(x): "x² ≥ x." Over D₁ = {2, 3, 4} the statement is true; over D₂ = {0.5, 1, 2} it is false (counterexample at x = 0.5); over the empty domain D₃ = ∅ it is vacuously true.

Domain D	∀x P(x)	∃x P(x)	Reason
{2, 3, 4}	TRUE	TRUE	All elements satisfy x² ≥ x
{0.5, 1, 2}	FALSE	TRUE	Counterexample: 0.5² = 0.25 < 0.5; but 1 and 2 are witnesses
{0.1, 0.3, 0.7}	FALSE	FALSE	No element satisfies x² ≥ x (all squares are smaller)
∅ (empty)	TRUE (vacuous)	FALSE	No elements to check; empty conjunction is true, empty disjunction is false

Truth values of ∀x P(x) and ∃x P(x) for P(x): "x² ≥ x" under various domains

SECTION 6

Worked Example

Let us work through a complete example involving nested quantifiers. Consider the domain D = {1, 2, 3} and the predicate Q(x, y): "x + y = 4." Determine the truth values of (a) ∀x ∃y Q(x, y), (b) ∃x ∀y Q(x, y), and (c) ∃x ∃y Q(x, y).

Evaluating Nested Quantifiers over D = {1, 2, 3}

1
Step 1 — Build the Truth Table for Q(x, y)

Evaluate Q(x, y) = "x + y = 4" for all combinations. Q(1,1)=F, Q(1,2)=F, Q(1,3)=T (since 1+3=4). Q(2,1)=F, Q(2,2)=T (since 2+2=4), Q(2,3)=F. Q(3,1)=T (since 3+1=4), Q(3,2)=F, Q(3,3)=F.

Q is true at exactly three pairs: (1,3), (2,2), (3,1).
2
Step 2 — Evaluate ∀x ∃y Q(x, y)

For each x ∈ {1,2,3}, check whether there exists at least one y such that Q(x,y) is true. For x=1: Q(1,3)=T, so ∃y Q(1,y) is true. For x=2: Q(2,2)=T, so ∃y Q(2,y) is true. For x=3: Q(3,1)=T, so ∃y Q(3,y) is true. Since ∃y Q(x,y) is true for every x, the universal quantifier is satisfied.

∀x ∃y Q(x, y) is TRUE.
3
Step 3 — Evaluate ∃x ∀y Q(x, y)

Now we ask: is there a single x such that Q(x,y) is true for ALL y ∈ {1,2,3}? For x=1: Q(1,1)=F, so ∀y Q(1,y) is already false. For x=2: Q(2,1)=F, so ∀y Q(2,y) is false. For x=3: Q(3,2)=F, so ∀y Q(3,y) is false. No single x satisfies the predicate for every y.

∃x ∀y Q(x, y) is FALSE.
4
Step 4 — Evaluate ∃x ∃y Q(x, y)

We need at least one pair (x, y) such that Q(x,y) is true. From Step 1, Q(1,3)=T suffices as a witness pair.

∃x ∃y Q(x, y) is TRUE.
5
Step 5 — Reflect on Quantifier Order

This example demonstrates a critical point: ∀x ∃y Q(x,y) can be true while ∃x ∀y Q(x,y) is false. The universal-then-existential version allows y to depend on x (a different partner for each x), whereas the existential-then-universal version demands a single x that works with all y simultaneously. Swapping quantifier order does not preserve truth value in general.

SECTION 7

Strategies for Proving and Disproving

Determining the truth of quantified statements requires different strategies depending on the quantifier and whether you expect the statement to be true or false. The table below summarizes the four canonical scenarios and the proof strategy each demands.

Goal	Strategy	What You Must Show
Prove ∀x P(x)	Exhaustive check (finite D) or universal generalization (arbitrary element proof)	P(d) is true for every d ∈ D. For infinite domains, take an arbitrary d and show P(d) follows from its membership in D alone.
Disprove ∀x P(x)	Counterexample	Exhibit a single element c ∈ D with P(c) false. This suffices because ¬(∀x P(x)) ≡ ∃x ¬P(x).
Prove ∃x P(x)	Constructive witness	Exhibit a specific element w ∈ D and verify P(w) is true. Alternatively, derive existence indirectly.
Disprove ∃x P(x)	Exhaustive refutation or universal proof of ¬P	Show ¬P(d) for every d ∈ D. This works because ¬(∃x P(x)) ≡ ∀x ¬P(x).

Four canonical scenarios for evaluating quantified statements

✦

KEY TAKEAWAY

The asymmetry between proving and disproving is a direct consequence of the quantifier-connective correspondence. Disproving a universal claim is "easy" — one counterexample suffices — much like a single bug proving a program is not correct. Disproving an existential claim is "hard" — you must show exhaustively that no witness exists — much like proving a program is correct under all inputs. This asymmetry is precisely why the fields of testing (finding bugs) and formal verification (proving correctness) require fundamentally different approaches.

SECTION 8

Connection to Infinite Domains & Advanced Theory

Over finite domains, determining the truth of a quantified statement is always decidable: you can check each element one by one. The situation changes dramatically over infinite domains such as ℤ, ℝ, or the set of all strings over an alphabet. You can no longer enumerate every element, so the conjunction/disjunction expansion becomes an infinite expression. To prove ∀x P(x) over ℤ, you must reason about an arbitrary integer — often using techniques like mathematical induction, direct proof, or proof by contradiction. To prove ∃x P(x), you must either construct a witness or use non-constructive methods (such as the pigeonhole principle or proof by contradiction).

Aspect	Finite Domain	Infinite Domain
Evaluating ∀x P(x)	Check P(d) for every d ∈ D; finite conjunction	Requires a general proof (induction, arbitrary element, etc.)
Evaluating ∃x P(x)	Search for a witness; finite disjunction	Construct a witness or use non-constructive existence proof
Decidability	Always decidable (mechanical procedure terminates)	Generally undecidable; depends on the theory (e.g., Presburger arithmetic is decidable, Peano arithmetic is not)
Negation	De Morgan's for quantifiers works identically	De Morgan's for quantifiers works identically
Computational perspective	Equivalent to nested for-loops over arrays	Relates to the halting problem and computability theory

Finite vs. infinite domain evaluation

As you advance into courses on computability, model theory, and set theory, the interplay between quantifier depth and decidability becomes a central theme. For now, the finite-domain case provides the essential intuition: the universal quantifier is a large AND, the existential quantifier is a large OR, the domain determines which elements are tested, and negation swaps one quantifier for the other while negating the predicate.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why ∀x P(x) is true over the empty domain D = ∅ for any predicate P. Why is ∃x P(x) false over the same domain?

Show answer

The statement ∀x P(x) is logically equivalent to the conjunction P(d₁) ∧ P(d₂) ∧ … ∧ P(dₙ). When D = ∅, this is an empty conjunction, which by convention evaluates to true — there is no element that can serve as a counterexample. Conversely, ∃x P(x) is equivalent to an empty disjunction P(d₁) ∨ … ∨ P(dₙ) with zero disjuncts, which evaluates to false because there is no element to serve as a witness. This is consistent with the De Morgan-like relationship: ¬(∀x P(x)) ≡ ∃x ¬P(x) is false (since the existential over the empty domain is false), which confirms ∀x P(x) is true.

Question 2: BASIC CALCULATION

Let D = {−2, −1, 0, 1, 2} and P(x): "x² < 5." Determine the truth values of ∀x P(x) and ∃x P(x).

Show answer

Evaluate P for each element: P(−2): (−2)² = 4 < 5, true. P(−1): (−1)² = 1 < 5, true. P(0): 0² = 0 < 5, true. P(1): 1² = 1 < 5, true. P(2): 2² = 4 < 5, true. Since P(x) is true for every element, the conjunction T ∧ T ∧ T ∧ T ∧ T = T. Therefore ∀x P(x) is TRUE. Since the universal is true, the existential ∃x P(x) is also TRUE (if all elements satisfy the predicate, at least one certainly does).

Question 3: INTERMEDIATE

Let D = {1, 2, 3, 4, 5, 6} and R(x, y): "x divides y evenly (y mod x = 0)." Determine the truth values of: (a) ∀x ∃y R(x, y), (b) ∃x ∀y R(x, y), and (c) ∀x ∀y R(x, y).

Show answer

(a) ∀x ∃y R(x, y): For each x, does there exist a y it divides? x=1 divides every y, so choose y=1. x=2 divides y=2. x=3 divides y=3. x=4 divides y=4. x=5 divides y=5. x=6 divides y=6. Every x divides at least itself, so this is TRUE. (b) ∃x ∀y R(x, y): Is there an x that divides every y ∈ D? Only x=1 divides 1,2,3,4,5,6, so x=1 is a witness. This is TRUE. (c) ∀x ∀y R(x, y): Does every x divide every y? x=2 does not divide y=3 (3 mod 2 = 1 ≠ 0), giving a counterexample. This is FALSE.

Question 4: APPLIED

A database has a table STUDENTS with columns name and gpa. A query checks the assertion: "Every student has a GPA of at least 2.0." In predicate logic, this is ∀x ∈ STUDENTS, (gpa(x) ≥ 2.0). The database contains the tuples {(Alice, 3.5), (Bob, 1.8), (Carol, 3.9)}. (a) Is the assertion true? (b) Write the negation of this assertion in predicate logic and in plain English. (c) Identify the witness or counterexample.

Show answer

(a) The assertion ∀x (gpa(x) ≥ 2.0) is FALSE because gpa(Bob) = 1.8 < 2.0. (b) The negation is ∃x ∈ STUDENTS, (gpa(x) < 2.0), which in plain English reads: "There exists a student whose GPA is below 2.0." (c) Bob is a counterexample to the universal claim and simultaneously a witness for the negated existential claim. This illustrates a practical connection: database integrity constraints are universally quantified assertions, and violations are found by searching for counterexamples — which is exactly what a SQL WHERE clause does when checking constraint violations.

Question 5: CRITICAL THINKING

Let D = ℤ⁺ (positive integers). Consider the statement S: ∀x ∃y (y > x ∧ y is prime). Argue whether S is true or false. Then consider S': ∃y ∀x (y > x ∧ y is prime). Argue whether S' is true or false, and explain why the two statements have different truth values despite containing the same predicate and quantifiers.

Show answer

S is TRUE by Euclid's theorem on the infinitude of primes: for any positive integer x, there exists a prime p > x. In other words, there is always a larger prime, so the existential is satisfied for every x — the value of y (the prime) may depend on x. S' is FALSE because it demands a single prime y that is greater than every positive integer x simultaneously. No such y exists: given any fixed y, choose x = y and the condition y > x fails. The key difference is quantifier scope: in S, the existential ∃y is inside the scope of ∀x, allowing y to vary with x. In S', the existential ∃y is outside, fixing y before x is chosen. This demonstrates that ∀x ∃y P(x,y) does not imply ∃y ∀x P(x,y) in general — the former allows a functional dependency of y on x, while the latter requires a uniform witness.

SUMMARY

Lesson Summary

Summary

To determine the truth of a quantified statement, you must consider three components: the quantifier (∀ or ∃), the predicate P(x), and the domain of discourse D. A universally quantified statement ∀x P(x) is true precisely when every element of D satisfies P — equivalently, when the conjunction P(d₁) ∧ P(d₂) ∧ … ∧ P(dₙ) evaluates to true. An existentially quantified statement ∃x P(x) is true when at least one element of D satisfies P — the disjunction P(d₁) ∨ … ∨ P(dₙ) evaluates to true.

Changing the domain can alter truth values even when the predicate and quantifier remain fixed. Negation swaps quantifiers: ¬(∀x P(x)) ≡ ∃x ¬P(x) and ¬(∃x P(x)) ≡ ∀x ¬P(x). For nested quantifiers, order matters: ∀x ∃y P(x,y) allows y to depend on x, whereas ∃y ∀x P(x,y) demands a single y for all x. To disprove a universal, provide a counterexample; to prove an existential, provide a witness. Over the empty domain, universal statements are vacuously true and existential statements are false. These principles form the bedrock for proof construction throughout mathematics and computer science.