Predicates and Quantifiers: Logic Explained Simply

A predicate is a statement containing variables, such as P(x): "x is even". Alone it is neither true nor false; it becomes a proposition when you plug in values, like P(4) (true) or P(7) (false). Predicates let logic talk about whole collections of objects.

Quantifiers turn predicates into propositions by saying how many values satisfy them. ∀x P(x) means "P(x) holds for every x", and ∃x P(x) means "P(x) holds for at least one x". Almost every theorem in mathematics is a quantified statement, so reading quantifiers fluently is essential.

Key Concepts

• Predicate P(x): a sentence with a variable; becomes a proposition when x is assigned a value.
• Domain: the set of values x may take; the truth of ∀x P(x) depends on it.
• Universal quantifier ∀: ∀x P(x) is true only if P(x) holds for every x in the domain.
• Existential quantifier ∃: ∃x P(x) is true if P(x) holds for at least one x in the domain.
• Quantifier negation: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x) (negation flips the quantifier).
• Nested quantifiers: in ∀x ∃y R(x, y), the order matters; swapping ∀ and ∃ changes the meaning.

How It Works

Evaluate a quantified statement against its domain step by step:

1. Fix the domain first: "∀x (x² ≥ 0)" is true over reals but means something different elsewhere.
2. For ∀x P(x), check every element: one counterexample makes the whole statement false.
3. For ∃x P(x), find one witness: a single example makes it true.
4. To negate, flip each quantifier (∀ becomes ∃ and vice versa) and negate the inner predicate.
5. Read nested quantifiers left to right: ∀x ∃y (x + y = 0) lets y depend on x, but ∃y ∀x (x + y = 0) demands one y for all x, which is false.

Worked Example

Take the domain {1, 2, 3} and the predicate P(x): "x² < 10". Evaluate three statements:

• ∀x P(x): 1, 4, 9 are all < 10, so true.
• ∃x (x² > 8): x = 3 gives 9 > 8, so true.
• ¬∀x (x < 3) becomes ∃x (x ≥ 3); x = 3 works, so the negation is true and the original is false.

Change the domain to {1, 2, 3, 4}: ∀x P(x) becomes false since 4² = 16. Same predicate, different domain, different answer.

Common Misconceptions

• "To disprove ∀x P(x) you must show P(x) is always false." No: one counterexample destroys a universal statement. You never need to check the rest.
• "∃x P(x) means P(x) is true for most x." It means at least one. Exactly one witness is enough, and the other values can all fail.
• "∀x ∃y and ∃y ∀x say the same thing." They do not: "everyone has someone who loves them" differs from "someone loves everyone".

Real-World Applications

• Theorem statements: "the sum of two even numbers is even" is ∀m ∀n ((even(m) ∧ even(n)) → even(m + n)). Reading mathematics is reading quantifiers.
• Database queries: "find customers who bought every product" is a universal query; "find a customer who bought something" is existential.
• Program specifications: "this function returns a sorted array for all inputs" is a universal claim tested by hunting counterexamples.

Predicates are statements with blanks; quantifiers fill them: ∀ demands the predicate hold for everything in the domain, ∃ asks for one witness, negation flips the quantifier, and nested order matters. Disprove universals with one counterexample and prove existentials with one example.