Basic logic — connectives — AND and OR

In my introductory post I talked about fake difficulties. It will take some time and several more posts before I can say what I really mean by that notion, but this post will get me a bit closer. So far I have mentioned that if you can’t solve a problem because you haven’t been bothered to look up what the words mean, then your difficulties are not genuine. A more interesting category of fake difficulties is a failure to grasp a few basic logical principles. I call this a fake difficulty even though for some people it is genuinely difficult; the reason I do so is that when mathematicians consider a problem to be hard, it is not for basic logical reasons. To put that another way, with a little bit of practice one can make basic logical deductions completely mechanically, and it is absolutely essential to learn how to do so. It is a simple skill (which is not to say that no work is needed), and it underlies all mathematical reasoning. Trying to understand university-level mathematics without a secure grasp of basic logic is like trying to learn long multiplication without knowing your tables — only a lot harder.

What am I talking about when I use the phrase “basic logic”? I am talking about having a good understanding of the following.

Logical connectives. The main ones are “and”, “or”, “not” and “implies”.

Quantifiers. The phrases “for all” and “there exists” come up a lot in mathematics and you have to be capable of dealing with sentences like this: for every \epsilon>0 there exists N such that for every n\geq N |a_n-a|<\epsilon.

Relationships between statements. Given a statement, you should have no trouble forming its negation, its converse and its contrapositive. Of course, for that you need to know what those three things are.

Each of the items above is a potential source of confusion. In particular, quantifiers take a lot of getting used to. However, when you are used to basic logical principles you will find that in many situations you can apply them in a purely mechanical way, sometimes without even needing to understand the statements to which you are applying them. In the next few posts I will try to help you develop that ability if you don’t already have it.

These posts, all with titles of the form “Basic logic — <subtitle>,” are not intended to be typical of the posts in this series, since they are introductory and not tied to any particular course. But basic logic is something that I have to get out of the way before we move on to the more interesting stuff. So let me now discuss a couple of logical connectives in more detail. I’ll save “not”, “implies”, quantifiers, and sentence relationships for later posts.

If you think your basic logic is not quite 100% secure, then I recommend that you read through all the posts that I shall put up on the topic. If put together, they are quite long, and therefore you probably won’t want to reread them too often, so I intend to write a brief summary of the main points, for easy reference later. But that summary will just give you the basic facts, without the justifications and explanations that will be presented in the posts.

AND and OR.

It may seem at first as though there is not much to say about the words “and” and “or”. After all, are they not just common English words that mathematicians happen to use as well? In a sense they are, but their meanings are subtly different from their usual everyday meanings, and it is important to understand the differences.

For the purposes of this discussion I am going to do something that you may not have seen before. You will be very familiar with the idea that letters can be substituted for numbers. But at university, letters (or other symbols) get substituted for absolutely everything. Here I am going to use letters to stand for statements. For some reason the traditional letters to use seem to be p and q, or sometimes P and Q.

AND.

How might we explain what “and” means? It seems difficult to do so without being circular and saying something like this: “P and Q” is true if and only if P is true and Q is true. I appear to have defined “and” using the word “and”. If I substitute actual sentences for P and Q I get something like this: “London is in England and Paris is in France” is true if and only if “London is in England” is true and “Paris is in France” is true, which is a bit of an odd observation to make.

And yet somehow it does tell me something. It tells me that if I want to establish the truth of the compound sentence “London is in England and Paris is in France” then it is enough to establish that London is in England and also to establish (possibly by a completely different method) that Paris is in France.

However, that observation is not enough to stop the example feeling odd. In my opinion, one gets a much better idea of the role of logical connectives in mathematics by considering statements with parameters. I’m talking here about statements like, “n is prime”, where all you know about n is that it is a positive integer. The statement “London is in England” is either true or false (and happens to be true). The statement “n is prime” involves the parameter n, and is true for some values of n, such as 13 and 17, and false for others, such as 14, 15 and 16.

The great advantage of thinking about statements with parameters is that their truth value is not fixed, but depends on the parameters. That this is an advantage will become particularly clear when we come to think about the word “implies”. But for now let us return to the word “and” and consider the statement, “n is prime and n is even.” For this to be true, we need n to be both a prime number and an even number, which tells us that n=2. For all other values of n it is false. For example, if n=3, then n is prime but n is not even, and because n is not even we cannot say “n is prime and n is even.” Similarly, if n=4 then the statement is false because n is not prime.

