# When does the negation of a universal quantifier require a disjunctive statement?

Here's a question I got wrong on a HW assignment recently, which asked students to negate the given statement and assign that negation a truth value.

Q: There are exactly 3 points on every line. my answer: Some lines have more than 3 points. (true)

explanation: I took this to be a universally quantified statement:

for every line l in the set of all lines L, if p(l) gives the number of points incident with l, p(l) = 3

I was marked wrong on the negation because I didn't also state that lines could have less than 3 points. Assuming that's correct, in this case of universally quantified negation it is not sufficient to state that p(l) does not equal 3 for at least one line l.

here's what my teacher wrote when I asked for a clarification:

Yes, your negation is half of the correct negation. But there are two parts to it. Recall in class there are two statements for the negation of Playfair's version of the parallel postulate. You need them both there to have a complete negation of the original statement.

This partly makes sense to me because the negation of my answer doesn't yield the original question. But it also doesn't because my answer did (I think) negate the statement, and did so in a way that is consistent with most everything I have read about how to negate logic statements: to negate ~(P -> Q) it is enough to claim at least one case where P -> ~Q.

Any clarification would be much appreciated!

• Hint: "Some have more than 3" ($\exists x\in L: p(x)\color{green}{>}3$) is not entirely the negation of "All have exactly 3" ($\forall x\in L: p(x)\color{green}{=}3$). – Graham Kemp May 16 '15 at 4:25

Consider the statement $P$, as follows:

Bob's shirt is blue.

Suppose I claimed that the negation $\lnot P$ is this statement:

Bob's shirt is red.

Can you see what's wrong?

The negation of a statement must be true if, and only if, the original statement is false.

$$P\text{ is false}\iff \lnot P\text{ is true}$$

(That's pretty much the meaning of the word "negation".) But even when $P$ is false, i.e. Bob's shirt isn't blue, I can't logically deduce that Bob's shirt must be red - it could be any other color. Clearly, the correct negation is simply

Bob's shirt isn't blue.

Do you see how this applies to your situation?

• Yes, thank you! All of these responses have actually been really helpful. – Stephen Anderson May 16 '15 at 6:36

This partly makes sense to me because the negation of my answer doesn't yield the original question. But it also doesn't because my answer did (I think) negate the statement, and did so in a way that is consistent with most everything I have read about how to negate logic statements: to negate ~(P -> Q) it is enough to claim at least one case where P -> ~Q.

Not quite. The negation of an implication is a conjunction of the antecedant and the negation of the consequent. Though you are correct that the negation of a universal is the existence of a negation.

$$\neg \forall x(Px\to Qx)\iff \exists x(Px\wedge \neg Qx)$$

In this case $Px$ means "$x$ is a line" and $Qx$ means "$x$ has exactly 3 points".

Still, your answer has negated the universal, and you actually negated the implication properly. "There are some lines with $\neg Qx$" is correct.

The issue is that you have not properly negated $Qx$. The negation of "have exactly 3 points" is not "have more than 3 points."

• Thank you! This makes a whole lot more sense to me now... – Stephen Anderson May 16 '15 at 6:38

The problem is that the negation of $p(\ell)=3$ is not $p(\ell)>3$: it’s $p(\ell)\ne 3$. The context ensures that we’re talking about non-negative integers, so $p(\ell)\ne 3$ expands to

$$p(\ell)=0\text{ or }p(\ell)=1\text{ or }p(\ell)=2\text{ or }p(\ell)>3\;.$$

The negation of $\forall x(P(x)\to Q(x))$ is $\exists x(\neg(P(x)\to Q(x)))$, and since $P(x)\to Q(x)$ is logically equivalent ot $\neg P(x)\lor Q(x)$, this is logically equivalent to $\exists x(\neg(\neg P(x)\lor Q(x)))$, which is in turn logically equivalent to $\exists x(P(x)\land\neg Q(x))$.

Here $P(x)$ is ‘$x$ is a line’, and $Q(x)$ is ‘$p(x)=3$’. To show that it holds, one need only find a line $\ell$ for which $p(\ell)\ne 3$, and finding one with more than $4$ points would certainly do this. So, however, would finding one with $0,1$, or $2$ points. Any of these would be sufficient to refute the claim $\forall x(P(x)\to Q(x))$, but you’re supposed to be doing more than that: you’re supposed to be finding the negation of the claim. In a sense you’re supposed to be finding all of the possible ways to refute the claim.