STEP-BY-STEP LESSON · §3.2
Predicates and Quantified Statements II
Negate quantifiers while preserving precise meaning.
Before you begin
Predicates and Quantified Statements I
P(x) is a condition whose truth depends on x. For P(x): x>2, specify allowed values first.
D={1,2,3}∀x∈D P(x) is true when the condition holds for every element of D. One violating element refutes it.
∀x∈D: x>2
∃x∈D P(x) needs at least one witness. For finite D, falsity can be established by checking every element.
∃x∈D: x>2
Symbols
- ¬∀
- not for all
- ¬∃
- there does not exist
Definitions and notation for this topic
De Morgan’s laws for propositions
¬(p∧q)≡¬p∨¬q; ¬(p∨q)≡¬p∧¬q
For classical propositions p and q, negating a conjunction gives a disjunction of the negations, and negating a disjunction gives a conjunction of the negations.
Negate the complete parenthesized expression and each component, including the strictness of inequalities. ≡ says the two formulas agree under every truth assignment.
Separate glossary example
For real x, ¬(x>0 ∧ x<1) is equivalent to x≤0 ∨ x≥1.
Negating quantifiers
¬(∀x∈D P(x)) ≡ ∃x∈D ¬P(x); ¬(∃x∈D P(x)) ≡ ∀x∈D ¬P(x)
Negating a quantified statement switches ∀ and ∃ and negates the complete predicate in their scope. Keep the same domain.
With several quantifiers, apply the rule successively without reordering variables. Negate the whole predicate: ¬(P∧Q) becomes ¬P∨¬Q, not ¬P∧¬Q.
Separate glossary example
¬(∀x∈ℤ (x≥0)) ≡ ∃x∈ℤ (x<0). Also ¬(∃x∈ℤ (x²=−1)) ≡ ∀x∈ℤ (x²≠−1).
¬(∀x P(x)) ≡ ∃x ¬P(x)
Step by step
Step 1 / 6
Not all
Negating “all have the property” means “some object lacks it”. It does not mean that all lack it.
¬∀x∈D P(x) ≡ ∃x∈D ¬P(x)
One exception is enough to violate an all-object requirement.
Worked example
Over integers, negate: every n divisible by 6 is divisible by 3.
- Write the structure as ∀n∈ℤ (6|n → 3|n), where d|n means d divides n.
- Move negation through ∀: ∃n∈ℤ ¬(6|n → 3|n). The domain stays integers.
- Negate the implication: ∃n∈ℤ (6|n ∧ 3∤n). It would require a multiple of 6 that is not a multiple of 3; none exists, so the negation is false.
Negate without changing the question
Negation changes 'every' to 'some' and 'some' to 'every', then negates the remaining condition. Keep the original domains and variable order. Negating an implication gives P and not Q. With several quantifiers, read choices from left to right: a later existential choice may depend on earlier universal choices.
Worked example
Negate: every integer n with n > 0 has n² > n. Then decide whether the negation has a witness.
Write the whole original claim before negating it.
∀n ∈ ℤ (n > 0 → n² > n)
Why: The condition n > 0 is the hypothesis, not a change from integers to real numbers.
Move the negation through the universal quantifier.
¬∀n ∈ ℤ (n > 0 → n² > n) ≡ ∃n ∈ ℤ ¬(n > 0 → n² > n)
Why: One failing permitted integer is enough to refute a claim about every integer.
Negate the conditional, including the inequality boundary.
∃n ∈ ℤ (n > 0 ∧ n² ≤ n)
Why: The negation of > is ≤. It is not another implication and does not say every positive integer fails.
Choose n = 1 and verify both parts.
1 > 0 ∧ 1² ≤ 1
Why: The witness is an integer, the hypothesis holds, and the strict conclusion fails. Therefore the original universal claim is false.
Self-review goal: Negate one quantifier at a time. Explain why ∀x ∈ ℤ ∃y ∈ ℤ (x+y=0) allows y = −x, whereas ∃y ∈ ℤ ∀x ∈ ℤ (x+y=0) would require one fixed y; x=0 and x=1 already demand different values.
Optional self-check
What does ¬∃x∈D: x=5 mean?
Show answer
Every element of D differs from 5.