Basic logic — connectives — IMPLIES

I have discussed how the mathematical meanings of the words “and”, “or” and “not” are not quite identical to their ordinary meanings. This is also true of the word “implies”, but rather more so. In fact, unravelling precisely what mathematicians mean by this word is a sufficiently complicated task that I have just decided to jettison an entire post on the subject and start all over again. (Roughly speaking what happened was that I wrote something, wasn’t happy with it for a number of reasons, made several fairly substantial changes, and ended up with something that simply wasn’t what I now feel like writing after having thought quite a bit more about what I want to say. The straw that broke the camel’s back was a comment by Daniel Hill in which he pointed out that “implies” wasn’t, strictly speaking, a connective at all.

I’ll mention a number of fairly subtle distinctions in this post, and you may find that you can’t hold them all in your head. If so, don’t worry about it too much, because you can afford to blur most of the distinctions. There’s just one that is particularly important, which I’ll draw attention to when we get to it.

“Implies” versus “therefore” versus “if … then”.

The three words “implies”, “therefore”, and “if … then” (OK, the third one isn’t a word exactly, but it’s not a phrase either, so I don’t know what to call it) are all connected with the idea that one thing being true makes another thing true. You may have thought of them as all pretty much interchangeable. But are they exactly the same thing?

Some indication that they aren’t quite identical comes from the grammar of the words. Consider the following three sentences.

If it’s 11 o’clock, then I’m supposed to be somewhere else.

It’s 11 o’clock implies I’m supposed to be somewhere else.

It’s 11 o’clock. Therefore, I’m supposed to be somewhere else.

The first one is the most natural of the three. The second doesn’t quite read like a proper English sentence (because it isn’t), and the third, though correct grammatically, somehow doesn’t quite mean the same as the first, which is partly reflected by the fact that it is two sentences rather than one. (I could have used a semicolon instead of the full stop, but a comma would not have been enough.)

Let’s deal with the difference between “Therefore” and “if … then” first. The third formulation starts with the sentence, “It’s 11 o’clock.” Therefore, it is telling us that it’s 11 o’clock. By contrast, the first formulation gives us no indication of whether or not it is 11 o’clock (except perhaps if there is a note of panic in the voice of the person saying the sentence). So we use “therefore” when we establish one fact and then want to say that another fact is a consequence of it, whereas we use “if … then” if we want to convey that the second fact is a consequence of the first without making any judgment about whether the first is true.

How about “implies”? Before I discuss that, let me talk about another distinction, between mathematics and metamathematics. The former consists of statements like “31 is a prime number” or “The angles of a triangle add up to 180”. The latter consists of statements about mathematics rather than of mathematical statements themselves. For example, if I say, “The theorem that the angles of a triangle add up to 180 was known to the Greeks,” then I’m not talking about triangles (except indirectly) but about theorems to do with triangles.

The sort of metamathematics that concerns mathematicians is the sort that discusses properties of mathematical statements (notably whether they are true) and relationships between them (such as whether one implies another). Here are a few metamathematical statements.

“There are infinitely many prime numbers” is true.

The continuum hypothesis cannot be proved using the standard axioms of set theory.

“There are infinitely many prime numbers” implies “There are infinitely many odd numbers”.

The least upper bound axiom implies that every Cauchy sequence converges.

In each of these four sentences I didn’t make mathematical statements. Rather, I referred to mathematical statements. The grammatical reason for this is that the word “implies”, in the English language, is supposed to link two noun phrases. You say that one thing implies another.

A noun phrase, by the way, is, roughly speaking, anything that could function as the subject of a sentence. For instance, “the man I was telling you about yesterday” is a noun phrase, since it functions as the subject of the sentence,

The man I was telling you about yesterday is just about to pass us on his bicycle for the third time.

Other noun phrases in that sentence are “his bicycle” and “the third time”.

Let me write something stupid:

The man I was telling you about yesterday implies his bicycle.

I wrote that because there is an important difference between two kinds of nonsense. The above sentence doesn’t make much sense, because you can’t imply a bicycle. However, it is at least grammatical in a way that

The man I was telling you about yesterday. Therefore, his bicycle.

is not.

All this means that when we use “implies” in ordinary English, we are not connecting statements (because statements are not noun phrases) but talking about statements (because we use noun phrases to refer to statements).

I can think of three ways of turning statements into noun phrases. The first is rather crude: you put inverted commas round it. For example, if I want to do something about the incorrect sentence

It is 11 o’clock implies I am supposed to be somewhere else.

then I could change it to

“It is 11 o’clock” implies “I am supposed to be somewhere else.”

The second method is to come up with some name for the statement. That doesn’t work well here, but let’s have a go.

The mid-morning hypothesis implies the inappropriate personal location scenario.

It works better for mathematical statements with established names such as the Bolzano-Weierstrass theorem.

The third method is to stick “that” or something like “the claim that” in front.

The fact that it is 11 o’clock implies that I am supposed to be somewhere else.

I mentioned above that “implies” is not, strictly speaking, a connective. Why is this? It’s because connectives are used to turn mathematical statements into mathematical statements. For example, we can use “and” to build the statement “ $n$ is prime and $n\geq 100$ ” out of the two statements “ $n$ is prime” and “ $n\geq 100$ “. When we do that, the new statement isn’t referring to the old statements, but rather it contains them.

Unfortunately, as so often with this kind of thing, common mathematical usage is more complicated than the above discussion would suggest. Most people read the “ $\implies$ ” symbol as “implies”. And most people are quite happy to write something like

$x\geq 10\implies x^2\geq 100$

which, according to what I said above, is ungrammatical because “implies” is not linking noun phrases. What I suggest you do here is not worry about this too much: confusion between mathematics and metamathematics is unlikely to be a problem when you are learning about Numbers and Sets and about Groups. If you are inclined to worry, then you could resolve to read a sentence like the above as “If $x\geq 10$ then $x^2\geq 100.$ ” I would also say that the symbol “ $\implies$ ” should in general be used fairly sparingly. In particular, don’t insert it into continuous prose. For instance, don’t write something like, “Therefore $x\in A$ and $A\subset B,$ $\implies x\in B.$ ” Instead, write, “Therefore $x\in A$ and $A\subset B,$ which implies that $x\in B.$ ” (Note that in that last sentence the word “which” functioned as the subject of “implies” and referred back to the statement “ $x\in A$ and $A\subset B$ “.)

Quotation and quasi-quotation.

If you like subtle distinctions that will not matter in your undergraduate mathematical studies, then read on. If you don’t, then feel free to skip this short section.

The distinction I want to draw attention to is between two uses of quotation marks. Just for good measure, let’s look at three different ways of doing something with the sentence, “There are infinitely many primes.”

There are infinitely many primes, but only one of them is even.
“There are infinitely many primes” is a famous theorem of mathematics.
“There are infinitely many primes” is an expression made up of five words.

The first of these sentences is about numbers. As such, it doesn’t use quotation marks. The third sentence is about a linguistic expression. As such, it very definitely requires quotation marks, just as they are needed in the sentence

“Dog” is a noun and “bark” is a verb.

As for the second sentence, it is somewhere in between. It isn’t about numbers, but it’s also not about a linguistic expression. It’s about a mathematical fact. This use of quotation marks is sometimes called quasi-quotation. I won’t say any more but will instead refer you to the relevant Wikipedia article if you are interested. [Thanks to Mohan Ganesalingam for drawing my attention to it.]

Yes, but what do “if … then” and “implies” mean?

I’ve just spent rather a long time discussing the grammar of “implies”, “therefore” and “if … then” and said almost nothing about what they actually mean. To avoid confusion, I’m mainly going to discuss “if … then” since there is no doubt that that really is a connective. But sometimes I’m going to want to do what I’ve done in previous posts and use the letters P and Q to stand for statements, and here, unfortunately, there is a danger of the confusion creeping back. In particular, if one is being careful about it then one needs to be clear what “standing for a statement” actually means.

Is it something like the relationship between “The Riemann hypothesis” and “Every non-trivial zero of the Riemann zeta function has real part 1/2”? That is, are P and Q names for some statements? Not exactly, because we want to be able to make sense of the expression $P\wedge Q$ (recall that $\wedge$ is a symbolic way of writing “and”) and the word “and” links statements rather than names. (You don’t, for example, say, “The Riemann hypothesis and Fermat’s Last Theorem” if you want to assert that the Riemann hypothesis and Fermat’s Last Theorem are both true.) So we should think of P and Q as statements themselves — it’s just that they are unknown statements.

But in that case we shouldn’t be allowed to write $P\implies Q,$ or at least not if $\implies$ means “implies”. But that’s just too bad. I’m going to write it, and if you’re worried about it then read “ $P\implies Q$ ” as “if P then Q”. But actually what I recommend is not worrying about it and just knowing in your heart of hearts that it would be easy to replace what you are saying by something that is strictly correct if there was ever any danger of confusion.

So let us pause, take a deep breath, allow everything I’ve written so far to slip comfortably into the back of our minds, and turn to the question of what “if … then” and “implies” actually mean. And the answer is rather peculiar. In everyday English, when we use one of these words, we are trying to explain that there is a link between the two statements we are relating (either directly or by referring to them). For example, if I say, “If we continue to emit carbon dioxide into the atmosphere at the current rate then sea levels will rise by two metres by 2100,” I am suggesting a causal link between the two.

Let me now give the standard account of what mathematicians mean by “if … then”. Later I shall qualify it considerably — not because I think it is incorrect but because I think it doesn’t give the whole picture and can be unnecessarily off-putting. The standard thing to say is that $P\implies Q$ is true unless $P$ is true and $Q$ is false. That is, if you want to establish that $P\implies Q,$ then the only thing that can go wrong is $P$ being true and $Q$ being false.

A brief interruption: purists will note that I have been inconsistent. If $P$ is a statement rather than something that refers to a statement, then I can’t say “ $P$ is true”. I have to say, “” $P$ ” is true.” Alternatively, I should have said, “ $P\implies Q$ unless $P$ and $\neg Q$ .” Can we agree that I’ll be slightly sloppy here? (If you don’t understand why it’s sloppy, I don’t think it matters.)

Let me illustrate this with a few examples.

If there were weapons of mass destruction in Iraq then pigs can fly.

The Riemann hypothesis implies Fermat’s Last Theorem.

If $n$ is both even and odd, then $n=17.$

If $n$ is a prime not equal to 2, then $n$ is odd.

Of these four statements, the fourth one seems quite reasonable, while the other three are all a bit peculiar. For example, it’s quite obvious that (the recent Pink Floyd stunt notwithstanding) pigs cannot fly. Doesn’t that make the first sentence false? And how can one say that the Riemann hypothesis implies Fermat’s Last Theorem when nobody expects a proof of Fermat’s Last Theorem that uses the Riemann hypothesis? And surely if $n$ is both even and odd, it could just as well be 19. Can it be correct to say that it has to be 17? As for the fourth sentence, it seems fine: if $n$ is a prime not equal to 2, then it cannot have 2 as a factor (or it wouldn’t be prime), so it must indeed be odd.

Well, mathematicians would say that all four statements are true. That’s because the only way “If P then Q” can be false is if P is true and Q is false. You should understand this as a definition of “if … then”. Let’s check the four statements using this definition.

For the first one to be false, we would need there to have been weapons of mass destruction in Iraq and for pigs to be unable to fly. Well, we’ve got the earthbound pigs but there were no weapons of mass destruction in Iraq, so the first statement is true. (Again, this is not some metaphysical claim. It just follows from the way we have chosen to define “if … then”.)

For the second to be false, we would need the Riemann hypothesis to be true and Fermat’s Last Theorem to be false. Well, Andrew Wiles, with help from Richard Taylor, has proved Fermat’s Last Theorem, so it’s not false. So the second statement in the list is true.

As for the third, the only way for that to be false is if $n$ is both even and odd but $n$ is not equal to 17. But no number is both even and odd. Therefore, the third statement is true. The problem about $n$ equalling 19 doesn’t arise because there are no even and odd integers in the first place.

Truth values and “causes”.

There’s something unsatisfactory about the truth-value definition of “if … then” and “implies”. It seems to leave out the idea that one thing can be true because another is true. It would be quite wrong to say, for instance, that Fermat’s Last Theorem is true because the Riemann hypothesis is true.

Fortunately, there is a very close link between the truth-value definition and what I’ll call the causal concept of “if … then”. I’m not going to attempt a precise definition of the causal concept — I’m just referring to the basic idea of one statement’s being a reason for another.

Let’s go back to the one statement that felt reasonable in the list above. It was this.

If $n$ is a prime not equal to 2, then $n$ is odd.

Now comes another somewhat subtle distinction, and this is the one I really care about. What does that statement above actually mean? I think a very natural way of interpreting it is this.

Whenever $n$ is a prime not equal to 2, it is also odd.

In other words, although it looks like a statement about some fixed number $n$ , the fact that we have been told nothing whatsoever about $n$ makes us read it in a slightly different way. We say to ourselves, “Since we’ve been told nothing at all about $n,$ this must be intended as a general statement about an arbitrary $n.$ So what it’s really saying is that if a positive integer has one property — being a prime not equal to 2 — then it has another — being odd.” If we’re thinking about things that way, then it’s rather tempting to say that the property “is a prime not equal to 2” implies the property “is odd”.

What I’ve just suggested is not standard mathematical practice, but in principle it could have been. However, it is incredibly important in mathematics to be completely sure at all times what kinds of objects one is dealing with. I said earlier that “if … then” connects statements and “implies” connects noun phrases that refer to statements. I did not say that either of them connects properties. So if I want to say that one property implies another, then I have to be absolutely clear that this is a different meaning of the word “implies” (even if it is related to the previous one).

OK, so let me be careful. First of all, what is a property? It’s what you get when you take a statement that concerns a variable and you remove that variable. For example, if I take the statement “ $n$ is a perfect square” and remove the variable $n$ from it, I get the property “is a perfect square”. A property is a thing you say about something else. (It’s almost like an adjective, but not quite because of the extra “is”.) If you want to be more formal about it, if you are given a set like the set of all positive integers, a property associated with that set is a function from elements of the set to statements. For example, the property “is prime” takes the number $n$ to the statement “ $n$ is prime”. (It is more conventional to say that all we actually care about is the truth values of these statements. So the property “is prime” takes the value TRUE at each prime number and FALSE at all other numbers. I’ll stick with my unconventional discussion here.)

Now suppose that we have two properties A and B associated with the positive integers. When do we say that A implies B (according to my unconventional definitions)? Well, for each positive integer $n,$ we have a statement $A(n)$ and a statement $B(n).$ I’ll say that $A$ implies $B$ (in the property sense) if for every positive integer $n$ , the statement $A(n)$ implies the statement $B(n)$ (in the truth-value sense). In other words, whenever $A(n)$ is true, so is $B(n),$ and otherwise anything can happen. In the example above, $A$ is the property “is a prime not equal to 2”, $B$ is the property “is odd”, and for each $n,$ $A(n)$ is the statement “ $n$ is a prime not equal to 2″ and $B(n)$ is the statement “ $n$ is odd”. Every time $A(n)$ is true, which it is when $n=3,5,7,11,13,17,19,23,29,31,...$ , so is $B(n).$ This gives us the feeling that the property $A$ “causes” the property $B$ .

Let me go back to the statement that seemed reasonable.

If $n$ is a prime not equal to 2, then $n$ is odd.

It’s important to be careful about what this means. Is it a statement about some specific $n$ ? If so, then we must interpret the “if … then” in the strict truth-value sense. Or is it really a way of saying, “Every prime not equal to 2 is odd”? In that case, it has more of a causal feel to it.

The best way to keep everything clear at all times is not to write the above sentence when you’re really talking about all $n.$ Instead, you can write

For every positive integer $n,$ if $n$ is a prime not equal to 2, then $n$ is odd.

Now, if you pick out just the part of this statement that says, “If $n$ is a prime not equal to 2, then $n$ is odd,” then you have something that must be interpreted in the truth-value sense. But when you apply those truth-value statements to all positive integers $n$ simultaneously, what you end up with is the nice “causal” statement that the property “is a prime not equal to 2” implies the property “is odd”.

A silly deduction and a sensible deduction.

Because there is a sort of causal notion of implication, and because it is in a way what we really care about when doing mathematics, I very much prefer to illustrate the meaning of “implies” or “if … then” with reference to examples that include variables. If I just take two fixed statements like “Margaret Thatcher used to be Prime Minister of the UK” and “there was recently a tsunami in Japan” and tell you that, despite the lack of any obvious relationship between them, the first statement implies the second statement because the second statement happens to be true, then it it is clear the notion of implication I am using has nothing to do with one thing being true because another thing is true: not even the most rabidly left-wing person is going to blame the Japanese tsunami on Thatcher’s premiership. But a statement like, “If $x\in A$ then $x\in A\cup B$ ,” is completely reasonable. Moreover, because $x$ is a general element of $A,$ which might be an infinite set, we can’t establish a statement like this by running through all $x$ and checking the truth values of the statements $x\in A$ and $x\in A\cup B.$ Rather, we have to give a proof — that is, an explanation of why $x$ must belong to $A\cup B$ if it belongs to $A.$ Thus, once you start looking at statements with variables, the truth-value notion of implication forces you to look for “reasons” and “causes” so that you can establish lots of truth-value facts at once. (I’m leaving out the possibility here that a statement could in some sense “just happen to be true”. For example, many people take seriously the following possibility. Perhaps the property “is even and at least 4” implies the property “is a sum of two primes” in the sense that no number is even and at least 4 without being a sum of two primes, but perhaps also there isn’t a reason for this — perhaps it just happens to be the case.)

Here’s another illustration of the difference between statements that involve parameters and statements that don’t. Consider the following claim.

If $\sqrt{2}$ is rational then there is an integer that is both even and odd.

I’m going to prove it in two different ways.

Proof 1. $\sqrt{2}$ is irrational, so the statement “ $\sqrt{2}$ is rational” is false, and therefore implies all other statements. In particular, it implies that there is an integer that is both even and odd.

Proof 2. If $\sqrt{2}$ is rational, then we can find positive integers $p$ and $q$ such that $\sqrt{2}=p/q,$ which implies that $2q^2=p^2.$ Let $k$ be the largest integer such that $p^2$ is a multiple of $2^k.$ Since $p^2$ is a perfect square, $k$ must be even. (To see this, just consider the prime factorization of $p.$ ) But $p^2=2q^2,$ and the largest k for which $2q^2$ is a multiple of $2^k$ is odd. (To see this, just consider the prime factorization of $q.$ ) Therefore, $k$ is both even and odd, which proves the result.

Which of these two arguments is more interesting? Undoubtedly the second, since it actually gives us a proof of the irrationality of $\sqrt{2}.$ So is the first argument valid at all? You might object to it on the grounds that it uses without proof the fact that $\sqrt{2}$ is irrational. But we can make the question more interesting as follows. There is (it happens) a different proof of the irrationality of $\sqrt{2}$ that does not involve the statement that some positive integer is both even and odd. What if we used that argument, concluded that “ $\sqrt{2}$ is rational” was false, and then went on to deduce “there exists an integer that is both even and odd” in the way that argument 1 does above. Would that be a valid deduction?

I think the answer has to be yes, but it is not an interestingly valid deduction. It is not showing that the irrationality of $\sqrt{2}$ is in any way caused by a contradiction that involves parity, since we deduced that from another, and unrelated, false statement.

If we think of implication as primarily something we apply to statements with parameters, and therefore indirectly and in a different sense to properties, then our starting point is not the statement “ $\sqrt{2}$ is irrational” but rather the statement “ $\sqrt{2}=p/q$ “. And our conclusion, that there exists an integer that is both even and odd, is deduced from the more precise (and informative) statement, “the highest $k$ such that $p^2$ is a multiple of $2^k$ is both even and odd”.

As a final remark about the above example, which allows me to emphasize a point I have already made, suppose that I start a proof of the irrationality of $\sqrt{2}$ by writing,

$\sqrt{2}=p/q\implies p^2=2q^2.$

What I am really saying is that whatever $p$ and $q$ might be, if $\sqrt{2}=p/q,$ then $p^2=2q^2.$ In other words, although it looks as though I’m talking about a specific pair $p$ and $q,$ in fact I’m making a general deduction.

What’s good about the usual convention concerning “if … then” and “implies”?

I think I have partially answered this question by pointing out that when we consider statements with parameters then the truth-value meaning of “implies” feels a lot closer to the more intuitive “causal” meaning of “implies”. However, the agreement isn’t total. One of the “silly” examples from early in this post was this.

If $n$ is both even and odd then $n=17.$

This looks odd, because although we know that $n$ can’t be both even and odd, we also feel that if $n$ were even or odd, there would be nothing about that fact that steered $n$ towards the number 17 as opposed to any other number. I can’t deny the feeling of oddness. All I can say is that the hypothetical situation never arises because the hypothesis, that $n$ is even and odd, is impossible.

What I can do, however, is explain why I don’t want to try to find a different convention that would make this statement false. I don’t want to do that because it would force me to give up some general principles that I like. One of those I have already mentioned:

Property $P$ implies property $Q$ if and only if the set of all $n$ such that $P(n)$ is a subset of the set of all $n$ such that $Q(n).$

I hope you’ll agree that that looks highly reasonable, and we don’t want to start having ugly exceptions to it if we don’t have to.

Here’s another mathematical principle that I think you will also have to agree with.

The empty set is a subset of every other set.

Now let’s apply these two principles. I’m going to let $P$ be the property “is both even and odd” and I’m going to let $Q$ be the property “equals 17”. Then the set of $n$ such that $P(n)$ is the empty set (since no $n$ is both even and odd). The set of $n$ such that $Q(n)$ is the set $\{17\}.$ Since the empty set is a subset of the set $\{17\},$ the first principle tells us that $P(n)$ implies $Q(n).$

To summarize this discussion, the formal mathematical notion of implication is a bit strange, but most of the strangeness disappears if you just look at statements with parameters, which tend to be the statements we care about. Each such statement corresponds to a property of those parameters, and implication of properties is closer to our intuitive notion of one thing “making” another true than implication of statements. Even then there are one or two oddnesses, but these are a small price to pay for the cleanness and precision of the definition and for the fact that it allows us to hold on to some cherished general principles.

An exercise — not to be taken too seriously.

(i) Prove that Borsuk’s conjecture implies the Riemann hypothesis.

(ii) Comment on your proof.

Hint: if you find part (i) difficult, then you are not applying one of the pieces of general study advice I gave in the first post of this series.

This entry was posted on September 28, 2011 at 12:35 pm 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.

33 Responses to “Basic logic — connectives — IMPLIES”

Joseph Perla Says:
September 28, 2011 at 1:36 pm | Reply
You should link the first post in this series
- gowers Says:
  September 28, 2011 at 2:07 pm
  Sorry to be slow, but I don’t see precisely what it is that you are suggesting. Do you mean that at the start of each post I should say that it is a continuation of the series that began a few posts ago? I can see that that might be a good idea.
- gowers Says:
  September 28, 2011 at 2:33 pm
  I was indeed being slow and have now understood your comment and followed the suggestion.
Colin Reid Says:
September 28, 2011 at 2:08 pm | Reply
Perhaps the mathematical sense of ‘if… then…’ is not so peculiar to mathematics, given that ‘if X, then Y’, where Y is statement whose falsehood is common knowledge, such as ‘pigs can fly’ or ‘I’m the Queen of Sheba’, is an emphatic way of saying ‘not X’ in everyday English. Your first example is something I can imagine a non-mathematician saying in ordinary conversation, and of course he wouldn’t mean to say that X and Y are causally linked – it is purely an assertion about truth-values.

By contrast, nobody says ‘if X, then Y’ when Y is known to be true because it would be pointless to say it – it doesn’t convey any new information. The difficult one is ‘if X, then Y’ where X is known to be false – is it a vacuous statement, or is it an assertion about some hypothetical alternative reality, and if so, is it an assertion about causation? The interpretation of ‘counterfactual conditional’ sentences can be a tricky business. There is also a limit to how far people will go with such counterfactuals – it’s OK if the premise is merely false, but it’s not allowed to be ‘nonsensical’ (which does not mean ‘syntactically invalid’).
- gowers Says:
  September 28, 2011 at 2:18 pm
  I agree that things like “then pigs can fly” or “then I’m a Dutchman” are used to emphasize the truth of some premise. But I think that if you stare hard at a non-mathematician and ask in a significant voice, “Is it really the case that if there were weapons of mass destruction in Iraq, then pigs can fly?” it is possible to push them into the more dubious counterfactual way of thinking. (When I say “dubious” I don’t mean that there’s something wrong with counterfactuals. It’s just that the right way of expressing that particular counterfactual is, “If there had been weapons of mass destruction in Iraq, then pigs would have been able to fly.” That statement is false, and I think that’s why people sometimes doubt the first one.)
Mark Meckes Says:
September 28, 2011 at 2:29 pm | Reply
I’ve really been enjoying this series of posts, since I’m teaching a course that (among other things) is about precisely these issues at the intersection of basic logic and language. (It’s what’s commonly called a “transition course” in the U.S.) I especially like your discussion about “implication” versus “causation” here.

A related issue came up recently for me. Several times in the past I’ve seen students use the word “suggests” in proofs, as in “P suggests that Q is true”. The most recent time I saw this, having recently discussed the “implies” connective in detail, it occurred to me that in colloquial English, “suggest” is a (not quite exact) synonym for the most common usage of “imply”, namely, to hint that something is true without directly saying so. This meaning of “imply” is much weaker than its mathematical meaning. I don’t know whether the students who write “suggest” in place of “imply” are misunderstanding what “imply” means in mathematical English, or if they’re simply overgeneralizing the synonym relationship between those words.
Terence Tao Says:
September 28, 2011 at 4:13 pm | Reply
Some assorted comments:

The wikipedia page on the “use-mention distinction” has some nice discussion and examples of the distinction between a statement, and a reference to that statement.

The two interpretations of “implies” as “material implication with parameters” and “logical deduction” are connected by the Godel completeness theorem, which roughly speaking says that the two senses are equivalent (assuming one’s logic is consistent and at most first-order, of course).

I like to interpret “If A, then B” as “B is at least as true as A”, as I discussed in this Buzz.
- Terence Tao Says:
  September 28, 2011 at 4:51 pm
  Actually, upon reflection I would probably withdraw my second comment: the completeness theorem equates “logical deduction” with “material implication in all possible worlds”, rather than “material implication with parameters”, which is a slightly different concept. (For instance, one normally doesn’t consider the prime ministership of Thatcher to be a variable parameter.)
- Jack Says:
  September 29, 2011 at 6:36 pm
  You’ve talked about the appendix basic mathematical “logic” in your Analysis I to me before, especially about this “implies” issue:-)(http://terrytao.wordpress.com/books/analysis-i/#comment-49187). I Gowers’s post is a very nice complementary material for that appendix.
- Jack Says:
  September 29, 2011 at 6:39 pm
  Oops, it’s supposed to be “I think Gowers’s post…”
- Doug Spoonwood Says:
  September 30, 2011 at 4:42 am
  The interpretations of “implies” happen in the context of propositional, or zero-order, logic. So, I would scratch “Godel completeness (meta) theorem” and write “completeness (meta) theorem” (for propositional logic), at least since that came as known before Godel’s result. Second, unless I’ve misunderstood something, the completeness (meta) theorem says if “p|=q”, then “p|-q”. For these two to come as equivalent, if that’s what you meant (and I don’t mean to assert that you did mean this), you also need soundness… if “p|-q”, then “p|=q”.
  
  That said, I wouldn’t interpret either of these as having anything to do with material implication, or perhaps better the material conditional, at least not so easily. I do agree that “p|-q” can get interpreted as “p implies q” with “implies” meant in the sense of “logical deduction”. But, if you read “p implies q” in the sense of “if p, then q”, then you’ve said (p->q). If interpreted semantically, which might seem more fitting than syntactically “|-(p->q)”, then “p implies q” means |=(p->q). By completeness one can infer |-(p->q). Now, the sense of “p implies q” in terms of “logical deduction” p|-q, comes as related to that of “material implication” |-(p->q) by the deduction (meta) theorem and its converse. In other words, if p|-q, then |-(p->q) (the deduction metatheorem), and if |-(p->q), then p|-q (the converse of the deduction metatheorem). If you mean iff p|=q, then and only then |-(p->q), then you’ll need both completeness and the deduction metatheorem and its converse.
  
  So completeness plays a role here, sure. But, completeness doesn’t equate things here… completeness along with the deduction theorem and its converse “equates” “material implication” with “logical deduction”, at least if “material implicaton” means |=(p->q) and “logical deduction” means p|-q.
Richard Baron Says:
September 28, 2011 at 4:24 pm | Reply
I love your way of selling the seemingly odd behaviour of implication when we start with something false: your example with the empty set as a subset of {17}.

May I suggest an alternative way, which is really a way of selling the seemingly odd truth-table for “if p then q”, but which also sells the parallel apparent oddity for implication, because they really ought to keep in step. It feels satisfying to have that much connection between object language and meta-language.

People are happy to accept the first two lines of the truth table: T and T give you T, and T and F give you F. Worries are all about the two lines where p is false: F T giving T, and F F giving T.

But consider the alternatives, given that one is committed to having something truth-functional. T and F (for the value of the whole conditional) would make “If p then q” equivalent to q, which doesn’t seem right. F and T would make it equivalent to “p if and only if q”, which really ought to be different from “if p then q”. Finally, F and F would make it equivalent to “p and q”, which again ought to be something different.

At that point, someone will ask why we should be so fixated on truth-functionality. Well, it kind of helps to hold the whole system together.
- Doug Spoonwood Says:
  September 29, 2011 at 3:55 am
  I like your approach here. But, one can still have a commitment to truth-functionality here and not have “T” for the (F, F), (F, T) lines of the truth table, if say one wants to give up {T, F} as the truth set and have a 3-valued, many-valued (with “many” meaning at least 3), or infinite-valued truth set instead. In other words, you’ll need an a priori commitment to *two-valued truth functionality* for your approach to work. I think the same applies to Gowers’s presentation here. That said, if you postulate that ->(F, F)=U, and ->(F, T)=U where U represents a third truth value not equal to T or F and “->” indicates material implication, then statement forms like, in Polish notation, CpCCpqq no longer hold as theorems or tautologies.
- Richard Baron Says:
  September 29, 2011 at 8:32 am
  Hello Doug, I agree one can make things more complicated, and then a case of the type that I put forward falls apart. But I was not offering an argument that should compel those who already know about these things. My objective was the more modest one of getting beginners to stop worrying and get on with practising the connectives, until what might have seemed unnatural comes to be natural.
  
  The context may be relevant here. I teach logic for the sake of logic, to people who may not be mathematically inclined. One probably has less trouble teaching logic for the sake of (and as a part of) mathematics, to mathematicians.
Anonymous Says:
September 28, 2011 at 5:33 pm | Reply
Learning that “If P then Q” can be translated into “(not P) or Q” and from there into “not (P and (not Q))” helped me understand why the truth conditions for “If..then” are what they are, since it seemed obvious (to me, at any rate) that we would want “If P then Q” to be true in the same cases as “not (P and (not Q)).”
Sune Kristian Jakobsen Says:
September 28, 2011 at 5:48 pm | Reply
Thanks for a great post. I have a few comments:

“If $n$ is both even and odd, then $n=17$ .”
I would say n had to be the zero-function 😉

You write $n.$ two different places, but it is shown as $0^\circ$ on my computer (strange, since I didn’t have the problem with AO instead of B in your “and and or”-post).

Your proof of “If $\sqrt{2}$ is rational then there is an integer that is both even and odd” reminds me the joke/anecdote where Russell claims that he can prove anything, assuming the 1+1=1. Someone challenged him: “you can’t use 1+1=1 to prove that you are the pope”, to which he answer “I am one and the pope is one thus the pope and I are one”.
Sune Kristian Jakobsen Says:
September 28, 2011 at 6:15 pm | Reply
I forgot one comment.
I interpreted your Thatcher-tsunami example as: Let
$p(t)=$ “Margaret Thatcher was Prime Minister of the UK at some time $<t$ ” and $q(t)=$ “there was a tsunami in Japan shortly before time t”. With this interpretation, $p(t)\Rightarrow q(t)$ is not true, since there was tsunamis before Thatcher became Prime Minister. On second reading I see that you wrote that it was "two fixed statements", so it was probably my own fault.
Aspirant mathmo Says:
September 28, 2011 at 7:55 pm | Reply
Near the start of this entry, you mention that some people have the tendency to use the “implies” symbol when not referring to noun statements. I suspect this is because some people want to use the “implies” symbol as a form of mathematical connective (which is not what it’s for!), and therefore often mistake “implies” with “which implies that”… as you hinted above! I know I’m sometimes guilty of this.
Anonymous Says:
September 28, 2011 at 11:28 pm | Reply
I don’t mean to be rude, but did somebody just sit in on a first year philosophy course?
- gowers Says:
  September 28, 2011 at 11:40 pm
  The phrase, “I don’t mean to be rude, but” is not without philosophical interest …
- Anonymous Says:
  September 30, 2011 at 2:59 pm
  I must have been talking about Terry.
Chris Purcell Says:
October 2, 2011 at 9:34 pm | Reply
XKCD has a nice strip pertinent to this article:

http://xkcd.com/704/
ogerard Says:
October 10, 2011 at 7:27 am | Reply
Thanks for this long post. I was delighted to rediscover several distinctions about mathematical discourse in ordinary english I usually do not keep consciously in mind when writing.

But you write in the first part:

“Here are a few metamathematical statements.

-1- “There are infinitely many prime numbers” is true.

-2- The continuum hypothesis cannot be proved using the standard axioms of set theory.

-3- “There are infinitely many prime numbers” implies “There are infinitely many odd numbers”.

-4- The least upper bound axiom implies that every Cauchy sequence converges.

In each of these four sentences I didn’t make mathematical statements. Rather, I referred to mathematical statements.”

I beg to differ slightly.

First, many metamathematical statements are mathematical statements in a larger theory and can often be treated as mathematical objects (for example Model theory).

Second, I would have drawn important distinctions between those four (but it was not exactly the subject of your post which is already very detailed).

Further, each of your four sentences implies a specific mathematical universe with minimal logical and set-theoretic axioms for it to be meaningful and unambiguous. I think this is important to point out to young mathematicians.

In these sentences we have most of the time silent implications together with an explicit “implies” (see below).

There is a topological analogy: most properties of, say a knot, depend on the space it is embedded in.

Not that these sentences do not have the same implied strength or the same immediate relevance for the mathematician, undergraduate or not. So I prefer to rephrase them with parameters and implicit hypothesis.

-1- Theorem A is true (in implied theory T)

-2- Axiom C is independent from Axiom-System S

-3- Theorem A has Corollary B (in implied theory T common to A and B)

-4- Axiom L (added to implied Theory R) gives it the strength to prove Theorem V.

The first sentence is of the most common kind for a mathematician.

The third sentence is very common as well and is a very small step from -1-.

Both -1- and -3- are used so frequently that the distinctions between mathematics and metamathematics is blurred as in common metalinguistic sentences people use every day : “Please, can you finish your sentence?” or “Do not answer this question!”

The fourth one is of strong metamathematical character and of interest to most mathematicians, because Theorem V is useful and a common way to express continuity. It could be paraphrased/expanded : one of the solutions to create a mathematical universe where you can have a notion of continuity for your analysis theorems is to have a Theory R consistent with Axiom L and add this axiom L to R, creating Theory R2 and go on with finding limits.

But the second one is the strongest of all, the most “meta” and the only one to be explicit about its metamathematical context. It is part of a family of statements of about “relationships between logical contexts in which you can do mathematics”. You can call that meta-trans-peri-mathematics or meta-meta-metamathematics.

It would be very difficult to find an equivalent to -2- in a non mathematical situation. It would be considered at best very subjective or dogmatic such as “You cannot speak about the “Gestalt” philosophical concept in english without using the german word “Gestalt” or another philosophical german word of equivalent depth and power. You will always fail if you try.”

The remarquable thing about mathematics is that we can reach a so strong level of implication in our discourse about it.
About metamathematical statements in a recent post by Timothy Gowers « thinking in tune Says:
October 10, 2011 at 7:32 am | Reply
[…] is a comment about this post by Professor Timothy Gowers, in a series for mathematical undergraduates he has started […]
Ram Says:
October 27, 2011 at 12:54 pm | Reply
Here is an excerpt from ” Principia Mathematica vol.1 ” Betrand Rusell and Whitehead :

The Implicative Function is a propositional function with two arguments p and q, and is the proposition that either not-p or q is true, that is, it is the proposition ~ p v q. Thus if p is true, ~ p is false, and accordingly the only alternative left by the proposition ~ p v q is that q is true. In other words ii p and ~p v q are both true, then q is true. In this sense the proposition ~ p v q will be quoted as stating that p implies q. The idea contained in this propositional function is so important that it requires a symbolism which with direct simplicity represents the proposition as connecting p and q without the intervention of ~ p . But “implies” as used here expresses nothing else than the connection between p and q also expressed by the disjunction “not-p or q” The symbol employed for “p implies q}” i.e. for ” ~pvq ” is “p \supset q.” This symbol may also be read “if p, then q.” The association of implication with the use of an apparent variable produces an extension called ” formal implication.” This is explained later: it is an idea derivative from ” implication ” as here defined. When it is necessary explicitly to discriminate ” implication ” from ” formal implication,” it is called “material implication.” Thus ” material implication” is simply “implication” as here defined. The process of inference, which in common usage is often confused with implication, is explained immediately.

