Negating Existential Statements

From One Witness to No Witnesses

In Negating Universal Statements, we established that denying “Every allowed input satisfies \(A(x)\)” requires one input where \(A(x)\) fails. We now examine the other direction: what does it mean to deny that even one successful input exists?

Consider “There exists a real number \(x\) such that \(x^2=4\).” The fact that \(x=0\) does not satisfy the equation does not disprove this statement. Neither does the failure of \(x=1\). The value \(x=2\) supplies a witness, so the existence claim is true.

To deny an existence claim, we must rule out every possible witness. The distinction is therefore between “some input fails” and “no input succeeds.” Only the second is the negation of “some input succeeds.”

Existential Statements and Witnesses

As before, let \(D\) be the domain of allowed inputs, and let \(A(x)\) be a condition that is either true or false for each \(x\in D\).

Definition. The existential statement

\exists x\in D,\ A(x)

means “There is at least one element \(x\) of \(D\) for which \(A(x)\) holds.” The symbol \(\exists\) is the existential quantifier. An element \(c\in D\) satisfying \(A(c)\) is a witness to this statement.

“At least one” does not mean “exactly one.” For the equation \(x^2=4\) over the real numbers, both \(2\) and \(-2\) are witnesses. Having two witnesses confirms the existential statement; it does not contradict it.

The phrase “There does not exist \(x\in D\) such that \(A(x)\)” means that the existential statement is false. It is sometimes written \(\nexists x\in D,\ A(x)\). We will use \(\neg(\exists x\in D,\ A(x))\) to keep the scope of the negation explicit.

The Rule for Negating an Existential Statement

Theorem: Negation of an Existential Statement. For any domain \(D\) and any condition \(A(x)\) defined on \(D\),

\neg\bigl(\exists x\in D,\ A(x)\bigr) \equiv \forall x\in D,\ \neg A(x).

Negation changes “there exists” to “for every” and negates the condition, while leaving the domain unchanged.

Proof. Suppose first that \(\neg(\exists x\in D,\ A(x))\) is true. Consider any \(c\in D\). If \(A(c)\) were true, then \(c\) would be a witness to the existential statement, contrary to our assumption. Thus \(A(c)\) is false, so \(\neg A(c)\) is true. Since this holds for every \(c\in D\), the statement \(\forall x\in D,\ \neg A(x)\) is true.

Conversely, suppose \(\forall x\in D,\ \neg A(x)\) is true. If \(\exists x\in D,\ A(x)\) were true, it would have a witness \(c\in D\) satisfying \(A(c)\). The universal statement would also give \(\neg A(c)\), a contradiction. Therefore the existential statement is false, and its negation is true. This proves the equivalence.

If \(D=\varnothing\), there is no witness to the existential statement, so its negation is true. The universal statement on the right is also true by vacuous truth, as discussed in the previous tutorial. Thus the rule does not require a nonempty domain.

The notation \(\equiv\) again means logical equivalence: the two formulas agree in truth value for every choice of domain and condition.

“None Succeed” Is Not “Some Fail”

Formula	Meaning
\(\exists x\in D,\ A(x)\)	At least one allowed input succeeds.
\(\neg(\exists x\in D,\ A(x))\)	No allowed input succeeds.
\(\forall x\in D,\ \neg A(x)\)	Every allowed input fails.
\(\exists x\in D,\ \neg A(x)\)	At least one allowed input fails.

The middle two rows are equivalent. The last row is different: an input may fail while another succeeds. Moving the negation inside without changing \(\exists\) to \(\forall\) does not negate the original statement.

Worked Example: A Failed Candidate Does Not Settle Existence

Let \(D=\{-1,0,2\}\), and let \(A(x)\) mean \(x>0\). Then

\exists x\in D,\ x>0

is true because \(2\in D\) and \(2>0\). Its negation is

\forall x\in D,\ x\leq0,

which is false because \(2\) violates it. Although \(-1\) and \(0\) fail the original condition, their failure does not rule out the successful input \(2\).

