Basic logic — relationships between statements — negation

I want to talk in the next couple of posts about transformations that can be applied to a statement. The three transformations I plan to discuss are forming the negation, the converse, and the contrapositive. For those who like an abstract definition to keep them going, let me quickly give the three relevant ones here. If $P$ is a statement, then “not $P$ “, sometimes written in symbolic form as $\neg P,$ is its negation. If $P$ has the form $p\implies q,$ then the converse of $P$ is the statement $q\implies p.$ And finally, again if $P$ has the form $p\implies q,$ the contrapositive is the statement $\neg q\implies\neg p.$

If that was too abstract for you, then maybe you’ll be happier to pick the idea up by looking at some examples. (I myself find that easier. I like to see enough examples for the abstract concept to become obvious. But others seem to prefer the abstract concept in order to understand the point of the examples. In this post I am indulging those kinds of people.)

Negation.

It isn’t that difficult to define negation. In symbolic terms, you negate a statement by sticking $\neg$ in front of it (putting the whole statement in brackets if it is complicated enough to need it). You can then read $\neg$ as “not”, or if you want to be absolutely sure you are getting the meaning right, as “it is not the case that”. It may seem a bit odd to have a whole post on this, when I’ve already devoted a post to the word “not”. But I wrote that post before writing about implication and quantifiers. That leaves me with things that still need to be said.

Let’s begin with a simple statement:

$n$ has at least three distinct prime factors.

According to what I said above, the negation of that statement is

$\neg$ ( $n$ has at least three distinct prime factors)

which can be translated into a more natural sentence in various ways. One possible translation is this.

$n$ does not have at least three distinct prime factors.

However, you should be very wary about simply moving the word “not” to a place where the sentence reads more naturally, because this can change the meaning of the sentence.

For example, take the following sentence from Goldilocks and the Three Bears.

Somebody has been sitting in my chair.

We can form the negation in the unnatural way as follows.

$\neg$ (Somebody has been sitting in my chair.)

Suppose we were now to move the “not” to where the main verb is. We would get this:

Somebody has not been sitting in my chair.

But that is not the same as saying

It is not the case that somebody has been sitting in my chair.

That last sentence, which is the correct negation, is telling us that nobody has been sitting in my chair, whereas the careless moving of the “not” produced a sentence that merely told us that there is somebody who hasn’t been sitting in that chair.

Let us return to the sentence

$n$ has at least three distinct prime factors.

If we want to negate it, we should think to ourselves, “What has to happen for this sentence to be false?” In this case it is quite simple: we know that the number of distinct prime factors of $n$ is a non-negative integer, so the only way for it not to be the case that that non-negative integer is at least 3 is for it to be at most 2. So a clean way of expressing the negation of this sentence is

$n$ has at most two distinct prime factors.

Negating a statement that begins with a quantifier.

It is very important to know how to negate sentences where quantifiers are involved. (The Goldilocks example, with the word “somebody”, is an example of the kind of mistake it is possible to make if you don’t.) Fortunately, negating sentences with quantifiers is extremely easy once you know how to do it. In fact, it is so easy that you can do it completely automatically even if you have no understanding whatsoever of the statement that you are negating.

To explain this, let me begin with two simple examples, which both involve just one quantifier. First let’s go for a universal quantifier. I’ll write a sentence in words and also in more symbolic form. Let’s write $P$ for the set of all prime numbers.

Every prime number is odd.

$\forall p\in P\ \ p$ is odd.

What has to be true to make it not the case that every prime number is odd? Do we need every prime number to be even? Not at all. All we need is for there to be at least one exception: that is, we need there to exist a prime number that is even. In other words, the negation of the above statement, again in two forms, is this.

Some prime number is even.

$\exists p\in P\ \ p$ is even.

The general rule here is that if you ever have a statement of the form

$\forall x\in X\ \ Q(x)$

then its negation is

$\exists x\in X\ \ \neg Q(x)$

Here $Q$ is some statement about things like x, and $Q(x)$ is what you get when you apply $Q$ to $x$ in particular. Perhaps I can say this a bit more wordily. If you ever have a statement of the form

For every $x$ in $X,$ fact F holds for x.