Here is another example that is perhaps even more typical of how mathematics uses the word “and”. One of the topics in the Numbers and Sets course is, needless to say, sets, and one of the definitions associated with sets is that of the intersection of two sets (which you may have met at school and represented in Venn diagrams). If A and B are two sets, then their intersection A\cap B is defined to be the set of all objects x such that x belongs to A and x belongs to B. I am trying to avoid using symbols here, but for those who have seen them, the definition would normally be written like this:

A\cap B=\{x: x\in A and x\in B\}.

Another way of expressing the same idea would be this: x belongs to A\cap B if and only if x belongs to A and x belongs to B.

What does this tell us? Well, when we try to solve a problem, we usually have a statement that we are trying to prove, and some statements that for one reason or another we know to be true. Suppose that one of the statements we know to be true is that x belongs to the intersection A\cap B, or in symbols x\in A\cap B. Then the meaning of the word “and” tells us that we can replace this information by the two bits of information that x belongs to A and that x belongs to B. That is, if we were to keep a list of statements that we knew to be true, and on that list we had

x belongs to A\cap B.

we would know that we could replace that list item by the two items

x belongs to A.
x belongs to B.

This might be a very useful thing to do: for example, perhaps the information that x belongs to A is used in one place in the argument and the information that x belongs to B is used in another place.

I still haven’t really demonstrated an interesting difference between the mathematical use of the word “and” and the everyday use. But here’s one. In everyday usage the following sentence makes good sense: “Jack and Jill went up the hill.” But in mathematics, at least when it is written formally, the word “and” connects statements (which is why it is called a logical connective) rather than connecting objects. So a mathematician would feel an urge to rewrite the well-known nursery rhyme in the following rather less catchy way: “Jack went up the hill and Jill went up the hill.” That’s not to say that you never see a sentence like “x and y are positive”, but you should be very aware that that is a different use of the word and should think of it as a useful shorthand for “x is positive and y is positive”.

OR.

The first thing to say about the word “or” as it is used in mathematics is that it is always the inclusive or rather than the exclusive or. In abstract terms, the statement “P or Q” is true if and only if P is true or Q is true or both. As with “and” one can illustrate this in a rather unilluminating way with examples such as the following.

London is in England or Paris is in France.
London is in England or Paris is in Pakistan.
London is in Scotland or Paris is in France.
London is in Scotland or Paris is in Pakistan.

Of those four sentences, the first three are true (because in each case at least one of the two constituent parts is true) and the fourth is false (because neither constituent part is true).

But again the real use of the word “or” is much better illustrated by statements with parameters. For instance, the statement “n is prime or n is of the form 4m+1″ is true if at least one of “n is prime” and “n is of the form 4m+1″ is true. (Here I’m imagining that n is a positive integer but m can be zero.) Let’s list the first few values of n for which this statement is true:

1,2,3,5,7,9,11,13,17,19,21,23,25,29,31,33,37,41,43,45,47,49,53,57,59.

For all the other positive integers up to 60 it is false (unless I’ve made a slip). Had I been using the exclusive or (so called because the two statements “exclude” each other) then I would not have included 5, 13, 17, 29, 37, 41 or 53 because those number are both prime and of the form 4m+1. But I was following conventional mathematical practice and using the inclusive or, so I did include them.

Perhaps the single most important thing you need to know about “or” is how to respond to it if it comes up in proofs. For example, suppose you find that amongst the list of statements you know a statement of the form “P or Q”. In other words, you know that either P is true or Q is true (or possibly both). In most cases, P and Q will be statements with parameters: an example might be “n=2 or n is odd”, which would follow if you knew that n was prime.

If you know that “P and Q” is true, then you can add both P and Q to your list of things that you know and can use. But if all you know is that “P or Q” is true, then your task is more difficult. This time what you have to do is split your argument into cases. If you are given that “P or Q” is true, and you want to deduce R, then you must show that you can deduce R if you assume P (and whatever else you know) and that you can also deduce R if you assume Q (and whatever else you know). That way, since at least one of P and Q is guaranteed to be true, R must be true. So in a proof you might write something like this: “First let us assume that P. Then … blah blah … so R follows. Now let us assume that Q. Then … blah blah … and again R follows. Therefore the result is proved.”

