Negating Universal and Existential Quantifiers

Hello. In the previous lesson, you translated quantified statements while tracking domains, logical connectives, and the order of nested quantifiers. This lesson takes the complementary step: given a statement, we will say exactly what it means for that statement to fail.

Negation is more than attaching the phrase “it is not the case that.” A useful negation must state the opposite claim in a form that can be tested, proved, or disproved. This is especially important in proofs: a false universal assertion fails because of a particular counterexample, while a false existential assertion fails because no possible witness works.

---

The two fundamental rules

Let $P(x)$ be a predicate on a domain $D$. The two rules to know are

$$\neg ((\forall x\in D)P(x))\equiv (\exists x\in D)\neg P(x)$$

and

$$\neg ((\exists x\in D)P(x))\equiv (\forall x\in D)\neg P(x).$$

In words:

• “It is not true that every object has property $P$” means “some object does not have property $P$.”
• “It is not true that some object has property $P$” means “every object lacks property $P$.”

The quantifier changes, and the predicate is negated. Both changes are essential.

The first law expresses an idea that will drive the next lesson:

$$\text{not every object works}$$

means

$$\text{at least one object fails}.$$

For example, consider the claim

$$(\forall n\in \mathbb{Z})(n^2\ge n).$$

Its negation is

$$(\exists n\in \mathbb{Z})(n^2<n).$$

The original says that every integer satisfies the inequality. The negation says that there is an integer for which the inequality fails. Indeed, $n=-1$ makes the negated predicate true because

$$(-1{)}^2<-1$$

is false—so this is not the right calculation. Instead, check the original carefully:

$$(-1{)}^2\ge -1,$$

which is true. A better failure occurs at no integer here: in fact, $n^2\ge n$ holds for every integer. So its negation is false. This illustrates a useful distinction: writing a negation correctly does not require the original statement to be false. It states what a failure would look like.

Now use a genuinely false universal statement:

$$(\forall x\in \mathbb{R})(x^3\ge x^2).$$

Its negation is

$$(\exists x\in \mathbb{R})(x^3<x^2).$$

Here $x=\frac{1}{2}$ is a witness for the negation, since

$${\left(\frac{1}{2}\right)}^3<{\left(\frac{1}{2}\right)}^2.$$

The witness does two jobs at once: it makes the negation true and demonstrates that the original universal claim is false.

---

Negate the whole predicate, not just the quantifier

The compact slogan “switch the quantifier and negate the predicate” is reliable only if you identify the whole predicate correctly.

For atomic comparisons, use their logical opposites:

Predicate $P(x)$	Negation $\neg P(x)$
$x=5$	$x\ne 5$
$x\ne 5$	$x=5$
$x<5$	$x\ge 5$
$x\le 5$	$x>5$
$x>5$	$x\le 5$
$x\ge 5$	$x<5$
$a\mid n$	$a\nmid n$

Thus, the negation of

$$(\exists x\in \mathbb{R})(x^2<0)$$

is not “there exists a real number whose square is nonnegative.” That statement may be true, but it is not logically opposite to the original. The correct negation is

$$(\forall x\in \mathbb{R})(x^2\ge 0).$$

Why? The original statement claims there is at least one real number with a negative square. To deny it, every real number must have a square that is not negative.

A useful prose test is this:

Could the original statement and my proposed negation both be true?

If yes, the proposed statement cannot be a genuine negation.

For instance, both of the following can be true:

• “There exists an integer that is even.”
• “There exists an integer that is not even.”

Therefore, the second is not the negation of the first. The correct negation is:

Every integer is not even.

Symbolically,

$$\neg ((\exists n\in \mathbb{Z})(2\mid n))\equiv (\forall n\in \mathbb{Z})(2\nmid n).$$

This statement happens to be false, because $2$ is even, but it is nonetheless the correct logical negation.

---

Connectives inside quantified statements

Many mathematical predicates contain “and,” “or,” or “if … then.” Negation must pass through those connectives correctly.

The relevant laws are:

$$\neg (P\wedge Q)\equiv \neg P\vee \neg Q$$ $$\neg (P\vee Q)\equiv \neg P\wedge \neg Q$$ $$\neg (P\to Q)\equiv P\wedge \neg Q.$$

The first two are De Morgan’s laws. They say:

• To fail an “and” statement, at least one part must fail.
• To fail an “or” statement, both parts must fail.

Consider the existence claim

$$(\exists x\in \mathbb{R})(x>0\wedge x^2=2).$$

It says that some real number is both positive and a square root of $2$. Its negation begins by changing the quantifier:

$$(\forall x\in \mathbb{R})\neg (x>0\wedge x^2=2).$$

Now apply De Morgan’s law to the predicate:

$$(\forall x\in \mathbb{R})(x\le 0\vee x^2\ne 2).$$

In prose:

For every real number $x$, either $x$ is not positive or $x^2$ is not $2$.

This is precisely what it would mean for no positive real square root of $2$ to exist.

Universal conditionals and counterexamples

The most important special pattern for proof writing is a universally quantified conditional:

$$(\forall x\in D)(P(x)\to Q(x)).$$

Its negation is

$$(\exists x\in D)(P(x)\wedge \neg Q(x)).$$

Read this carefully:

A universal implication fails when there is an object that satisfies the hypothesis but fails the conclusion.

This object is a counterexample.

For example, the claim

$$(\forall n\in \mathbb{Z})(6\mid n\to (2\mid n\wedge 3\mid n))$$

says that every integer divisible by $6$ is divisible by both $2$ and $3$. Its negation is

$$(\exists n\in \mathbb{Z})(6\mid n\wedge \neg (2\mid n\wedge 3\mid n)).$$

