When I started writing about basic logic, I thought I was going to do the whole lot in one post. I’m quite taken aback by how long it has taken me just to deal with AND, OR, NOT and IMPLIES, because I thought that connectives were the easy part.
Anyway, I’ve finally got on to quantifiers, which are ubiquitous in advanced mathematics and which often cause difficulty to those beginning a university course. A linguist would say that there are many quantifiers, but in mathematics we normally make do with just two, namely “for all” and “there exists”, which are often written using the symbols and
(If it offends you that the A of “all” is reflected in a horizontal axis and the E of “exists” is reflected in a vertical axis, then help is at hand: they are both obtained by means of a half turn.)
Let me begin this discussion with a list of mathematical definitions that involve quantifiers. Some will be familiar to you, and others less so.
1. A positive integer is composite if there exist positive integers
and
both greater than 1, such that
2. An matrix
is invertible if there exists an
matrix
such that
(Here
is the
identity matrix.)
3. A binary operation on a set A is commutative if for every
and for every
4. A function from a set
to a set
is a surjection if for every
there exists
such that
5. A set of real numbers is dense if for every real number
and for every
there exists a real number
such that
and
I have put those in approximately ascending order of difficulty. To see how such a definition comes about, let us take the last of them. It is a familiar and useful property of the rational numbers (that is, numbers that can be written as fractions) that they “appear everywhere”. This property can be expressed in a number of ways. One is to say that whenever and
are real numbers and
there must be at least one rational number
that lies between them. Another way of saying it is that every real number can be arbitrarily well approximated by rationals.
Let’s try to turn those two thoughts into precise definitions. But before we do so, I would like to draw attention to a number of words that should alert you to the possible presence of , or a universal quantifier, as it is sometimes known. A few examples are “whenever”, “always”, “every”, and “each”. For each one of these words I’ll give an example of a sentence that contains it. Then I’ll translate those sentences into a more mathematical style using a universal quantifier.
Now the translations.
There are other words and phrases that suggest the lurking presence of or an existential quantifier. They are things like “there is”, “for some”, “some”, “at least one”, “you can find”. I’ll content myself with just one example this time.
This could be translated as follows.
You might want to argue that the word “cars” in the first sentence implies that more than one car runs on electricity. If that bothers you, here’s another example. Suppose I receive an email and react by saying, “Somebody likes me.” The meaning there (if you are rather literal-minded and take my words at face value) is
Creating mathematical statements that involve quantifiers.
Right, let’s see what we can do with this statement:
I’m going to use symbols this time. The word “whenever” alerts me to a universal quantifier. Indeed, the phrase “Whenever and
are real numbers” can be translated into
before we even look at the rest of the sentence. “With
is then a condition that needs to be satisfied for the rest of the sentence to apply. “There is some” now looks suspiciously like an existential quantifier, and it is: we translate “there is some rational number
” into the symbolic form
Finally, “that” is referring back to the number
so we are saying that
lies between
and
which we can put more mathematically by saying
Putting that all together gives us this.
To read that sentence, read as “for every” or “for each” (or if you like, “for all” but that sounds somehow less idiomatic), read
as “in”, read
as “the reals”, read “
” as “if
, then “, read
as “there exists”, read
as “the rationals”, and read
as “is less than”. So what you would actually say when reading those symbols is this.
As you will have deduced from that, is the conventional symbol for the set of real numbers and
is the symbol for the set of rational numbers. We also have
for the set of natural numbers (or positive integers),
for the set of all integers, and
for the set of complex numbers.
What about the definition of “dense” in terms of arbitrarily good approximation? The informal definition was this.
We can make a start on this by turning the “every” into a proper quantifier. That gives us this.
So now our problem is reduced to finding a formal way of saying that x can be arbitrarily well approximated by rationals. What does that mean? It means this: however well you want me to approximate x by a rational number, I can do it. Now the word “however” contains “ever” within it. Could this be hinting at a universal quantifier? Yes it could. It is saying something like, “Give me any level of accuracy you want,” which contains the word “any”, a real giveaway. Having said that, the word “any” is a bit problematic because sometimes it replaces an existential quantifier, as it does for instance in the sentence, “If there is any reason to go, I’ll happily go.” The usual advice, with which I concur, is to keep “any”, “anything”, “anywhere”, etc. out of your mathematical writing.
Anyhow, we can avoid the word “any” by going further and saying, “For every level of accuracy that can be specified.” To clarify this, let us think what “level of accuracy” means. When I approximate a real number by a rational number, I am trying to pick a rational number that is close to the real number. And the accuracy of the approximation is naturally measured by the difference. So to specify a level of accuracy is to provide a small positive number and insist that the difference should be less than that number. For historical reasons, mathematicians like the Greek letters and
for this purpose. So “for every level of accuracy” ends up as the rather more straightforward “for every
“.
Where have we got to now? We are here.
Now the word “can” is another one that sometimes conceals an existential quantifier. For example, “It can be cold in Cambridge,” means that amongst the possibilities for the weather in Cambridge there exists at least one cold one. So we could take the hint from that and rewrite the above sentence as follows.
And now, to finish off, we just have to remember what we meant by “approximates to within “. We end up with statement 5 from earlier on.
In symbols, this would be as follows.
By the way, a quick piece of stylistic advice. Some people, when they first come across the symbols and
get too keen on them and start using them in the middle of ordinary text, writing sentences like this: “And therefore
we know that
is at most M.” That looks awful. You should either write something like, “And therefore for every
in the set
we know that
is at most M,” or you should write something more like this.
“And therefore,
”
In general, don’t overdo the symbols. And if you do use them (in order, say, to avoid an excessively wordy sentence), then don’t mix them up with words too much. A good rule of thumb there is to make sure that each symbol is part of a bunch of words that can stand reasonably well on their own. For example, the following mixture isn’t too bad:
But these are unspeakably awful.
I leave it to you to come up with nicer formulations of the above four sentences. One final exhortation: please don’t ever use the symbol to stand for the word “every”. If you’re now thinking “But isn’t that what it means?” then I’m glad I brought this up. It doesn’t mean “every”. It means “for every”. That kind of distinction really matters in mathematics.
Understanding mathematical statements that contain quantifiers.
I’ve discussed how you can take a slightly vague English statement and convert it into a precise formal mathematical one. It’s tempting to give many more examples, but I’d rather save that up for the actual definitions you will encounter. So if one example isn’t enough for you, be patient and there will be more.
But what about the reverse process? Suppose you are presented with a statement like this.
If you haven’t seen that before, you will probably find it pretty opaque. In fact, some people find it pretty opaque even if they have seen it before. So what can one do to make sense of it?
Well, most people find that the more quantifiers they have to cope with, the harder it gets. So a good technique for understanding a statement such as the above is to build up gradually. Let me illustrate how this can be done. (What I’m about to show is meant to be something you can do for yourself with other definitions. The hope would be that once you’ve gone through the process with a few of them you will get used to them and not need to go through the process any more.)
To make things really easy, let’s start with no quantifiers at all. That is, let’s start with the quantifier-free “heart” of the statement, which is
This isn’t hard to understand: it’s saying that the nth term of the sequence differs from by less than
OK, now let’s add a quantifier. The one thing to remember is that we’ll add the quantifier furthest to the right. In other words, we start at the end of the entire statement (this we’ve just done) and work backwards.
That’s got one quantifier, but it’s still not too bad. It’s simply saying that every term of the sequence differs by at most from
Or rather, it would be if it weren’t for that little condition that
So I lied. It isn’t quite saying that every term differs by at most
It’s saying that every term differs by at most
as long as we’ve got to
or beyond.
Right, let’s add a second quantifier.
What is the effect of that “” on the previous sentence? Well, the previous sentence said that
is within
of
as long as we’ve got past
But it gave us no idea what
was. And in fact
isn’t really a fixed number. All we know is that there is some
that makes that statement true. That is, there is some
such that
stays within
of
once
gets to
or beyond.
Note that I hid the “for all” quantifier inside the word “stays” there. I used the word “stays” to mean “is for evermore” and the “ever” in “evermore” is a very clear hint of a universal quantifier. This informal language isn’t part of mathematics and should be kept out of proofs, but it is a useful aid to thought.
Actually, there is another piece of informal language that I find useful for this specific situation where we have I think of the
as saying “eventually” (which could also be “from some point onwards” if you want to make the
stick out a bit more clearly) and the
as saying “always”. So this part of the statement is saying
I quite like the word “stays” too:
We’ve still got a quantifier to go. What is ? Again, it isn’t something fixed. Let’s have a look at the whole statement.
We now reach something that’s a bit less easy to put into informal language. Here’s an attempt.
In general, if you ever see a statement that begins and ends with something being less than
the general idea is that however small you want that something to be … complicated stuff … you can get it to be that small. (Of course, the letter doesn’t have to be
Another popular choice is
)
It would be remiss of me not to mention that the definition we have just picked apart is the formal definition of the concept of convergence. You will find over the next few weeks that if you see the sentence
then to work with it you need to translate it into the formal statement we’ve just looked at with its three quantifiers. That’s an oversimplification because it applies only when we are reasoning from first principles. Once you have met the definition of convergence, you will prove simple facts about it such as that if converges to
and
converges to
then
converges to
These facts can then be used to prove facts that involve convergence without writing out the definition in full. However, when you’re just starting, and sometimes later on too, you do need to write out the definition. So one thing you have to do is learn these definitions — off by heart. If you don’t, you might just as well give up. But if you follow some of the tips above, you may find that you don’t have to learn the definitions as if they were a random jumble of symbols. Ideally, you will develop enough understanding to have a good intuitive picture of what the definition says, and the means to translate that intuitive picture into the formal definition with quantifiers. Another thing you can do is try writing out wrong versions of the definition and seeing why they are wrong. For example, suppose we interchange the first two quantifiers in the definition we’ve been discussing. Then we get the following statement.
That is an unnecessarily complicated way of saying that from some point on all terms of the sequence are equal to (If you don’t immediately see that it saying that, then try carrying out the process I’ve just outlined above. At some point the meaning will jump out at you.)
What I’ve just recommended may sound like hard work; that is because it is. But it isn’t impossibly hard, and time invested at this stage will pay huge dividends later.
I could say plenty more about quantifiers, but I think I’ll hold my fire for now, and discuss them more when they come up in the courses.
September 30, 2011 at 12:16 pm |
Once students have got the idea, and if it is not too great a distraction from proper work, it is fun to ask them to put into symbols:
Everyone loves someone (the order of quantifiers has serious implications)
All drinks must be ordered at the bar (you can run up a large bar tab if you are not careful with this one)
September 30, 2011 at 4:57 pm
Though it is possible for some English sentences (and ever a handful of mathematical sentences) to be nonfirstorderisable, such as the Geach-Kaplan sentence “Some critics admire only one another”. These sentences require either second-order logic (quantifying over predicates, rather than objects) or set theory in order to properly formalise.
Still, this is not a major concern in most of mathematics, as one is usually willing to use the framework of set theory to model such sentences. (There are subtle model-theoretic differences between the set-theoretic formalisation and the second-order logic formalisation, but this is an issue that is primarily of concern to logicians rather than to most mathematicians.)
October 1, 2011 at 3:08 am |
can you write something on Fuzzy logic?
October 1, 2011 at 9:08 am |
When translating the mathematical expressions into English, I like to translate the negations as well, so that students can see things like what you get to pick when finding a counterexample or how to start a proof by contradiction correctly.
October 1, 2011 at 10:17 am
I agree that that’s a good thing to do. In case anyone is wondering why I haven’t mentioned negating sentences with strings of quantifiers, that’s because it’s coming up in the next post, which is on negation.
October 1, 2011 at 2:41 pm |
I noticed that when translating English sentences to logical sentences containing quantifiers, one should take care of sentences like
(the predicates M stands for being an exciting movie and C for having a contrived plot).
is not bound to the existential quantifier. However if one thinks about the sentence, one will notice that the actual meaning is
).
“If an exiting movie exists, it will have a contrived plot.”
I noticed that a lot of students blindly apply the translation rules, ending up with
But this is not correct because the second
“Exciting movies have contrived plots”
and thus it’s a for-all statement (
October 2, 2011 at 9:16 am |
First, of course, such as there is no direct translation word for word from English to Japanese (and reverse), there is also no such translation from English to first order (and reverse). However, I admire you, prof. Gowers, for trying to approximate the impossible, in a way that should be helpful to many math students. (Maybe you should be more explicit in pointing out it is only an approximation, but that’s just my opinion.)
That said, I’d like to point out two things.
First, you have an error in your example “Whenever a,b are real numbers with a less than b…” — you forgot to translate “with” (the precondition that a be less than b). Probably because it is a bit hard to translate into a symbolism you use, when you can either quantify same way over many variables, or quantify with conditions, but usually not both. You can use implication, which will probably confuse things because then you don’t have prenex normal form, you can say “r is between a and b” in a more precise way that doesn’t presume a being less than b, or you can split variables:
“for every a in reals, for every b greater than a, there is…”. But you can’t just leave it as it is.
Second, I strongly recommend you not to use “s.t.” in symbolic sentences. It goes counter to your (excellent) advice not to intermix symbols and words in weak chunks, and trying to defend it as a symbol is very wrong. See 10th comment, point (ii), by David Ullrich, in http://www.mathkb.com/Uwe/Forum.aspx/math/39701/Symbol-for-such-that. In short, just as reverse A doesn’t mean “every” but “for every”, reverse E doesn’t mean “exists” but “exists … such that”. Yes, it’s split, but so is “if … then”.
I know I should be very careful when correcting a Fields medallist about math style, and I know there is a fair bit of tradition in such matters, but I believe this is not only a stylistic question, but also a mathematical one — the same way you feel about “implies” vs. “if … then”. And the tradition is wrong (mathematically).
October 2, 2011 at 9:25 am
I had a policy of avoiding “s.t.”, so the fact that one of them slipped in was an accident. Thanks for pointing that out — I have now removed it.
I decided to go down the implication route in order to correct the other mistake. It’s slightly confusing for the reason you say, but I think it’s reasonably close to how we actually think about that version of the definition. For instance, in a metric space I think we would probably quantify over open balls. And sometimes we sloppily write
in a situation like this.
October 2, 2011 at 9:48 pm
I assume you removed “s.t.” from your first statement in “Creating mathematical statements that involve quantifiers”. Unfortunately, you did not remove it from the _description_ of the statement, which assumes it is still there. (‘read “s. t.” as “such that”’, etc.)
October 2, 2011 at 10:07 pm
Thanks. I hope I’ve finally got it sorted out now.
October 6, 2011 at 10:31 pm |
Davenport and Heintz 1988 proved that quantifier elimination is in fact at least there exists a family n of formulas with n quantifiers of length O n and constant degree such that any quantifier-free formula equivalent to n must involve polynomials of degree and length using ..Basu and Roy 1996 proved that there exists a well-behaved algorithm to decide the truth of a formula x1 xk P1 x1 xk 0 Ps x1 xk 0 where is or with complexity in arithmetic operations sk 1dO k ..
October 7, 2011 at 10:17 am
Is it possible to send this comment again? I think you must have used the “is less than” symbol directly, which often causes trouble because WordPress interprets it as html. So instead you have to type <: except that where I’ve just put a colon you put a semicolon. “Is greater than” is >: — again with a semicolon instead of a colon.
November 8, 2011 at 6:26 am |
Mark Meckes from CWRU brought me here. This post is absolutely brilliant. The amount of care that went into writing this post is way up there with Warren Esty’s Foundations of Logic. Thank you for this excellent resource.
November 8, 2011 at 11:14 pm |
I note that you have not quite followed my “quantifier packaging” approach, which involves giving a name to the intermediate concepts (e.g. “absorption” of sequences by sets). I can think of many possible reasons for this, including the following:
(1) it may be undesirable to introduce non-standard terminology;
(2) the students need to learn to “package” the quantifiers for themselves, and not become dependent on the teachers to do this for them.
(3) If you do introduce new/non-standard terminology, it will only be in a limited number of settings. You want to emphasize that the students should be able to do this for themselves for all multi-quantifier statements.
What are your thoughts here?
Joel
August 5, 2012 at 6:25 pm |
This is a great sequence of posts! One advantage of making your teachings available in this blog format is that they can reach audiences far away in time or distance. (I can only hope the two following short comments will not be deemed inappropriate for having been produced only now, by a faraway reader who is not a native speaker of English.)
In the present post you wrote “We also have $ latex \mathbb{N} $ for the set of natural numbers (or positive integers)”. This would have seemed to me to conflict with what I had assumed to be the usual terminology on natural numbers, positive integers and nonnegative integers. Or does it?
Further, your attempted translation of the statement about convergence of a sequence, “However close you want $ latex a_n $ to be to $ latex a $ eventually it will always be that close”, gave me a somewhat misleading impression that one could have intended to mean a given precise distance, in other words, it gave me the feeling that the expression “that close” could be translated back in such a way that the strict order in the corresponding mathematical statement would be replaced by an equality (which is surely not intended). Maybe writing “be within that distance” instead of “be that close” would do more justice to the original mathematical statement?
August 6, 2012 at 11:02 am
The standard meaning of “natural numbers” in Cambridge is “positive integers”. It’s not a world standard, but I was writing primarily for Cambridge students (though I’m of course delighted if anyone else wants to read the posts). I agree that “at least that close” would have been clearer than “that close”. Having said that, I would note that if I were to say, “Do you think Usain Bolt can run 100m in 9.5 seconds?” it would be obvious that I meant “in under 9.5 seconds” rather than “in exactly 9.5 seconds”. I think this is a similar example.
October 17, 2012 at 12:27 am |
Hi Gowers, Can you please explain what is the difference between saying ‘there doesn’t exist x such that P(x) is true’, and ‘for all x, p(x) is false’?
October 17, 2012 at 10:14 am
There isn’t a difference (or at least, there isn’t in the kind of classical logic that is used for undergraduate mathematics courses and by most working mathematicians).
October 17, 2012 at 5:30 pm |
Is the wrong definition of convergence you gave useful in mathematics? I am trying to make sense of the wrong definition. Is it the ‘for all e’ where the meaning jumps out? Because e>0 and you want the other thing to be less than e, it must be 0 so we conclude that the nth term onwards is a?
November 24, 2016 at 3:42 am |
hey…..
can anyone tell me the applications of Quantifiers in our real life?
kindly plzz tell me
October 26, 2017 at 10:22 am |
[…] https://gowers.wordpress.com/2011/09/30/basic-logic-quantifiers/ […]