What I mean when I say that you need to be on top of basic logic is that you should get to the stage where reacting to a statement of the form “P or Q” in the way I have just described is a pure reflex: you see that you know that either P or Q, so you just automatically go into “If P, then … and if Q, then …” mode.

What about if the statement “P or Q” is the statement you are trying to prove (as opposed to what I have just been discussing, when “P or Q” is one of the statements you are trying to use to prove something else)?

If P and Q are fixed statements, then you can prove “P or Q” by picking one of P and Q and proving that. For instance, if I want to prove the statement “There are infinitely many primes or every group of prime order is cyclic” then I could simply prove that there are infinitely many primes and have done with it. But that is not the situation that usually occurs. Usually when one wishes to prove “P or Q” it is a statement with parameters. For example, an important result in the Numbers and Sets course is this.

Theorem. Let p be a prime number and let a and b be positive integers. Suppose that p is a factor of ab. Then either p is a factor of a or p is a factor of b.

Before I say anything more about this, note that the result would be false if I were not using the inclusive or. For example, p could be 5, a could be 10 and b could be 15. Then p is a factor of ab (which equals 150) but it is a factor of both a and b. Part of the reason I’m mentioning this is that the word “either” suggests to many people that one is using the exclusive or, probably because in many ordinary-language contexts we use the word “either” to emphasize that the two alternatives we then go on to lay out are incompatible. An example: if I say, “I don’t know where I’m going to go on holiday next year. I think I’ll either go to the South of France or to Greece.” then it would be quite reasonable of you to interpret me as ruling out going to both places. But in mathematics the word either does not have this implication. If it sounds to you as though it does, then you need to get into the habit of ignoring the word whenever you see it.

Returning to the theorem, what is the statement we are trying to prove. It is “p is a factor of a or p is a factor of b.” Now because we don’t actually know anything about p, a or b, beyond the fact that p is a prime and a and b are positive integers, we can’t just say, “Right, I’m going to prove that p is a factor of a,” or “Right, I’m going to prove that p is a factor of b.” Instead what we have to do is more like this.

1. Assume that p is not a factor of a.

2. Draw some consequence of that assumption and use it to prove that p is a factor of b.

If we can do that, then the result is proved, since either p is a factor of a or the above argument can be used to show that p is a factor of b. The consequence one uses if p is not a factor of a is that the highest common factor of p and a is 1. I won’t say any more at this stage but in a future post I shall discuss this proof in detail.

Sometimes when one wishes to prove a statement of the form “P or Q” a slightly more complicated plan of attack works. It goes something like this.

1. Attempt to prove P, and try to identify what has to happen for your proof not to work.

2. Show that if that happens, then Q must be true.

Here is a simple example: the infinite pigeonhole principle. I will state the result and its proof.

Theorem. Suppose that the positive integers are each coloured either red or blue. Then either there are infinitely many red integers or there are infinitely many blue integers.

Proof. [First comes the attempt to prove one of the two statements.] Let us attempt to find infinitely many red integers. We’ll try to do it in the simplest way imaginable: we’ll just pick a red integer n_1, then a larger red integer n_2, then a larger red integer n_3, and so on. If we succeed, then we have produced an infinite sequence of distinct red integers and we have therefore obtained the first statement.