Applying De Morgan’s law one more time gives

$$(\exists n\in \mathbb{Z})(6\mid n\wedge (2\nmid n\vee 3\nmid n)).$$

So a counterexample would need to be divisible by $6$ while failing divisibility by $2$ or by $3$. No such integer exists, so the original statement is true.

Notice what the negation is not:

$$(\exists n\in \mathbb{Z})(6\nmid n\wedge 2\nmid n).$$

That merely describes an integer not divisible by $6$, such as $5$. But the original theorem never claimed that all integers are divisible by $6$; it claimed something only about integers that are divisible by $6$.

---

Restrictions: conditional versus existential form

In the previous lesson, a restricted universal statement over a broad domain took the form

$$(\forall x\in D)(P(x)\to Q(x)).$$

Its negation must preserve the restriction as part of the counterexample:

$$(\exists x\in D)(P(x)\wedge \neg Q(x)).$$

For example, “Every prime greater than $2$ is odd” can be written over the integers as

$$(\forall p\in \mathbb{Z})((p\text{ is prime}\wedge p>2)\to p\text{ is odd}).$$

The negation is

$$(\exists p\in \mathbb{Z})(p\text{ is prime}\wedge p>2\wedge p\text{ is not odd}).$$

In prose:

There is a prime integer greater than $2$ that is not odd.

The number $2$ is not a counterexample because it fails the hypothesis $p>2$. This is exactly why universal implications are not negated by simply negating their conclusions.

Existential restrictions behave differently. “There exists a positive real number whose square is $2$” uses conjunction because one witness must meet every stated condition:

$$(\exists x\in \mathbb{R})(x>0\wedge x^2=2).$$

Its negation says that every candidate fails at least one required condition:

$$(\forall x\in \mathbb{R})(x\le 0\vee x^2\ne 2).$$

---

Multiple quantifiers: work from the outside inward

For nested quantifiers, negate each quantifier in turn, retaining their order and negating the final predicate.

The general pattern is

$$\neg ((\forall x\in D)(\exists y\in E)P(x,y))\equiv (\exists x\in D)(\forall y\in E)\neg P(x,y).$$

The order does not reverse. Each quantifier merely changes to its opposite.

Consider

$$(\forall n\in \mathbb{N})(\exists m\in \mathbb{N})(m>n).$$

This says:

For every natural number $n$, there is a natural number $m$ greater than $n$.

The value of $m$ may depend on $n$; for a given $n$, we can take $m=n+1$.

To negate it, proceed in stages:

$$\neg ((\forall n\in \mathbb{N})(\exists m\in \mathbb{N})(m>n))$$ $$\equiv (\exists n\in \mathbb{N})\neg ((\exists m\in \mathbb{N})(m>n))$$ $$\equiv (\exists n\in \mathbb{N})(\forall m\in \mathbb{N})(m\le n).$$

The final statement says:

There exists a natural number $n$ such that every natural number $m$ is at most $n$.

In other words, the natural numbers would have a largest element. This makes the meaning of the negation vivid: the original claim fails exactly if some $n$ cannot be surpassed by any natural number.

This example also shows why it is dangerous to negate nested statements informally. “Not every $n$ has some larger $m$” does not mean “every $n$ has no larger $m$.” The latter is much stronger and would say every natural number is largest.

---

Negating definitions

Definitions often contain an existential quantifier, even when written in ordinary prose. Learning to negate them is a way to see exactly what the definition excludes.

An integer $n$ is a multiple of $3$ precisely when

$$(\exists k\in \mathbb{Z})(n=3k).$$

Negating this definition gives

$$(\forall k\in \mathbb{Z})(n\ne 3k).$$

So to say that $n$ is not a multiple of $3$ is to say:

For every integer $k$, $n$ is not equal to $3k$.

Likewise, a natural number $n$ is a perfect square when

$$(\exists k\in \mathbb{N})(n=k^2).$$

Its negation is

$$(\forall k\in \mathbb{N})(n\ne k^2).$$

Thus, a non-square is not merely a number that fails to equal one particular square. It fails to equal $k^2$ for every natural number $k$.

This style of analysis will be especially useful in number theory and topology, where definitions routinely combine quantifiers with conditions. Before attempting a proof, rewriting the desired conclusion or its negation in quantified form often reveals the kind of argument that is needed.

---

A dependable negation procedure

When you encounter a quantified statement, use this short procedure.

1. State the domain and identify the outermost quantifier.
   Determine whether the assertion begins with “for every” or “there exists.”

2. Switch each quantifier.
   Universal becomes existential; existential becomes universal.

3. Negate the final predicate completely.
   Replace comparisons by their opposites, use De Morgan’s laws for conjunctions and disjunctions, and replace a conditional by “hypothesis and not conclusion.”

4. Translate the result into full prose.
   Check whether it genuinely describes the failure of the original claim.

A particularly useful pair of translations to remember is:

$$\neg ((\forall x\in D)P(x))\equiv (\exists x\in D)\neg P(x)$$ $$\neg ((\forall x\in D)(P(x)\to Q(x)))\equiv (\exists x\in D)(P(x)\wedge \neg Q(x)).$$

The second formula is the formal anatomy of a counterexample.

---

Key takeaways

Negating a quantified statement requires two operations: switch every quantifier and negate the predicate within its scope. “Not every” means “some fail,” while “there does not exist” means “all fail.”

When a predicate contains connectives, negate its complete logical structure. In particular, the negation of a universal conditional is an existential statement identifying an object for which the hypothesis holds and the conclusion fails.

Next, you will focus directly on disproving universal statements by constructing counterexamples. The logical work done here will explain exactly why one carefully chosen example can refute an assertion that claims to cover every object in a domain.