Basic logic — quantifiers

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 $\forall$ and $\exists.$ (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 $n$ is composite if there exist positive integers $a$ and $b,$ both greater than 1, such that $ab=n.$

2. An $n\times n$ matrix $A$ is invertible if there exists an $n\times n$ matrix $B$ such that $AB=BA=I_n.$ (Here $I_n$ is the $n\times n$ identity matrix.)

3. A binary operation $\circ$ on a set A is commutative if for every $a\in A$ and for every $b\in A,$ $a\circ b=b\circ a.$

4. A function $f$ from a set $A$ to a set $B$ is a surjection if for every $y\in B$ there exists $x\in A$ such that $f(x)=y.$

5. A set $A$ of real numbers is dense if for every real number $x$ and for every $\epsilon>0$ there exists a real number $a$ such that $a\in A$ and $|a-x|<\epsilon.$

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 $a$ and $b$ are real numbers and $a<b$ there must be at least one rational number $r$ 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 $\forall$ , 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.

Whenever it rains, the grass smells wonderful.

I always believe what my doctor says.

Every country in the EU is having economic difficulties at the moment.

Each picture in the Fitzwilliam museum is worth getting to know.

Now the translations.

For every time t, if it rains at time t then the grass smells wonderful at time t.

For every statement S, if my doctor says S then I believe S.

For every country C, if C belongs to the EU then C is having economic difficulties at the moment.

For every picture P, if P is in the Fitzwilliam museum then P is worth getting to know.

There are other words and phrases that suggest the lurking presence of $\exists,$ 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.

Some cars run on electricity.

This could be translated as follows.

There exists a car C such that C runs on electricity.

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

There exists a person P such that P likes me.

Creating mathematical statements that involve quantifiers.

Right, let’s see what we can do with this statement:

Whenever $a$ and $b$ are real numbers with $a<b$ there is some rational number $r$ that lies between $a$ and $b.$

I’m going to use symbols this time. The word “whenever” alerts me to a universal quantifier. Indeed, the phrase “Whenever $a$ and $b$ are real numbers” can be translated into $\forall a,b\in\mathbb{R}$ before we even look at the rest of the sentence. “With $a<b$ 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 $r$ ” into the symbolic form $\exists r\in\mathbb{Q}.$ Finally, “that” is referring back to the number $r,$ so we are saying that $r$ lies between $a$ and $b,$ which we can put more mathematically by saying $a<r<b.$ Putting that all together gives us this.

$\forall a,b\in\mathbb{R}\ a<b\implies\exists r\in\mathbb{Q}\ \ a<r<b.$

To read that sentence, read $\forall$ as “for every” or “for each” (or if you like, “for all” but that sounds somehow less idiomatic), read $\in$ as “in”, read $\mathbb{R}$ as “the reals”, read “ $a<b\implies$ ” as “if $a<b$ , then “, read $\exists$ as “there exists”, read $\mathbb{Q}$ as “the rationals”, and read $<$ as “is less than”. So what you would actually say when reading those symbols is this.

For every $a, b$ in the reals, if $a<b,$ then there exists r in the rationals such that $a$ is less than $r$ is less than $b.$

As you will have deduced from that, $\mathbb{R}$ is the conventional symbol for the set of real numbers and $\mathbb{Q}$ is the symbol for the set of rational numbers. We also have $\mathbb{N}$ for the set of natural numbers (or positive integers), $\mathbb{Z}$ for the set of all integers, and $\mathbb{C}$ for the set of complex numbers.

What about the definition of “dense” in terms of arbitrarily good approximation? The informal definition was this.

Every real number can be arbitrarily well approximated by rationals.

We can make a start on this by turning the “every” into a proper quantifier. That gives us this.

For every real number x, x can be arbitrarily well approximated by rationals.

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 $\epsilon$ and $\delta$ for this purpose. So “for every level of accuracy” ends up as the rather more straightforward “for every $\epsilon>0$ “.

Where have we got to now? We are here.

For every real number x and for every $\epsilon>0$ , x can be approximated to within $\epsilon$ by a rational number.

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.

For every real number x and for every $\epsilon>0$ , there exists a rational number $r$ such that $r$ approximates $x$ to within $\epsilon.$

And now, to finish off, we just have to remember what we meant by “approximates to within $\epsilon$ “. We end up with statement 5 from earlier on.

For every real number x and for every $\epsilon>0$ , there exists a rational number $r$ such that $|x-r|<\epsilon.$

In symbols, this would be as follows.

$\forall x\in R\ \forall \epsilon>0\ \exists r\in\mathbb{Q}\ \$ $|x-r|<\epsilon.$

By the way, a quick piece of stylistic advice. Some people, when they first come across the symbols $\forall$ and $\exists,$ get too keen on them and start using them in the middle of ordinary text, writing sentences like this: “And therefore $\forall x\in A$ we know that $f(x)$ is at most M.” That looks awful. You should either write something like, “And therefore for every $x$ in the set $A$ we know that $f(x)$ is at most M,” or you should write something more like this.

“And therefore,

$\forall x\in A\ f(x)\leq M.$ ”

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:

Therefore, $x\in B$ whenever $x\in A.$

But these are unspeakably awful.

Therefore, $x\in$ the union of A and B.

Therefore, $x\in B\ \ \forall$ elements $x$ of $A.$

Therefore, $x$ is an element of A, which $\implies$ $x$ is an element of B.

It follows that $\exists x\in A$ that does not belong to B.

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 $\forall$ 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.

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

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

$|a_n-a|<\epsilon.$

This isn’t hard to understand: it’s saying that the nth term of the sequence differs from $a$ by less than $\epsilon.$

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.

$\forall n\geq N\ |a_n-a|<\epsilon.$

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 $\epsilon$ from $a.$ Or rather, it would be if it weren’t for that little condition that $n\geq N.$ So I lied. It isn’t quite saying that every term differs by at most $\epsilon.$ It’s saying that every term differs by at most $\epsilon$ as long as we’ve got to $N$ or beyond.

Right, let’s add a second quantifier.

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

What is the effect of that “ $\exists N$ ” on the previous sentence? Well, the previous sentence said that $a_n$ is within $\epsilon$ of $a$ as long as we’ve got past $N.$ But it gave us no idea what $N$ was. And in fact $N$ isn’t really a fixed number. All we know is that there is some $N$ that makes that statement true. That is, there is some $N$ such that $a_n$ stays within $\epsilon$ of $a$ once $n$ gets to $N$ 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 $\exists N\in\mathbb{N}\ \forall n\geq N.$ I think of the $\exists N$ as saying “eventually” (which could also be “from some point onwards” if you want to make the $\exists$ stick out a bit more clearly) and the $\forall n\geq N$ as saying “always”. So this part of the statement is saying

eventually $a_n$ is always within $\epsilon$ of $a.$

I quite like the word “stays” too:

eventually $a_n$ stays within $\epsilon$ of $a.$

We’ve still got a quantifier to go. What is $\epsilon$ ? Again, it isn’t something fixed. Let’s have a look at the whole statement.

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

We now reach something that’s a bit less easy to put into informal language. Here’s an attempt.

However close you want $a_n$ to be to $a,$ eventually it will always be that close.

In general, if you ever see a statement that begins $\forall \epsilon>0$ and ends with something being less than $\epsilon,$ 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 $\epsilon.$ Another popular choice is $\delta.$ )

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

