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.)
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
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
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.
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