Negating Quantified Statements

From Propositions to Predicates

In propositional logic, a statement like "5 is a prime number" is a simple, indivisible unit. In predicate logic, we can analyze its internal structure. We can define a predicate, or propositional function, $P(x)$ as a statement whose truth value depends on the variable $x$. For example, let $P(x)$ be the predicate "x is a prime number."

This $P(x)$ is not a proposition on its own because it is neither true nor false. It only becomes a proposition when the variable $x$ is either given a specific value (e.g., $P(5)$ is true, $P(6)$ is false) or is "bound" by a quantifier.

The set of all possible values for the variable is called the universe of discourse. Specifying this universe is crucial. For our predicate $P(x)$, if the universe is the set of integers, the predicate makes sense. If the universe is the set of all triangles, it does not.

To learn the formal definitions, please read the first part of the following resource.

Negating Quantified Statements: De Morgan's Laws for Quantifiers

The core of this lesson is learning how to negate quantified statements. The rules for doing so are direct analogues of De Morgan's laws, which you saw in the context of propositions ($\neg (A\wedge B)\equiv \neg A\vee \neg B$).

1. Negating a Universal Statement: Consider the statement "All dogs are mammals." This is a "for all" ($\forall$) statement. To show it is false, you don't need to prove that no dogs are mammals. You only need to find one dog that is not a mammal.

   Symbolically, the negation of a universal statement becomes an existential statement.

   $$\neg (\forall x,P(x))\equiv \exists x,\neg P(x)$$

   "It is not the case that for all x, P(x) is true" is logically equivalent to "There exists an x for which P(x) is false."

2. Negating an Existential Statement: Now consider "There exists a person who can fly." This is a "there exists" ($\exists$) statement. To show it is false, you can't just find one person who can't fly. You have to show that every person cannot fly.

   Symbolically, the negation of an existential statement becomes a universal statement.

   $$\neg (\exists x,P(x))\equiv \forall x,\neg P(x)$$

   "It is not the case that there exists an x for which P(x) is true" is logically equivalent to "For all x, P(x) is false."

The following video provides an excellent, intuitive walkthrough of these two rules.

These rules can be summarized with two clear examples.

Now, let's solidify this with a formal reading that explains the reasoning behind these equivalences.

Negating More Complex Statements

Real mathematical statements often involve multiple quantifiers. The rule is to apply the negation from left to right, one quantifier at a time.

For example, let's negate $\forall x\exists y,Q(x,y)$.

1. First, treat $\exists y,Q(x,y)$ as a single predicate $R(x)$. The statement is $\forall x,R(x)$.
2. The negation is $\neg (\forall x,R(x))\equiv \exists x,\neg R(x)$.
3. Now, substitute $R(x)$ back: $\exists x,\neg (\exists y,Q(x,y))$.
4. Apply the negation rule to the inner part: $\neg (\exists y,Q(x,y))\equiv \forall y,\neg Q(x,y)$.
5. The final result is: $\exists x\forall y,\neg Q(x,y)$.

Notice that the order of quantifiers is critical. The statement $\forall x\exists y,Q(x,y)$ ("For every $x$, there is a $y$...") is very different from $\exists y\forall x,Q(x,y)$ ("There is a $y$ that works for every $x$...").

A Look Ahead: The Definition of a Limit

To see how powerful this technique is in the context of Real Analysis, consider the formal $ϵ$-$\delta$ definition of a limit, which you will study in depth later.

The statement ${\lim }_{x\to a}f(x)=L$ is defined as:

Let's use our rules to express what it means for the limit not to be $L$, i.e., ${\lim }_{x\to a}f(x)\ne L$. We negate the entire statement step-by-step:

1. $\neg [\forall ϵ>0,\exists \delta >0,\forall x,(\dots )]$
2. $\equiv \exists ϵ>0,\neg [\exists \delta >0,\forall x,(\dots )]$ (Negating the first $\forall$)
3. $\equiv \exists ϵ>0,\forall \delta >0,\neg [\forall x,(\dots )]$ (Negating the $\exists$)
4. $\equiv \exists ϵ>0,\forall \delta >0,\exists x,\neg (0<|x-a|<\delta \to |f(x)-L|<ϵ)$ (Negating the second $\forall$)

Finally, we negate the conditional statement. Recall from our last lesson that $\neg (P\to Q)\equiv P\wedge \neg Q$. So, the negation of the limit definition is:

This complex but precise statement is derived mechanically using the rules you've just learned. Mastering this skill is essential for your goal of studying analysis rigorously.

Practice

Now it's time to put these rules into practice. The following video presents two statements for you to negate. Pause the video and try to write down the negations yourself before watching the solutions.

Conclusion

In this lesson, we have extended our logical toolkit to handle general statements using quantifiers. This is a critical step toward the language of formal mathematics.

The key takeaways are:

• Statements about all elements of a set use the universal quantifier ($\forall$).
• Statements about the existence of at least one element use the existential quantifier ($\exists$).
• Negating a quantified statement follows a pattern similar to De Morgan's laws: the quantifier is swapped ($\forall \leftrightarrow \exists$), and the negation is applied to the predicate itself.
• For statements with multiple quantifiers, the negation is applied sequentially from left to right.

You now have the fundamental language of logic needed for mathematical proofs. In our next lesson, we will use this foundation to construct our first type of formal argument: the direct proof.