I dont understand this when i compared to implication function read in modern logic books which just give a truth table for if p then q.

I am confused…
- Anonymous Says:
  November 13, 2014 at 5:19 pm
  When you say to bad, I am going to is use the double-line arrow anyways, why not just use a single line arrow for if..then?
Mathematical implication « Wildon's Weblog Says:
November 13, 2012 at 5:54 pm | Reply
[…] variants on the expression `I’m the Queen of Sheba’, or `pigs can fly’ I found a Blog post by Timothy Gowers that discusses all the issues above much more carefully. You might find the […]
A little paradox | Gowers's Weblog Says:
December 9, 2013 at 5:05 pm | Reply
[…] post is intended as a footnote to one that I wrote a couple of years ago about the meaning of “implies” in mathematics, which was part of a series of posts designed as an introduction to certain aspects of university […]
The arrow thing | New-cleckit dominie Says:
February 4, 2014 at 9:13 pm | Reply
[…] students? One, no doubt, is that in formal terms it’s a slippery object: not, as Tim Gowers discusses with his characteristic clarity, a logical connective in a strict sense, and certainly not closely […]
David Says:
June 28, 2015 at 2:26 pm | Reply
In the section ‘Yes, but what do if and then mean?’, you wrote;

“$P\implies Q$ unless $P$ and $\neg Q$.”

to emphasize the use of quotation marks; however, should this not be

“$P\implies Q$” unless “$P$ and $\neg Q$.”?

with a quotation mark after Q in the first implication?
http://kateebd01267.wikidot.com Says:
December 23, 2020 at 12:37 pm | Reply
http://kateebd01267.wikidot.com

Basic logic — connectives — IMPLIES | Gowers's Weblog
Learn To Play Poker – The Guidelines – CakeShop Says:
November 20, 2022 at 4:26 pm | Reply
[…] general simplicity that players have actually in switching tables, playing during meal or before supper implies that occasionally you will be playing in shorthanded […]
온라인바둑이 Says:
January 31, 2023 at 9:59 am | Reply
온라인바둑이

Basic logic — connectives — IMPLIES | Gowers's Weblog