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 is a statement, then “not
“, sometimes written in symbolic form as
is its negation. If
has the form
then the converse of
is the statement
And finally, again if
has the form
the contrapositive is the statement
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 in front of it (putting the whole statement in brackets if it is complicated enough to need it). You can then read
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:
According to what I said above, the negation of that statement is
which can be translated into a more natural sentence in various ways. One possible translation is this.
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.
We can form the negation in the unnatural way as follows.
Suppose we were now to move the “not” to where the main verb is. We would get this:
But that is not the same as saying
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
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 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
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 for the set of all prime numbers.
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.
The general rule here is that if you ever have a statement of the form
then its negation is
Here is some statement about things like x, and
is what you get when you apply
to
in particular. Perhaps I can say this a bit more wordily. If you ever have a statement of the form
then its negation will be
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.
Putting that in symbolic form gives us this. I’ll let stand for the set of all living human beings and I’ll write
for a typical element of
(that is, a typical living human being).
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
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
is
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, “ is over 125 years old,” is indeed an amazingly strong thing to say about
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, and
becomes
or
While I’m at it, let me reveal that the symbols
and
are often used for AND and OR. With the help of those, we can write de Morgan’s laws as
and
The fact that NOT turns AND into OR and vice versa feels quite like the fact that NOT turns into
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
that we considered earlier could be thought of as a concise way of saying this:
So when we negate it, we should obtain a concise way of saying this:
and indeed we do, since
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.
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.
In other words, we could think of it as saying, “For every 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
(In theory it doesn’t even have to involve
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 on the front. In our case, we get the following.
Now we use the rule that we can change into
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.
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.
It remains to negate the bit right inside that doesn’t involve quantifiers. Doing that gives us the following statement.
Here I’m using the rule that negating < turns it into (Similarly, negating > turns it into
.) 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 Consider, for example, the following statement: every prime of the form
can be written as a sum of two squares. In a more symbolic form, we might represent this as follows.
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.
The question is, what do we do now? We’ve got a NOT outside a statement of the form 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 is of the form
then
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
false is if
is true and
is false. So there’s the answer handed to us on a plate. It tells us that the only way for
to be false is if is of the form
but
cannot be written as a sum of two squares. So now we’ve completed our negation. It reads as follows.
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 for some positive integer
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
mean? A very natural way of reading it is as a general statement about primes (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
that can be written in the form
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-
as implying the property is-expressible-as-a-sum-of-two-squares, but it is much cleaner to write
and simply understand that is an arbitrary prime than it is to write something like
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 as fixed (but unknown) and the “implies” symbol was merely telling me that for that fixed
it was not the case that the left-hand side was true and the right-hand side false. Only after I stuck
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
It is quite hard to avoid all confusion on this score, because people do say things like this. “Let us fix a prime in the set
Since all elements of
leave a remainder of 1 when you divide by 4, this implies, by a theorem of Fermat, that
can be written as a sum of two squares.” From the way this sentence is written, it looks as though the implication is
However, it is implicit in the discussion that the in question is not genuinely fixed. If you asked the person who was talking, “You’ve just said you fixed
. So can you tell us what prime you’re talking about please?” you would get short shrift. When we say that we have “fixed”
it is a sort of lie: actually we are talking about an arbitrary, general
which is another way of saying that we are talking about all
. 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.
Suppose we decided to write it instead like this.
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 guarantees being far enough along in the sequence to be within
of
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.
Our remaining task is to negate the bit in brackets. Well, we say, the only way that can fail is if and
So we might write this.
However, this doesn’t make sense. What is ? It’s not at all clear what the above sentence means. The mistake was to treat the statement “
implies that
” as though it were referring to a single
and using the truth-value notion of “implies”, when in fact it was an informal way of expressing the general statement
If we include the quantifier, then we will not make this mistake. Instead, we will write the correct negation, which is
October 2, 2011 at 12:06 pm |
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.
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.
October 2, 2011 at 7:12 pm |
“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.
October 2, 2011 at 10:27 pm |
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.
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.
October 3, 2011 at 9:20 pm
What browser/OS do you normally use?
October 3, 2011 at 10:50 pm
Safari. The problem really does seem to be intermittent for me.
October 3, 2011 at 6:52 am |
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.
October 3, 2011 at 1:59 pm |
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.
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.
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:
Click to access 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.
October 11, 2011 at 11:36 am |
[…] the mechanical rules set out in the post on negation, we obtain the negation, which is […]
October 20, 2011 at 2:04 am |
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.
March 20, 2016 at 10:01 am |
[…] I’m mindful of the Quantifier Negation Laws and Negating a statement that … several quantifiers. […]
May 3, 2016 at 7:15 pm |
can you please provide me with the expression for the negation of an implication like what is ~(PQ) equivalent to?
October 26, 2017 at 7:42 am |
This is very well composed. The blog post was informative to readers who have a good value for articles. We looking ahead for more of the very same. He has detailed each and everything very well and in brief.
October 26, 2017 at 10:17 am |
Many many thanks, Dr. Gowers! It will serve many of mine own students also…
October 26, 2017 at 10:28 am |
[…] https://gowers.wordpress.com/2011/10/02/basic-logic-relationships-between-statements-negation/ […]