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