$(a_n)$ converges to $a.$

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 $a_n$ converges to $a$ and $b_n$ converges to $b,$ then $a_n+b_n$ converges to $a+b.$ 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.

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

That is an unnecessarily complicated way of saying that from some point on all terms of the sequence are equal to $a.$ (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.

This entry was posted on September 30, 2011 at 11:25 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.

19 Responses to “Basic logic — quantifiers”

Richard Baron Says:
September 30, 2011 at 12:16 pm | Reply
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)
- Terence Tao Says:
  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.)
Anonymous Says:
October 1, 2011 at 3:08 am | Reply
can you write something on Fuzzy logic?
Jack Says:
October 1, 2011 at 9:08 am | Reply
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.
- gowers Says:
  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.
Florian Says:
October 1, 2011 at 2:41 pm | Reply
I noticed that when translating English sentences to logical sentences containing quantifiers, one should take care of sentences like
“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
$(\exists x: M(x))\Longrightarrow C(x)$ (the predicates M stands for being an exciting movie and C for having a contrived plot).
But this is not correct because the second $x$ is not bound to the existential quantifier. However if one thinks about the sentence, one will notice that the actual meaning is
“Exciting movies have contrived plots”
and thus it’s a for-all statement ( $\forall x: (M(x) \Longrightarrow C(x))$ ).
Veky Says:
October 2, 2011 at 9:16 am | Reply
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).
- gowers Says:
  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 $\forall a<b$ in a situation like this.
- Chris Purcell Says:
  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.)
- gowers Says:
  October 2, 2011 at 10:07 pm
  Thanks. I hope I’ve finally got it sorted out now.
dieta Says:
October 6, 2011 at 10:31 pm | Reply
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 ..
- gowers Says:
  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 &lt: except that where I’ve just put a colon you put a semicolon. “Is greater than” is &gt: — again with a semicolon instead of a colon.
Anonymous Says:
November 8, 2011 at 6:26 am | Reply
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.
Joel Says:
November 8, 2011 at 11:14 pm | Reply
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
Anonymous Says:
August 5, 2012 at 6:25 pm | Reply
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?
- gowers Says:
  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.
johnathan Says:
October 17, 2012 at 12:27 am | Reply
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’?
- gowers Says:
  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).
johnathan Says:
October 17, 2012 at 5:30 pm | Reply
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?

Gowers's Weblog