In this example, both “Some \(x\in D\) satisfies \(x>0\)” and “Some \(x\in D\) satisfies \(x\leq0\)” are true. Consequently, they cannot be negations of one another.

The proof requirement changes with the quantifier. One verified witness proves an existential statement. To disprove it, show that every allowed input fails. For a finite domain, checking every element can suffice; for an infinite domain, a list of unsuccessful trials does not by itself rule out all witnesses.

Proving That No Witness Exists

Forming a negation is a logical task. Determining whether that negation is true is a separate mathematical task. The negation rule tells us what to prove, but does not prove that every particular existence claim is false.

Worked Example: An Equation with No Real Solution

Negate the statement

\exists x\in\mathbb R,\ x+1=x.

The exact negation is

\forall x\in\mathbb R,\ x+1\neq x.

To prove it, let \(x\) be any real number. If \(x+1=x\), subtracting \(x\) from both sides would give \(1=0\), which is false. Hence \(x+1\neq x\). This argument applies to every real \(x\), so the negation is true and the original existence claim is false.

The argument did not select a particular unsuccessful number. It excluded every real number by using a consequence that any proposed solution would have to satisfy.

Worked Example: A Correct Negation Can Be False

The negation of “There exists a real number \(x\) with \(x\geq5\)” is

\forall x\in\mathbb R,\ x<5.

This is the correct negation, but it is false: \(x=5\) is real and does not satisfy \(x<5\). Indeed, \(5\) is a witness to the original existential statement.

The boundary matters. Negating \(x\geq5\) gives \(x<5\), not \(x\leq5\). Equality belongs to the original condition, so it must be excluded from its negation.

Negating the Complete Inner Condition

An existential statement may ask for a witness satisfying several requirements. After changing the quantifier, negate the entire condition using the rules from Negating a Mathematical Statement.

Identify the allowed inputs.
Write the domain \(D\) explicitly and keep it fixed.

Identify the full condition.
Write the assertion as \(\exists x\in D,\ A(x)\), including every requirement on the witness.

Change the quantifier and negate the condition.
Write \(\forall x\in D,\ \neg A(x)\), then simplify using the appropriate logical rules.

If a disproof is requested, exclude every witness.
Give an argument valid for any input in \(D\), or check every element when the domain is finite.

Worked Example: No Input Satisfies Both Bounds

Let \(D=\{0,1,5\}\). Consider

\exists x\in D,\ (x>1)\land(x\leq4).

Applying the existential negation rule and De Morgan’s Laws gives

\begin{aligned} &\neg\bigl(\exists x\in D,\ (x>1)\land(x\leq4)\bigr)\\ &\quad\equiv \forall x\in D,\ \neg\bigl((x>1)\land(x\leq4)\bigr)\\ &\quad\equiv \forall x\in D,\ (x\leq1)\lor(x>4). \end{aligned}

This negation is true. The elements \(0\) and \(1\) satisfy \(x\leq1\), while \(5\) satisfies \(x>4\). These are all the elements of \(D\), so no element satisfies both original bounds.

The failed requirement need not be the same for every input. Some inputs fail the lower bound; others fail the upper bound. Replacing the disjunction in the negation by a conjunction would incorrectly require every input to fail both bounds.

Worked Example: Neither Alternative Is Available

Let \(D=\{1,2,3\}\). Negate “There exists \(x\in D\) such that \(x<0\) or \(x>4\).”

\begin{aligned} &\neg\bigl(\exists x\in D,\ (x<0)\lor(x>4)\bigr)\\ &\quad\equiv \forall x\in D,\ (x\geq0)\land(x\leq4). \end{aligned}

All three elements of \(D\) lie between \(0\) and \(4\), inclusive. Thus both alternatives fail at every allowed input, proving the negation.

For a conjunction to fail, at least one part must fail. For a disjunction to fail, both parts must fail. The quantifier rule does not replace these inner logical rules; it tells us where to apply them.

Preserving Restrictions on a Witness

Suppose the statement is “There exists a positive real number \(x\) such that \(x+1\leq1\).” Let \(D\) be the set of positive real numbers. Its negation is