then its negation will be

There is an $x$ in $X$ for which fact F does not hold.

In the case of the primes-being-odd example, the original statement was false and its negation was true (since 2 is a prime).

If you have read the post on NOT, you may remember a general rule that I mentioned: that if you negate something strong you get something weak, and vice versa. That applied in the example above. The statement, “Every prime is odd,” is strong because it is telling us about all primes. (The fact that it is false is neither here nor there. It is both strong and false.) We therefore expect its negation to be weak, and indeed that is the case: it merely tells us that at least one prime has a certain property (that of not being odd). In principle there might be just one non-odd prime with all the rest being odd, and the statement would still be true. Oh, and hang on … that is actually the case.

There are therefore no prizes for guessing what happens when you negate a statement that begins with an existential quantifier. You should expect something strong, and something strong is indeed what you get. Let’s take a non-mathematical example.

Someone in the world is over 125 years old.

Putting that in symbolic form gives us this. I’ll let $H$ stand for the set of all living human beings and I’ll write $h$ for a typical element of $H$ (that is, a typical living human being).

$\exists h\in H\ \ h$ is over 125 years old.

For that to be false, there cannot be a single living human being who is over 125 years old. That is, for every living human being $h,$ $h$ is not over 125 years old.

$\forall h\in H\ \ h$ is not over 125 years old.

In general, the rule is just like the “for all” rule but with the quantifiers the other way round. That is, the negation of

$\exists x\in X\ Q(x)$

$\forall x\in X\ \neg Q(x)$

Going back to the example about very old people, perhaps you will object that the statement that there exists somebody who is over 125 years old is not that weak after all, since being over 125 years old is so amazingly unexpected. That’s a reasonable point, so let’s take the sentence apart a little. The statement, “ $h$ is over 125 years old,” is indeed an amazingly strong thing to say about $h.$ However, if we want to dilute that strength as much as we possibly can without going to the homoeopathic extreme of saying nothing at all, then the best we can do is to say that somebody somewhere has exceeded the age of 125, without giving any more information. So the quantifier is weak, but the bit inside the quantifier is strong. When we negate it, we reverse this. Now we are saying that everybody (wow, that’s quite strong) is at most 125 (oh … what we’re actually saying about everybody isn’t that surprising).

Something else that you may have noticed if you are feeling alert is that there is a close parallel between what I have just been discussing and de Morgan’s laws (which are discussed towards the end of my post on the logical connective NOT). Recall that de Morgan’s laws tell us that to negate an AND you turn it into an OR and put the NOT by the statements that were ORed together. That is, $\neg(P$ and $Q)$ becomes $\neg P$ or $\neg Q.$ While I’m at it, let me reveal that the symbols $\wedge$ and $\vee$ are often used for AND and OR. With the help of those, we can write de Morgan’s laws as

$\neg(P\wedge Q)\iff \neg P\vee\neg Q.$

and

$\neg(P\vee Q)\iff \neg P\wedge\neg Q.$

The fact that NOT turns AND into OR and vice versa feels quite like the fact that NOT turns $\forall$ into $\exists$ and vice versa (with the NOT shunted inside in all cases). And we can see why this is if we think of a universal quantifier as an enormous AND and an existential quantifier as an enormous OR. For example, the statement

$\forall p\in P\ \ p$ is odd.

that we considered earlier could be thought of as a concise way of saying this:

2 is odd and 3 is odd and 5 is odd and 7 is odd and 11 is odd and 13 is odd and 17 is odd and 19 is odd and 23 is odd and 29 is odd and 31 is odd and 37 is odd and 41 is odd and 43 is odd and 47 is odd and 53 is odd and …

So when we negate it, we should obtain a concise way of saying this:

2 is even or 3 is even or 5 is even or 7 is even or 11 is even or 13 is even or 17 is even or 19 is even or 23 is even or 29 is even or 31 is even or 37 is even or 41 is even or 43 is even or 47 is even or 53 is even or …

and indeed we do, since

$\exists p\in P\ \ p$ is even.

is saying precisely that.