[Next comes the process of understanding what must be the case if the proof of the first statement doesn't work.] The only way we can fail is if for some k we find that we have identified red integers n_1<n_2<\dots<n_k and cannot find any red integer n that is bigger than n_k. (If we could find such an n, then we could have used it for n_{k+1}, so we wouldn’t have been stuck at n_k.)

[And now, having drawn a consequence of our failure to prove the first statement, we go ahead and use it to prove the second.] But in that case all the integers from n_k+1 onwards are blue, so in particular there are infinitely many blue integers. \square

The associativity of AND and OR.

There is a rule that I ought to mention briefly, even though you will either be aware of anyway or will happily use it without even thinking about it. It is the rule

  • “P or (Q or R)” is the same as “(P or Q) or R”
  • and the companion rule

  • “P and (Q and R)” is the same as “(P and Q) and R”.
  • For “P or (Q or R)” to be true, we need at least one of P and “Q or R” to be true. And for “Q or R” to be true we need at least one of Q or R to be true. Putting all that together, we find that for “P or (Q or R)” to be true we need at least one of P, Q and R to be true. And clearly the same argument shows that the same condition needs to hold for the statement “(P or Q) or R” to be true. So we just drop the brackets and write “P or Q or R” and think of this as saying that at least one of the three statements is true.

    Similarly, we don’t bother with brackets for repeated ANDs, writing “P and Q and R” for the statement that all three of P, Q and R are true. And similar considerations hold for larger collections of statements as well.

    The distributivity of AND over OR and vice versa.

    Consider the following sentence.

  • x is prime or y is prime and z is prime.
  • What does this mean? Does it mean this?

  • At least one of x and y is prime. Oh, and by the way, z is prime too.
  • Or does it mean this?

  • Either x is prime, or both y and z are prime.
  • The answer is that the sentence as written could mean either. Since mathematicians don’t like ambiguity, they do not allow themselves to write such sentences, or their symbolic equivalents, which are P\vee Q\wedge R and P\wedge Q\vee R.

    Before I talk about distributivity, let me briefly mention another context where there are expressions we are not allowed to write. Nobody writes a\div b\div c, because the numbers (a\div b)\div c and a\div(b\div c) are in general different. But hang on, you might say, the numbers (x-y)-z and x-(y-z) are in general different, but it is considered perfectly OK to write x-y-z. That is indeed true, and all I can say in response is that we have a very strongly established convention that when you’ve got a string of pluses and minuses, you bracket them in such a way that you do the calculations from the left. For instance, x-y-z+w-u-v is understood to mean ((((x-y)-z)+w)-u)-v. (More intuitively, it means “start with x, then take away y, then take away z, then add w, then take away u, then take away v.) We could easily use an exactly analogous convention for division, so why don’t we? That’s a historical question, but I suspect the answer is closely related to the fact that we usually don’t use the division symbol \div, preferring to write things as fractions. With that notation, we can distinguish clearly between \frac x{y/z} and \frac {x/y}z. (Of course, we don’t write x/y/z because that would go back to being ambiguous.)

    Returning to AND and OR, that tells us that an expression like P\vee Q\wedge R is invalid until it is given some brackets. So let’s do so and consider the expression P\vee(Q\wedge R). And to do that, let us continue with analogies from arithmetic. (You might prefer the word “algebra” since I’ll use letters rather than numbers, but in university mathematics, the word “algebra” has rather different connotations and we’ll happily talk about arithmetic even if the numbers we’re adding, subtracting, multiplying and dividing are unknown and represented by letters.) The distributive law in arithmetic is the one that says that x(y+z)=xy+xz. By a miracle, exactly the same rule applies to \vee and \wedge. That is,

  • P\vee(Q\wedge R)\iff (P\vee Q)\wedge (P\vee R)
  • Before I continue, let me say that you should always be suspicious of anything in mathematics that looks like a remarkable coincidence. Nearly always there is an explanation, and nearly always that explanation takes the form of some more general statement of which the two parts of the coincidence are separate manifestations. If you want something to think about, see whether you can come up with some general statement that contains the distributive law for times and plus and the distributive law for OR and AND as special cases. And if you’re interested in the question of whether there is such a thing as a genuine coincidence in mathematics, you might like to read a very nice article on the topic by Philip Davis.

    Oh, and if you do try to find that general distributivity statement, then while you’re at it you might as well throw in the fact that AND is distributive over OR. That is, not only do we have the rule I’ve just stated, namely

  • P\vee(Q\wedge R)\iff (P\vee Q)\wedge (P\vee R)
  • but we also have the same thing with AND and OR reversed. That is,

  • P\wedge(Q\vee R)\iff (P\wedge Q)\vee (P\wedge R)
  • That may come as a bit of a surprise, seeing that addition is not distributive over multiplication, by which I mean that it is not a correct rule that x+yz always equals (x+y)(x+z). This tells you that finding a general framework that encompasses times/plus and or/and can’t be too simple, since otherwise it wouldn’t explain why plus/times doesn’t work but and/or does.

    I’ve just stated these distributivity rules, so before I stop, let me briefly discuss why they are true. Let’s go back to the sentence about primes, but this time put brackets in. Suppose we wanted to show that

  • (x is prime or y is prime) and (x is prime or z is prime).
  • Well, if we can show that x is prime, then we’ll be in great shape, since that will make both brackets true, which is exactly what we need. But if we can’t show that x is prime, then the only way of making both brackets true is to show that y is prime and z is prime. And now if you look carefully at what I’ve just written, you’ll see that I’m saying that it is both necessary and sufficient to show that

  • x is prime or (y is prime and z is prime).
  • A similar justification can be given for the other distributivity law. That is, if you want to show that

  • x is prime and (y is prime or z is prime)
  • then it is necessary and sufficient to show that

  • (x is prime and y is prime) or (x is prime and z is prime)
  • I recommend that you stare at these two sentences until you have convinced yourself that they are indeed saying precisely the same thing.

    One last question to finish the post: why do you think that the conventional way of interpreting expressions like x-y-z+w is what it is?

    About these ads

    41 Responses to “Basic logic — connectives — AND and OR”

    1. Terence Tao Says:

      One subtlety with connectives that I’ve seen undergraduates have trouble with is that the roles of “AND” and “OR” are flipped when dealing with sets, rather than with individuals. For instance, let A be “the set of cats and dogs”, and let a be an element of A. Then it is not true that “a is a cat and a dog”; instead one has “a is a cat OR a dog”.

      This subtlety means that one cannot apply some mindless substitution rule in order to translate logical connectives into set-theoretic notation such as unions and intersections. For instance, the “set of cats and dogs” is the union of “the set of cats” and “the set of dogs”, but “the set of numbers that are even and square” is the intersection of “the set of numbers that are even” and “the set of numbers that are square”. It’s not a problem so long as one is thinking with the part of the brain that is capable of comprehending English sentences, but sometimes this mode of thinking shuts down when faced with a scary-looking maths problem, and one instead relies on more dubious formal substitution rules such as “AND means UNION”, which can lead to trouble.

      • gowers Says:

        Funnily enough, I had a similar problem when writing an extension to the post above. It seems reasonable to say that P\vee Q is true if and only if at least one of P and Q is true. So to explain “or” I actually used the word “and”. Of course, it’s the words “at least one” that are doing most of the work in defining “or”.

      • Jimbo Says:

        There is an additional subtle difference between “the set of cats and dogs” and “the set of numbers that are even and square”, which seems to be important – the phrase “that are”.

        “the set of cats and dogs”, I’d intuitively think of as containing both cats and dogs whereas “the set of animals that are cats and dogs” I would say is empty.

    2. David Says:

      Just to point out a small typo; where you write “x belongs to A \cap B”, you have just below it “x belongs to AO” which should be “x belongs to B”.

    3. Anonymous Says:

      The typo is two paragraphs above your Jack and Jill example.

    4. Sune Kristian Jakobsen Says:

      I think you forgot 31 and 43 on your list of numbers that are prime or on the form 4m+1.

      Thanks very much — now corrected.

    5. Anonymous Says:

      16 lines above the “OR” section.
      Your LaTeX source for the AO bit is “B.” (including the full stop). Maybe try removing the full stop from the TeX’d bit? Not sure why that would affect it though…

      • gowers Says:

        OK, something weird is indeed going on because it looked fine on my computer. However, I have changed it, by moving the full stop outside the TeX (which I normally avoid doing because it risks the punctuation appearing on a new line). I hope it looks OK now. To me it looks unchanged …

    6. Peter Smith Says:

      This is obviously going to be a fantastically useful series! A comment, a query, and a suggestion:

      Comment: “With a little bit of practice one can make basic logical deductions completely mechanically”. Well, with a bit of practice one can mechanically check that purported logical deductions are indeed in good order. And you can learn some useful heuristic tips for finding logical deductions from what you are given to where you want to go (like your “if a premise is a disjunction, try using proof-by cases”; “if your desired conclusion is a conjunction, try proving the conjuncts separately”). The snag comes when you have a number of premisses and a desired target conclusion, so your rules of thumb give you a variety of different proof-finding heuristic tips to try. How do you proceed to discover whether the conclusion really follows? In what order should you apply your proof-discovery tips? When should you give up and infer that the alleged conclusion doesn’t follow? In general there’s no mechanical rule!

      Query: “But in mathematics, at least when it is written formally, the word “and” connects statements (which is why it is called a logical connective) rather than connecting objects.” Well, in standard formal logic — whose language is borrowed by mathematicians — the “and” connective indeed only connects statements (maybe statements with variables/parameters). But, precisely because of that, standard logic does have trouble regimenting lots of perfectly ordinary mathematical statements with “and”s, such as “the points A and B and C are collinear”. Obviously that can’t be rewritten “A is collinear and B is collinear and C is collinear”.

      One dodge is to treat the “and”s as mere puncutation, so regiment the collinearity claim as “Collinear(A, B, C)” attributing a three-place relation “Collinear”. The snag comes when we think how we’d regiment “the points A and B and C and D are collinear” which seemining would now get regimented as “Collinear*(A, B, C, D)” involving a different four-place relation. An alternative dodge is to regiment these along the lines of “the set {A, B, C} has property Coll” and “the set {A, B, C, D} has property Coll”, and so on. These can invoke the same property Coll each case, but at the cost of changing the subject. How strange — we thought we were talking about some points, and now it seems we are talking about something else, a set! And so it goes …

      So the query is: how seriously do we really want to say that in mathematics the word “and” connects statements? I’d have thought: Often yes, always no.

      Finally, a suggestion: Talking about the associativity of ‘and’ and ‘or’ would have been a good opportunity to stress the non-associativity of mixed cases, and remarking on the potential dangerous ambiguity of P and Q or R.

      • gowers Says:

        Thanks for that interesting comment, or perhaps I should call it those comments. The question of how to find the deductions mechanically, as opposed to merely verifying them, is the central question of this series of posts. Although it can’t be done in complete generality, there are mechanical methods that cover a lot of useful cases, and even when those methods break down, they draw attention to what one might call “the exact place where a problem becomes hard”. More details later …

        Thanks for the suggestion about mixed cases. I agree with you, so I’ll add a section on that topic straight away.

      • Corentin Lena Says:

        There is a way around the difficulty in the example you give. If you think of “collinear” as a three-place relation between points, then “the points A and B and C and D are collinear” can be read as a shorthand for the statement “Collinear(A,B,C) and Collinear(B,C,D)”. I agree that it is not very elegant, and I am not sure that such reductions could always be done.
        I would like to thank Prof. Gowers for this great series of posts. I am sure I will find it useful, and I will recommend it to the students I TA (providing they can read English).

    7. Anonymous Says:

      The AO/B mixup seems fine to me now. No idea what was going on there though!

    8. Clark Barwick Says:

      Thanks so much for these posts! I’m sharing them with my first-year students at MIT. One small correction: isn’t 19 x 3 = 57?

    9. Joseph Perla Says:

      This is so great, I’m learning a lot of proofs this semester, and even though I’m somewhat familiar with this, thinking about it in such an explicit way helps a lot. Thank you so much!

    10. Richard Baron Says:

      When I read your final question, about grouping from left to right when we have only + and – in a string, the first thing that came to mind (not as an answer) was Polish and Reverse Polish notation. This must be a after-effect of having been to Casimir Lewy’s logic lectures.

    11. Anonymous Says:

      From ‘all you know about n is that it is a positive integer’ then if same for m may remove 1 from the list ‘1,2,3,5,7,9,11,13,17,19,21, …’
      TDevlin

      Thanks — I’ve clarified that now.

    12. A. Cooper Says:

      An interesting point from the field of linguistics: while most people intuitively feel that ordinary-language “or” is exclusive in meaning, it turns out that almost all semanticists agree it’s *really* inclusive.

      The point is that in almost any real-life situation where one uses “or”, the “and” is ruled out for (a term of art in linguistics) pragmatic reasons. For example, “Frank is a cat or a dog” feels exclusive, but only because we know that in real life “Frank is a cat and a dog” is not possible.

      Statements like “London is in England or Paris is in France.” are rejected as ill-formed by most people not because they violate the meaning of “or”, but because they violate the hearer’s expectation that the speaker will have made the most specific (i.e. mathematically strongest) statement possible–here, “London is in England and Paris is in France.” The speaker’s failure to do so upsets the hearer, but again this is a perceived deficiency of the speaker, not of the statement itself.

      • gowers Says:

        I’ve thought of a counterexample, though it involves imperatives and is therefore perhaps not perfect. If I were to get cross with my young son, I might say, “Stop that or I’ll send you to your room.” If my son obediently stopped and I then said, “Right, it’s off to your room with you,” he would feel utterly confused and indignant. The clear understanding of this “or” is that it is exclusive, and yet it is possible for my son to obey me and for me to send him to his room, so the “and” is not ruled out.

        Similar remarks apply to other connectives. If I hear somebody say, “Put your hand up if you would like to go to the seaside,” and I have no wish whatsoever to go the seaside, it would be considered misleading of me to put my hand up: that particular “if” is understood as “if and only if”.

        I’m sure you’re familiar with such examples, but in case anyone else is reading this comment who isn’t, the notion of Gricean implicature is quite entertaining, and relevant to this.

    13. Daniel J. Hill Says:

      I’m afraid that this will seem very pedantic — but, then again, I think you may appreciate pedantry. I don’t think it’s right to say that `implies’ is a connective, I am afraid. The word `implies’ is written between names of statements or between the name of a set of statements and the name of a statement: `the Axiom of Choice implies Zorn’s Lemma’, `Peano’s Axioms imply Fermat’s Last Theorem’. But `implies’ is not a connective here, but a dyadic relational term. Connectives are written between statements, not names of statements, so what we want is `if . . . then’ or `only if': `if the Axiom of Choice is true then Zorn’s Lemma holds’, `Peano’s Axioms are all true only if Fermat’s Last Theorem is correct’. Quine chastises Bertrand Russell for this mistake, and it does have implications (if you’ll pardon the weak joke).

      • gowers Says:

        I see your point entirely, even to the extent of there being a section in my next post about the difference between “implies” and “therefore” in which I said that implies was a relationship between statements, by which I meant names of statements. And from time to time I’ve wanted to illustrate what I am saying with examples and have found myself having to put in ugly inverted commas.

        The difficulty I have is that (i) we often write things like x+6=15\implies x=9 and (ii) we read the symbol “\implies” as “implies”. I see that the Wikipedia article is quite careful about this and says that the symbol means if … then.

        Another thing is that we happily write P\implies Q when P and Q are unknown statements. Clearly we don’t mean these as names of statements, or we wouldn’t be able to say P\wedge Q. And yet most people (I think) read P\implies Q as “P implies Q”.

        Anyhow, thanks for the comment. As you suspected, pedantic objections are welcome. I now have to think how to strike the right balance between getting everything correct and being intelligible. What I really care about is that people should be able to do things like negating implications, so I don’t want to scare people off with subtle distinctions. But I’d much rather be accurate than inaccurate. I’ve got some rewriting to do before I put up my next post …

      • Todd Trimble Says:

        The connective \Rightarrow can be and is pronounced “implies” by logicians and non-logicians alike. The fact that colloquially it is also used (harmlessly!) between names of statements should not obscure recognition of this fact. My own feeling is that this was not at all a helpful bit of pedantry on Quine’s part.

      • Todd Trimble Says:

        Ah, but there is a useful distinction to be made here after all: whereas “implies” is the name usually given to the connective \Rightarrow (so that if p and q denote propositions, then there is a proposition p \Rightarrow q), the word “entails” refers to the relation. That is, one writes p \vdash q, pronounced “p entails q“, to say that one may infer q from p in a deductive system. This turn out to be a useful distinction, and perhaps this was the distinction Quine meant.

    14. Daniel J. Hill Says:

      Thanks very much for this gracious and helpful reply, Prof. Gowers, and let me say what I should have said straightaway, viz. how good and kind it is that you are taking time to help non-experts (like me) master the basics.

      Just one point: you say `Clearly we mean these as names of statements, or we wouldn’t be able to say P\wedgeQ.’ But I think the example works against the principle you are trying to draw: the wedge symbol is written between statements, not names of statements, to create a further statement. There are complications here depending on whether `P’ and `Q’ are supposed to be meta-variables in our metalanguage or, as I’d taken them, dummy sentence letters in the object language, but clearly `the Axiom of Choice and Zorn’s Lemma’ isn’t a statement, but just a conjunction of names, whereas what we want is something like `1 + 1 = 2 and 2 + 2 = 4′ where we have on each side of the connective a statement, not a name.

      (Some people, e.g. Machover, have two sorts of arrows, one (single-shafted) to abbreviate `if . . . then’ and one (double-shafted) in the metalanguage for `implies’.)

      Anyway, I am looking forward to the rest of the posts — thanks again for doing this.

      • gowers Says:

        Oops, I meant to write, “Clearly we don’t mean these as names of statements.” What I actually wrote was nonsense, as you point out, but it wasn’t what was in my brain at the time, and I think with the extra word “don’t” it becomes OK (and agrees with you).

        I’ve decided to add the word “don’t” so as not to confuse people. Of course, that makes your response confusing, but I hope that this reply will deal with that.

    15. Doug Spoonwood Says:

      “The distributive law in arithmetic is the one that says that x(y+z)=xy+xz. By a miracle, exactly the same rule applies to \vee and \wedge.”

      In my opinion, it isn’t so surprising that “OR” and “AND” distribute over each other. Two very simple ways to interpret “OR” and “AND” are to think of “OR” as the maximum (minimum), and “AND” as the minimum (maximum) on an ordered set of two natural numbers, integers, rational numbers, or real numbers {a, b}. Via either of those interpretations distribution of both connectives over each other readily follows. The greater surprise, in my opinion, comes as that multiplication distributes over addition in arithmetic.

      • Todd Trimble Says:

        Except that “or” (applied to propositions) isn’t a maximum! A maximum between two elements would mean whichever is greater, whereas two propositions may not be comparable in logical strength. Instead, the “or” should be interpreted as a least upper bound.

    16. Basic logic — connectives — IMPLIES « Gowers's Weblog Says:

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

    17. Kiril Says:

      Could you please say more about how to deduce all the different forms of the distributive law from a single more general one? That sounds extremely interesting and I haven’t been able to figure it out.

      Thanks!

    18. Doug Spoonwood Says:

      @Todd Trimble Sure, “OR” interpreted as sup (or inf), and “AND” as inf (or sup respectively) comes as more accurate. Distribution then may or may not happen (i. e. not all lattices distribute). But, if you have a two-element set {a, b} of natural, integers, reals, or rationals, and the sup (inf) belongs to the set, then the max (min) behave just like the sup (inf).

    19. Anonymous Says:

      Let me quote this paragraph:

      [But if all you know is that “P or Q” is true, then your task is more difficult. This time what you have to do is split your argument into cases. If you are given that “P or Q” is true, and you want to deduce R, then you must show that you can deduce R if you assume P (and whatever else you know) and that you can also deduce R if you assume Q (and whatever else you know). That way, since at least one of P and Q is guaranteed to be true, R must be true. So in a proof you might write something like this: “First let us assume that P. Then … blah blah … so R follows. Now let us assume that Q. Then … blah blah … and again R follows. Therefore the result is proved.”]

      Is this where “[proof by cases](http://en.wikipedia.org/wiki/Proof_by_exhaustion)” from?

    20. Anonymous Says:

      I always used to wonder why we define “or” as being the inclusive or rather than the exclusive or. At least for me the explanation that made sense runs like this:

      1. “P and Q” is true if and only if P is true and Q is true.

      The above definition of “and” is relatively intuitive as it is consistent with everyday usage.

      2. Given 1, when would a statement such as “not (P and Q)” be true?

      Clearly, “not( P and Q)” will be true whenever “P and Q” is false. But, “P and Q” is false precisely when “P or Q” is true with or being understood to be inclusive.

      Thus, the above argument indicates that the inclusive or is needed to make ensure that the truth values of “not (P and Q)” is consistent with the truth values of “P and Q”.

      Hopefully the above makes sense and is of use to someone.

      • Richard Baron Says:

        Would you accept the following amended version of your paragraph beginning “Clearly”? (The critical change is from “P or Q” to “not P or not Q”.)

        Clearly, “not( P and Q)” will be true whenever “P and Q” is false. But, “P and Q” is false precisely when “not P or not Q” is true, with “or” being understood to be inclusive.

        Then I can see what you mean. “And” and “or” go together nicely, so long as “or” is inclusive.

      • Anonymous Says:

        Of course! I should have been more careful. Thanks for the correction.

    21. Hãy học lô-gíc cơ bản với Tiến sĩ Gowers, giải thưởng Fields 1998 « Út V. Lê Says:

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

    22. ipad Says:

      Is a sentiment…

      Excellent web sitePlenty of useful info hereI�m sending it to a few buddies ans additionally sharing in deliciousAnd obviously, thank you on your sweat!…

    23. Relationships Says:

      Relationships…

      [...]Basic logic — connectives — AND and OR « Gowers's Weblog[...]…

    24. vivekkhandelwal Says:

      I think the link to the article by Philip Davis is broken . The new address seems to be http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Davis311-320.pdf

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s


    Follow

    Get every new post delivered to your Inbox.

    Join 1,600 other followers

    %d bloggers like this: