A proposition is a statement that is simply true or false: "5 is prime" (T). A predicate is a proposition that contains a variable: P(x) = "x is prime". It becomes a proposition when x is substituted.
Domain matters. ∀x (x > 0) is False over the integers (negative integers exist) but True over the positive integers.
Negating Quantifiers — De Morgan for Predicates
¬(∀x P(x)) ≡ ∃x ¬P(x) Not every x satisfies P ≡ some x fails P
¬(∃x P(x)) ≡ ∀x ¬P(x) No x satisfies P ≡ every x fails P
Original: ∀x (x² ≥ 0) over the reals.
Negate: ∃x (x² < 0). This is False — no real square is negative.
Conclusion: the original statement is True (its negation is False).
Worked Example
Let the domain be all students in CS 121. Let P(x) = "x passed the final exam".
∀x P(x) → Every student passed.
∃x P(x) → At least one student passed.
∀x ¬P(x) → No student passed.
¬(∀x P(x)) ≡ ∃x ¬P(x) → Some student did not pass.
Practice Problems
1. Negate: ∀x ∃y (x + y = 0) over the integers.
∃x ∀y (x + y ≠ 0)
"There is some integer x such that no integer y satisfies x + y = 0."
(The original is True; the negation is therefore False.)
2. Is ∃x (x² = 2) true over the rationals? Over the reals?
Over the rationals: False. √2 is irrational; no rational number squares to 2.
Over the reals: True. x = √2 ≈ 1.414... is a real number.
Knowledge Check
P(x) = 'x is even'. P(7) is
7 is odd, not even.
Correct — 7 is odd, so P(7) is False.
P(7) is a proposition; it has a definite truth value.
A proposition is either True or False, never both.
Recap: substitute the value — P(7) = '7 is even' = False.
∀x (x > 0) over the integers is
Negative integers and zero exist.
Correct — a single counterexample (e.g., x = −1) disproves a universal statement.
The domain is stated as the integers.
'Most' is not 'all'; universal means every single element.
Recap: to disprove ∀x P(x), find ONE counterexample. To prove it, you must show P holds for every element in the domain.
The negation of ∀x P(x) is
That means 'no x satisfies P' — much stronger than the negation.
Correct — not-all means at-least-one-fails.
That's just rewriting the original negation symbol; it needs to be simplified.
That's 'some x satisfies P' — unrelated to the negation.
Recap: De Morgan for quantifiers — ¬(∀x P) ≡ ∃x ¬P. Push the negation in and flip the quantifier.
The domain of a quantifier
The domain can be any set.
Correct — the truth of a quantified statement depends entirely on the domain.
Quantifiers work over infinite domains (integers, reals, etc.).
Domain is crucial — ∀x (x > 0) is False over integers but True over positive integers.
Recap: always specify the domain. The same statement can be True over one domain and False over another.
∃x (x² = −1) is true over
No real number squares to −1.
Same reason — no integer squares to −1.
Correct — i² = −1, where i is the imaginary unit.
It is true over the complex numbers.
Recap: ∃x (x² = −1) — False over reals/integers, True over complexes (x = i or x = −i).