Similarly, the statement that somebody in the world is at least 125 years old is shorthand for, “I am at least 125 years old or you are at least 125 years old or Lord Rees of Ludlow is at least 125 years old or George Osborne is at least 125 years old or Cheryl Cole is at least 125 years old or Andy Murray is at least 125 years old or the younger son of the people who used to live in the house next door until a few years ago is at least 125 years old or …” You get the idea.

Negating a statement that begins with several quantifiers.

Right, that’s single quantifiers dealt with. But what happens if we’ve got a more complicated sentence like the definition of convergence that was discussed in the post on quantifiers? That was as follows.

$\forall \epsilon>0\ \ \exists N\in\mathbb{N}\ \ \forall n\geq N\ \ |a_n-a|<\epsilon.$

If you still feel that you don’t really understand this sentence, that’s OK. In fact, it’s almost better than if you do understand it, since then you really will see just how mechanical it is to negate statements that involve quantifiers.

The first thing to understand is that there is an implicit bracketing going on. We could if we wanted write the statement as follows.

$\forall \epsilon>0\ \ (\exists N\in\mathbb{N}\ \ \forall n\geq N\ \ |a_n-a|<\epsilon).$

In other words, we could think of it as saying, “For every $\epsilon$ something weird happens.” If you don’t find it weird, that’s not a problem — what matters is that we’ve got some statement that involves $\epsilon.$ (In theory it doesn’t even have to involve $\epsilon,$ but if it didn’t then it would be a bit weird. It would be like saying, “For every prime number the president of the United States is Barack Obama.” That’s a true statement, but the role of prime numbers is a bit puzzling.)

But now we have reduced the task to something we know how to do. If we want to negate a statement, the first step is to put the whole statement in brackets and stick a $\neg$ on the front. In our case, we get the following.

$\neg(\forall \epsilon>0\ \ (\exists N\in\mathbb{N}\ \ \forall n\geq N\ \ |a_n-a|<\epsilon)).$

Now we use the rule that we can change $\neg\forall$ into $\exists\neg.$ That is, to negate a “for every” you can change it to “there exists” and bring the negation inside. Doing that here we get the following.

$\exists \epsilon>0\ \ \neg(\exists N\in\mathbb{N}\ \ \forall n\geq N\ \ |a_n-a|<\epsilon)).$

So far all we’ve done is apply the rule that works with a single quantifier, and completely ignored what’s in the inner set of brackets. But now if we stop ignoring that, we see that we’ve still got a sentence with quantifiers that needs negating. What can we do?

Presumably you’ve spotted that we can just repeat the process. We are in exactly the situation we were in before (a “not” outside some quantifiers) so we can do exactly the same thing (make the “not” and the outer quantifier switch places, and turn the outer quantifier into the other type). I won’t give all the gory details. I’ll just say that you can bring the NOT past all the quantifiers as long as you swap them round. The result of doing that is the following.

$\exists \epsilon>0\ \ \forall N\in\mathbb{N}\ \ \exists n\geq N\ \ \neg(|a_n-a|<\epsilon).$

It remains to negate the bit right inside that doesn’t involve quantifiers. Doing that gives us the following statement.

$\exists \epsilon>0\ \ \forall N\in\mathbb{N}\ \ \exists n\geq N\ \ |a_n-a|\geq\epsilon.$

Here I’m using the rule that negating < turns it into $\geq.$ (Similarly, negating > turns it into $\leq$ .) Note that strict inequalities becomes non-strict ones, which is yet another example of strong statements becoming weak ones.

Negating implications.

There’s one other thing you need to know if you want to carry out the technique just described, which is how to negate a statement of the form $P\implies Q.$ Consider, for example, the following statement: every prime of the form $4m+1$ can be written as a sum of two squares. In a more symbolic form, we might represent this as follows.

$\forall p\in P\ \ (p$ is of the form $4m+1\ \implies\ p$ can be written as a sum of two squares).

As a first step towards negating this, we do the trick discussed above, flipping all the quantifiers (in this case only one), which gives us this.

$\exists p\in P\ \ \neg(p$ is of the form $4m+1\ \implies\ p$ can be written as a sum of two squares).

The question is, what do we do now? We’ve got a NOT outside a statement of the form $P\implies Q:$ how do we simplify it further?