\neg\bigl(\exists x\in D,\ x+1\leq1\bigr) \equiv \forall x\in D,\ x+1>1.

The negation remains a statement about positive real numbers. It is true because adding \(1\) to \(x>0\) gives \(x+1>1\). A value such as \(x=-1\) is not a possible witness to the original claim, even though it satisfies \(x+1\leq1\).

We can also express the original claim over all real numbers by placing the positivity requirement inside the condition:

\exists x\in\mathbb R,\ (x>0)\land(x+1\leq1).

Its negation is

\forall x\in\mathbb R,\ (x\leq0)\lor(x+1>1).

By the equivalence between \(A\to B\) and \(\neg A\lor B\), this says

\forall x\in\mathbb R,\ (x>0\to x+1>1).

These are two ways to express the same denial: every positive real number fails the requested inequality. Inputs that are not positive are irrelevant to the search for a witness.

Existence under a restriction uses “and.” “There exists \(x\in D\) satisfying \(A(x)\) and \(B(x)\)” requires both conditions at the same input. Writing \(\exists x\in D,\ (A(x)\to B(x))\) instead changes the claim: an input where \(A(x)\) is false already makes the implication true.

If an existential statement genuinely contains an implication, use the implication negation rule without changing its meaning:

\begin{aligned} &\neg\bigl(\exists x\in D,\ (A(x)\to B(x))\bigr)\\ &\quad\equiv \forall x\in D,\ A(x)\land\neg B(x). \end{aligned}

Here every input must make the implication false: its hypothesis must be true and its conclusion false at every allowed input. This is much stronger than excluding witnesses to \(A(x)\land B(x)\).

Empty Domains and the Two Negation Rules

If \(D=\varnothing\), then \(\exists x\in D,\ A(x)\) is false regardless of the condition. There is no allowed input to serve as a witness. Its negation is therefore true, in agreement with the vacuous truth of \(\forall x\in D,\ \neg A(x)\).

For example, take the empty domain used in the previous tutorial:

D=\{x\in\mathbb R:x>1\text{ and }x<0\}.

“There exists \(x\in D\) with \(x=7\)” is false. Its negation, “Every \(x\in D\) satisfies \(x\neq7\),” is true. But “There exists \(x\in D\) with \(x\neq7\)” is false as well: changing the condition cannot supply an element to an empty domain.

Together with the result from the previous tutorial, we now have both single-quantifier negation rules:

\begin{aligned} \neg(\forall x\in D,\ A(x)) &\equiv \exists x\in D,\ \neg A(x),\\ \neg(\exists x\in D,\ A(x)) &\equiv \forall x\in D,\ \neg A(x). \end{aligned}

The complete distinction. To deny “every,” find one failure. To deny “there exists,” rule out every success. In either case, keep the domain unchanged and negate the whole condition, not just one selected part.

Check Your Understanding

Write each negation as a complete quantified statement. When asked to determine its truth, distinguish a proof ruling out every witness from the failure of only one candidate.

Negate “There exists a real number \(x\) such that \(x>5\).” Is the negation true? Explain why checking \(x=5\) does not disprove the original statement.
Let \(D=\{-2,0,2\}\). Negate “There exists \(x\in D\) with \(x^2=4\).” Determine the truth value of each statement. Does having two witnesses cause any difficulty?
Negate “There exists \(x\in\{0,1,5\}\) such that \(1<x\leq4\).” Verify the negation at every element. Must the same bound fail at all three inputs?
Negate “There exists a real \(x\) such that \(x+1=x\) or \(x+2=x\).” Prove the negation by treating an arbitrary real input.
Negate “There exists a positive real \(x\) such that \(x+2\leq2\).” Express your answer both over the positive real numbers and as a universal conditional over all real numbers. Why is \(x=0\) not an admissible witness?
If \(D=\varnothing\), determine the truth values of \(\exists x\in D,\ A(x)\), \(\exists x\in D,\ \neg A(x)\), and \(\forall x\in D,\ \neg A(x)\). Which is the negation of the first statement?