Section 3.2 Negating Quantified Statements
In this section we will look at how to negate statements involving quantifiers.
If you look back at the Check your Understanding questions in
Section 3.1, you should notice that both
\(\forall x\in D, P(x)\) and
\(\forall x\in D, \sim P(x)\) were false, which means they are not negations of each other. Similarly, both
\(\exists x\in D, P(x)\) and
\(\exists x \in D, \sim P(x)\) were true. In general, the two statements won’t necessarily have the same truth values, but the examples were chosen to make sure we can see that they are not negations of each other.
Negating Quantified Statements.
The negation of \(\forall x\in D, P(x)\) is \(\exists x\in D, \sim P(x)\text{.}\)
In notation:
\begin{equation*}
\sim(\forall x\in D, P(x))\equiv \exists x\in D, \sim P(x).
\end{equation*}
The negation of \(\exists x\in D, P(x)\) is \(\forall x\in D, \sim P(x)\text{.}\)
In notation:
\begin{equation*}
\sim(\exists x\in D, P(x))\equiv \forall x\in D, \sim P(x).
\end{equation*}
We can think of negation as switching the quantifier and negating \(P(x)\text{,}\) but it will be really helpful if we can understand why this is the negation. Thinking about negating a “for all” statement, we need the statement to not be true for all things, which means it must be false for something, Thus, there exists something making \(\sim P(x)\) true. Thinking about negating a “there exists” statement, we need there not to exist anything making \(P(x)\) true, which means \(P(x)\) must be false for everything. Thus, everything makes \(\sim P(x)\) true.
Example 3.2.1. Negating a Quantified Statement.
Negate the statement: For all primes \(p\text{,}\) \(p\) is odd. Is this statement true or false?
Answer 1.
There exist a prime \(p\) such that \(p\) is not odd. The original statement is false, since we can find an even prime (\(p=2\)).
Negate the statement: There exists a real number \(x\text{,}\) such that \(x^2< 0\text{.}\) Is this statement true or false?
Answer 2.
For all real numbers \(x\text{,}\) \(x^2\geq 0\text{.}\) The original statement is false, since the negation is true.
Activity 3.2.1.
Write the negation of the following statements (in English).
(a)
For all integers \(n\text{,}\) \(\sqrt{n}\) is an integer.
(b)
There exists an integer \(n\text{,}\) such that \(n^2=5\text{.}\)
Many of our quantified statements may have predicates involving other logical connectives. So it is going to be important to remember how to negate "and"s, "or"s, and "if...then"s. The following summarizes the rules we have already seen for negating statements with connectives
Negations of Logical Statements.
-
AND statement.
\(\sim(p\wedge q)\equiv \sim p\ \vee \sim q\text{.}\) This is DeMorgan’s Law.
-
OR statement.
\(\sim(p\vee q)\equiv \sim p\ \wedge \sim q\text{.}\) This is DeMorgan’s Law.
-
IF...THEN statement.
\(\sim(p\rightarrow q)\equiv p\ \wedge \sim q\text{.}\) The negation of a conditional is NOT a conditional.
-
Universal conditional.
\begin{align*}
\sim(\forall x\in D, P(x)\rightarrow Q(x)) & \equiv \exists x\in D, \sim(P(x)\rightarrow Q(x))\\
&\equiv \exists x\in D, P(x)\wedge \sim Q(x)
\end{align*}
Activity 3.2.2.
Write the negation of the following statements (in English).
(a)
There exists an integer \(n\text{,}\) such that \(1 < n < 2\text{.}\)
(b)
For all real numbers \(x\text{,}\) if \(x>2\) then \(x+5>7\text{.}\)
(c)
For all functions \(f\text{,}\) if \(f\) is continuous, then \(f\) is differentiable.
Recall from
Section 2.2 the contapositive of
\(p\rightarrow q\) is
\(\sim q\rightarrow \sim p\text{.}\) We can use this to define the contrapositive of a universal conditional statement.
Definition 3.2.2.
The universal conditional statement \(\forall x\in D, P(x)\rightarrow Q(x)\) has contrapositive \(\forall x\in D, \sim Q(x)\rightarrow \sim P(x)\text{.}\)
Similarly, the converse of \(p\rightarrow q\) is \(q\rightarrow p\text{.}\)
Definition 3.2.3.
The universal conditional statement \(\forall x\in D, P(x)\rightarrow Q(x)\) has converse \(\forall x\in D, Q(x)\rightarrow P(x)\text{.}\)
Activity 3.2.3.
Consider the statement “For all real numbers \(x\text{,}\) if \((x+1)(x-2)>0\) then \(x < -1\) or \(x>2\text{.}\)”
(a)
Write the negation of the statement.
(b)
Write the contrapositive of the statement.
Activity 3.2.4.
Consider the statement “For all integers \(n\text{,}\) if \(n\) has a factor of 15, then \(n\) has a factor of 3 and \(n\) has a factor of 5.”
(a)
Write the negation of the statement.
(b)
Write the contrapositive of the statement.
The relationship between “for all” and “there exists” can be used to show some surprising things. What happens if our domain, \(D\text{,}\) has nothing in it? In particular, let \(D=\emptyset\text{,}\) the empty set. Is \(\forall x\in D, P(x)\) true or false? Well, let’s look at the negation: \(\exists x\in D, \sim P(x)\text{.}\) Now the negation must be false since \(D\) has nothing in it, so there can’t exist something in \(D\) making \(\sim P(x)\) true. Since the negation is false, the original statement is true! We say \(\forall x\in D, P(x)\) is vacuously true.
Example 3.2.4. Vacuously True Statement.
Consider the statement “For all llamas, \(L\text{,}\) in Discrete Math, \(L\) is getting an A.” The negation is “There exists a llama, \(L\text{,}\) in Discrete Math, such that \(L\) is not getting an A.” Since no such llama exists, the negation is false. Making the original true. So every llama in Discrete is getting an A.
As one additional note, it can be helpful in deciding if your negation is correct by finding the truth value of both the original and the negation. They should have opposite values. Similarly, if you need to determine the truth value of a complex statement, it might be easier to find the truth value of the negation.
Activity 3.2.5.
(a)
For all integers \(n\text{,}\) \(\sqrt{n}\) is an integer.
(b)
There exists an integer \(n\text{,}\) such that \(n^2=5\text{.}\)
(c)
There exists an integer \(n\text{,}\) such that \(1 < n < 2\text{.}\)
(d)
For all real numbers \(x\text{,}\) if \(x>2\) then \(x+5>7\text{.}\)
(e)
For all functions \(f\text{,}\) if \(f\) is continuous, then \(f\) is differentiable.
(f)
For all real numbers \(x\text{,}\) if \((x+1)(x-2)>0\) then \(x < -1\) or \(x>2\text{.}\)
(g)
For all integers \(n\text{,}\) if \(n\) has a factor of 15, then \(n\) has a factor of 3 and \(n\) has a factor of 5.
Reading Questions Check Your Understanding
1.
Determine the negation of \(\forall n\in \mathbb{Z}, n>0\text{.}\)
\(\exists n\in \mathbb{Z}, n\leq 0.\)
-
\(\exists n\in \mathbb{Z}, n> 0.\)
-
\(\forall n\in \mathbb{Z}, n\leq 0.\)
-
\(\forall n\in \mathbb{Z}, n> 0.\)
-
2.
Determine the negation of \(\forall n\in \mathbb{Z}\text{,}\) if \(n>0\) then \(n^3>0\text{.}\)
\(\exists n\in \mathbb{Z}\text{,}\) if \(n\leq 0\) then \(n^3\leq 0\)
-
\(\exists n\in \mathbb{Z}\text{,}\) \(n\leq 0\) and \(n^3\leq 0.\)
-
\(\exists n\in \mathbb{Z}\text{,}\) \(n>0\) and \(n^3\leq 0.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) if \(n\leq 0\) then \(n^3\leq 0\)
-
3.
Determine the negation of \(\exists n\in \mathbb{Z}\text{,}\) \(n>5\) and \(n^2\leq 10\text{.}\)
\(\forall n\in \mathbb{Z}\text{,}\) \(n\leq 5\) or \(n^2> 10.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) \(n\leq 5\) and \(n^2> 10.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) \(n >5\) or \(n^2\leq 10.\)
-
\(\exists n\in \mathbb{Z}\text{,}\) \(n >5\) or \(n^2\leq 10.\)
-
\(\exists n\in \mathbb{Z}\text{,}\) \(n\leq 5\) and \(n^2> 10.\)
-
4.
Determine the negation of \(\exists n\in \mathbb{Z}\text{,}\) such that if \(n^2>4\) then \(n>2\) or \(n<-2.\)
\(\forall n\in \mathbb{Z}\text{,}\) if \(n^2\leq 4\) then \(n\leq 2\) or \(n\geq -2.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) if \(n^2\leq 4\) then \(-2\leq n\leq 2.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) \(n^2>4\) and \(-2\leq n\leq 2.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) \(n^2\leq 4\) and \(-2\leq n\leq 2.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) \(n^2\leq 4\) and \(n\leq 2\) or \(n\geq -2.\)
-
5.
Determine the contrapositive of \(\forall n\in \mathbb{Z}\text{,}\) if \(n>0\) then \(n^3>0\text{.}\)
\(\exists n\in \mathbb{Z}\text{,}\) if \(n^3\leq 0\) then \(n\leq 0.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) if \(n\leq 0\) then \(n^3\leq 0.\)
-
\(\exists n\in \mathbb{Z}\text{,}\) if \(n\leq 0\) then \(n^3\leq 0.\)
-
\(\forall n\in \mathbb{Z}\text{,}\) if \(n^3\leq 0\) then \(n\leq 0.\)
-
Exercises Exercises
1.
Which of the following is a negation for “All discrete math students are athletic”? More than one answer may be correct.
There is a discrete math student who is nonathletic.
All discrete math students are nonathletic.
There is an athletic person who is a discrete math student.
No discrete math students are athletic.
Some discrete math students are nonathletic.
No athletic people are discrete math students.
2.
Write an informal negation for each of the following statements. Be careful to avoid negations that are ambiguous.
All dogs are friendly.
All people are happy.
Some apples are red.
Some teams are undefeated.
3.
Write a negation for each of the following statements.
Any valid argument has a true conclusion.
Every real number is positive, negative, or zero.
4.
Write the negation of each of the statements.
\(\forall\) real numbers \(x\text{,}\) if \(x>3\) then \(x^2>9\text{.}\)
\(\forall n\in \mathbb{Z}\text{,}\) if \(n\) is prime then \(n\) is odd or \(n=2\text{.}\)
\(\forall\) integers \(n\text{,}\) if \(n\) is divisible by 6, then \(n\) is divisible by 2 and \(n\) is divisible by 3.
5.
Determine whether the proposed negation is correct. If it is not, write a correct negation.
Statement: The sum of any two irrational numbers is irrational.
Proposed negation: The sum of any two irrational numbers is rational.
6.
Determine whether the proposed negation is correct. If it is not, write a correct negation.
Statement: For all integers \(n\text{,}\) if \(n^2\) is even then \(n\) is even.
Proposed negation: For all integers \(n\text{,}\) if \(n^2\) is even, then \(n\) is not even.
7.
Consider the following sequence of digits: 2300204. A person claims that all of the 1’s in the sequence are to the left of all of the 0’s in the sequence. Is this true? Justify your answer.
Hint.
Write the claim formally and write a formal negation for it. Is the negation true or false?
You have attempted
of
activities on this page.