Let’s apply a few principles that I’ve been going on about. The first is that if you want to understand a negation, or check whether what you’ve claimed is a negation really is a negation, you should always ask yourself the question, “What needs to be true for this statement to be false?” So let’s do that here. What needs to be true for it not to be the case that if $p$ is of the form $4m+1$ then $p$ can be written as a sum of two squares? And to answer that question we go back further to the principle that says that the only thing that can make an implication $P\implies Q$ false is if $P$ is true and $Q$ is false. So there’s the answer handed to us on a plate. It tells us that the only way for

$p$ is of the form $4m+1\ \implies\ p$ can be written as a sum of two squares

to be false is if $p$ is of the form $4m+1$ but $p$ cannot be written as a sum of two squares. So now we’ve completed our negation. It reads as follows.

$\exists p\in P\ \ p$ is of the form $4m+1\$ and $p$ cannot be written as a sum of two squares).

By the way, it is a famous theorem that a prime can be written as a sum of two squares if and only if it is equal to 2 or is of the form $4m+1$ for some positive integer $m.$ We knew in advance that precisely one out of the original statement and its negation had to be true. It happens to be the original statement that is true and the negation that is false.

Do implications need quantifiers?

There’s a small point in there that confuses some people (including me when I was an undergraduate). What does the statement

$p$ is of the form $4m+1\ \implies\ p$ can be written as a sum of two squares

mean? A very natural way of reading it is as a general statement about primes $p$ (the context making it clear that we are talking about primes here). In other words, it sort of feels as though this statement is saying that every prime $p$ that can be written in the form $4m+1$ can also be written as a sum of two squares. As I discussed at some length in my post about IMPLIES, we think about properties. In this case, we think of the property is-of-the-form- $4m+1$ as implying the property is-expressible-as-a-sum-of-two-squares, but it is much cleaner to write

$p$ is of the form $4m+1\ \implies\ p$ can be written as a sum of two squares

and simply understand that $p$ is an arbitrary prime than it is to write something like

(is of the form $4m+1$ ) implies (can be written as a sum of two squares) when applied to primes

However, my actual interpretation of “implies” when I was analysing the sentence and its negation was not the property interpretation but the truth-value interpretation. For the purposes of the above statement I was thinking of $p$ as fixed (but unknown) and the “implies” symbol was merely telling me that for that fixed $p$ it was not the case that the left-hand side was true and the right-hand side false. Only after I stuck $\forall p\in P$ on the outside did that become a general statement about the primes. To avoid confusion it’s probably best to stick to this convention. And if you find it hard to hold the entire convention and its explanation in your head, then a simpler rule of thumb may perhaps suffice, which is

If in doubt, put in the quantifier.

It is quite hard to avoid all confusion on this score, because people do say things like this. “Let us fix a prime $p$ in the set $A.$ Since all elements of $A$ leave a remainder of 1 when you divide by 4, this implies, by a theorem of Fermat, that $p$ can be written as a sum of two squares.” From the way this sentence is written, it looks as though the implication is

( $p$ is prime and $p\in A$ ) implies ( $p$ can be written as a sum of two squares)

However, it is implicit in the discussion that the $p$ in question is not genuinely fixed. If you asked the person who was talking, “You’ve just said you fixed $p$ . So can you tell us what prime you’re talking about please?” you would get short shrift. When we say that we have “fixed” $p$ it is a sort of lie: actually we are talking about an arbitrary, general $p,$ which is another way of saying that we are talking about all $p$ . So the reason that the confusion occurs is that there is a very useful informal way of talking that hides the quantifiers. It’s often fine to do that, just as it is often fine to wear jeans. But you don’t wear jeans at a black-tie dinner, and you don’t leave out the quantifiers when you are writing out a proof carefully (and at this early stage you should be careful with all your proofs).

To show the sort of confusion that can arise if you disregard this advice, let’s go back to the definition of convergence. Recall that that was the following. I’ll give a slightly wordy version.

For every $\epsilon>0$ there exists a positive integer $N$ such that for every $n\geq N$ $|a_n-a|<\epsilon.$

Suppose we decided to write it instead like this.

For every $\epsilon>0$ there exists a positive integer $N$ such that $n\geq N$ implies that $|a_n-a|<\epsilon$ .

It’s not that hard to see what that second formulation means: the word “implies” has its “property” sense, and is telling us that being at least $N$ guarantees being far enough along in the sequence to be within $\epsilon$ of $a.$ However, this mix of formality and informality (jeans at the black-tie dinner) is dangerous. Suppose, for instance, that we decide to negate the sentence in its second form. Applying the mechanical procedure, we might begin by getting to this.

There exists some $\epsilon>0$ such that for every $N\in\mathbb{N}$ NOT ( $n\geq N$ implies that $|a_n-a|<\epsilon).$

Our remaining task is to negate the bit in brackets. Well, we say, the only way that can fail is if $n\geq N$ and $|a_n-a|\geq\epsilon.$ So we might write this.

There exists some $\epsilon>0$ such that for every $N\in\mathbb{N},$ $n\geq N$ and $|a_n-a|\geq\epsilon.$

However, this doesn’t make sense. What is $n$ ? It’s not at all clear what the above sentence means. The mistake was to treat the statement “ $n\geq N$ implies that $|a_n-a|<\epsilon$ ” as though it were referring to a single $n$ and using the truth-value notion of “implies”, when in fact it was an informal way of expressing the general statement

For every positive integer $n$ , if $n\geq N$ then $|a_n-a|<\epsilon.$

If we include the quantifier, then we will not make this mistake. Instead, we will write the correct negation, which is

There exists some $\epsilon>0$ such that for every $N\in\mathbb{N}$ there exists $n\geq N$ such that $n\geq N$ and $|a_n-a|\geq\epsilon.$

This entry was posted on October 2, 2011 at 10:37 am and is filed under Basic logic, Cambridge teaching. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

15 Responses to “Basic logic — relationships between statements — negation”

Christian Says:
October 2, 2011 at 12:06 pm | Reply
It seems to me that when you write that we knew “in advance” that either the statement of Fermat’s two-square-theorem or its negation had to be true, you are already committing yourself to a very weak form of platonism. The reason for bringing this up is that though I’m entirely fine with such a view, I got the impression a few posts earlier that you wanted to avoid appealing to any form of platonisms in this series of posts.

By the way, I also felt that your cautious wording concerning “some people” who might find it conveivable that Goldbachs conjecture could be true without there being any particular reason for it has been phrased exactly as it is so as to avoid any personal commitment to platonism.
- gowers Says:
  October 2, 2011 at 3:11 pm
  That’s an interesting comment and it reflects the fact that I have two different hats. One is my philosophical hat: I am not a Platonist and do not, for example, think that there has to be a fact of the matter about the truth or otherwise of CH. The other is my everyday mathematical hat, where I’m perfectly happy to reason using the most classical of classical logic. The second is my main hat for these posts, since classical logic seems entirely appropriate for the kinds of statements that are included in the first year of the Cambridge Mathematical Tripos. The advice I would give to undergraduates is to learn to reason classically and then worry about the philosophical side only later and only if it interests them.
Jack Says:
October 2, 2011 at 7:12 pm | Reply
“If you have read the post on negation, you may remember a general rule that I mentioned…”

I guess you mean “If you have read the post on ‘NOT’, you may remember a general rule that I mentioned…”🙂

Oops — thanks. Changed now.
Chris Purcell Says:
October 2, 2011 at 10:27 pm | Reply
I’m getting the weird LaTeX problem mentioned on earlier posts. I’m seeing:

You’ve just said you fixed _np_ So can you tell us what prime you’re talking about please?” you would get short shrift. When we say that we have “fixed” _p_ it is a sort of lie: actually we are talking about an arbitrary, general _p_ which is another way of saying that we are talking about all _np_

As before, I think the problem is your latex interpreter is translating a final period to an initial “n”. No idea why.

Note: If you’re not seeing it yourself, try with Chrome. It may be for instance that WordPress is delivering correct Unicode to your browser and falling back to an incorrect image in my Chrome.
- gowers Says:
  October 2, 2011 at 10:41 pm
  I think I’ll have to stop putting full stops inside my LaTeX, which is annoying as it means that some of them will no longer go on the same line as the symbol they follow.
  
  Oddly enough, although most of the time I don’t see the problem, there was one time when I saw the AO that resulted from B with a full stop after it in LaTeX. Come to think of it, perhaps that was on a different computer and different browser, in which case it wouldn’t have been so odd after all. I can’t remember whether it was.
- Chris Purcell Says:
  October 3, 2011 at 9:20 pm
  What browser/OS do you normally use?
- gowers Says:
  October 3, 2011 at 10:50 pm
  Safari. The problem really does seem to be intermittent for me.
Alireza Says:
October 3, 2011 at 6:52 am | Reply
First: I am lucky that I am teaching a similar course to your posts! Thanks for the posts!

Second: the book that I am using is a bit sloppy. At the beginning it tries to avoid using quantifiers! As a result some confusions arises. For instance it gives the following exercise:

” Is the following statement true or false?
(n^2-n-2=0 implies n=2) or (n^2-n-2=0 implies n=-1)”

As you can see no quantifiers are used. But I think it is a good example on how important it is to write the quantifiers at the right place:

(for any n, n^2-n-2=0 implies n=2) or (for any n, n^2-n-2=0 implies n=-1) is false.

For any n, ((n^2-n-2=0 implies n=2) or (n^2-n-2=0 implies n=-1)) is true.
Nick Says:
October 3, 2011 at 1:59 pm | Reply
I understand Christopher Zeeman used to present this to first-year undergraduates as a game: at each ∀x, imagine someone challenging you with a value for x (so it gets fixed but by someone else); at each ∃y, you must choose a value for y, and, at the end of all the quantifiers, you must show that the remaining statement holds with those values. A proof of the entire statement can then be seen simply as a strategy for always winning the game.
- gowers Says:
  October 3, 2011 at 2:34 pm
  I’ve tried that too. In fact, I have even gone as far as to play the game with a room full of people I’m lecturing to. I very much like the idea in theory but I’m not sure I’ve ever managed to help anyone with that approach. It’s quite easy to get people to see who has a winning strategy (especially if I make sure that I’m the one with the winning strategy, so they get to feel indignant about it), but not so easy to get them to understand the link between that and the original statement with mixed quantifiers — unless they’ve got a pretty good understanding already.
- Richard Baron Says:
  October 3, 2011 at 6:56 pm
  The winning strategy approach is fun, but one needs to get any negation signs within the string of quantifiers out to the front first, otherwise it gets seriously confusing.
  
  I have tried something that is, I think, equivalent to the winning strategy approach. It is outlined on pages 53 and 54 of the document linked below, with some prefatory remarks on pages 50 and 51:
  
  http://www.rbphilo.com/intrologic.pdf
  
  These notes are for budding philosophers who are not necessarily mathematical, so they assume that we have a specific universe in mind, which the students will almost certainly think of as finite, and that each object has been labelled with a constant.
Injections, surjections and all that « Gowers's Weblog Says:
October 11, 2011 at 11:36 am | Reply
[…] the mechanical rules set out in the post on negation, we obtain the negation, which is […]
Chris Kuhn Says:
October 20, 2011 at 2:04 am | Reply
I stumbled upon this thanks to Google’s e-reader. That said, I have been quite enjoying your posts. However, I have found that when explaining things it is helpful to give both the logical notated statement and the same statement again in English. You seem to give just one or the other. While I’m able to follow, others may not be able to.

I’m glad you’re writing this. It has been a great refresher for me.
Why can negation pass through multiple quantifiers? [Chartrand P52-53, Velleman P65] - MathHub Says:
March 20, 2016 at 10:01 am | Reply
[…] I’m mindful of the Quantifier Negation Laws and Negating a statement that … several quantifiers. […]
Karthik Nayak Says:
May 3, 2016 at 7:15 pm | Reply
can you please provide me with the expression for the negation of an implication like what is ~(PQ) equivalent to?

Gowers's Weblog

Basic logic — relationships between statements — negation

Share this:

Like this:

Related

15 Responses to “Basic logic — relationships between statements — negation”

Leave a Reply Cancel reply