Basic logic — connectives — NOT

I realized after writing the title of this post that it might look as though I was saying, “I’m going to discuss connectives … not!” Well, that’s not what I meant, since “not” is a connective and I’m about to discuss it.

NOT.

If you don’t know how to negate a mathematical statement, then you won’t be able to do serious mathematics. It’s as simple as that. So how does the mathematical meaning of the word “not” differ from the ordinary meaning? To get an idea, let’s consider the following sentences.

“We are not amused.”

“He is not a happy man.”

“That was not a very clever thing to do.”

n is not a perfect square.”

a is an element of the set A, but it is not the largest element of A.

A is not a subset of B.”

When Queen Victoria said, “We are not amused,” it is clear that what she meant was she was distinctly unamused, and not merely that she had failed to laugh. Similarly, if I say, “He is not a happy man,” I will usually mean that he is positively unhappy rather than neutral on the contentment scale. And if I say, “That was not a very clever thing to do,” I am saying, in a polite British way, that it was a stupid thing to do. (I could perhaps avoid that interpretation by stressing the word “very”. For example, if someone had made a good but reasonably standard move in chess and I knew enough about chess to tell that — which I don’t — then I might say, “That was not a very clever thing to do — but it was pretty good, so well done.”)

In all the examples above, the word “not” takes us from one end of some scale to the other: from amused to unamused, from happy to unhappy, from clever to stupid. In mathematics, the word “not” does not have this sense. If P is a mathematical statement, then “not P” is the mathematical statement that is true precisely when P is false. That is, if P is true, then “not P” is false, and if P is false, then “not P” is true. So if you want to understand a statement of the form “not P” then you should think to yourself, “What are the exact circumstances that need to hold for P to be false?”

In the case of the statement “n is not a perfect square” this is completely straightforward. We don’t have a notion of an utterly imperfect square, so there is no possibility of misinterpretation. We just mean that it is not the case that n is a perfect square. But take the statement “a is not the largest element of the set A.” We have been told that a is an element of A. If we want to show that a is not the largest element of A, what do we have to establish? Do we need to show that a is the smallest element of A? No. All we need to do is establish that it is not the case that a is the largest element of A. The usual way to set out that objective would be to formulate it as the following statement.

  • There is some element of A that is larger than a.
  • If that statement is true, then a is not the largest element of A. And if that statement is false, then there is no element of A that is larger than a, and since a is an element of A that tells us that a is the largest element of A.

    The third mathematical statement above was “A is not a subset of B.” Let me give two mistaken interpretations of that statement.

  • First mistaken interpretation: B is a subset of A.
  • This is mistaken because it is perfectly possible for A to fail to be a subset of B without B being a subset of A. For example, A could be the set \{1,2,3\} and B could be the set \{2,3,4\}.

    To work out what it means for A to fail to be a subset of B, let us write out more carefully what it means to say that A is a subset of B. The usual definition (written out in a slightly wordy way because I’m still trying to avoid symbols) is this.

  • A is a subset of B if every element of A is also an element of B.
  • By the way, I should mention here a convention that you need to know about. When mathematicians give definitions, they tend to use the word “if” where “if and only if” might seem more appropriate. For example, I might write this: “an integer n is even if there exists an integer m such that n=2m.” You might argue that this definition says nothing about what happens if no such integer m exists. Might 13 be even too? No, is the answer, because I am defining something and the convention is that you should simply understand that the words “and not otherwise” are implicit in what I’ve said, or equivalently that the “if” is really “if and only if”.

    OK, if “A is a subset of B” can be translated into “Every element of A is also an element of B,” then how should we translate “A is not a subset of B”? This brings me to the second incorrect answer.

  • Second mistaken interpretation: No element of A is an element of B.
  • This makes the going-to-the-opposite-extreme mistake. Don’t do that. Faced with a statement of the form “not P”, think to yourself, “What needs to be true for P to be false?” Applied to this case, we ask, what needs to be true for “Every element of A is an element of B to be false?” The answer is that at least one element of A should fail to be an element of B. Or as mathematicians might normally write it,

  • There exists an element of A that is not an element of B.
  • Or more formally still,

  • There exists a such that a\in A and a\notin B.
  • As I hope you can guess if you didn’t know already, the symbol \notin means “is not an element of”. As I also hope you can guess, putting a line through a symbol usually has the force of a not. You are probably already familiar with the symbol \ne, which means “does not equal”.

    There is a pair of logical principles known as de Morgan’s laws that you may well just take for granted, but that it is probably good to be consciously aware of. They concern what happens when you negate a statement that involves an “and” or an “or”. Let me illustrate them with some depressing scenes from my everyday life.

    Once a year I have to renew the tax disc on my car. If I didn’t do that I would have to pay a fine, but doing it without a fuss involves being a bit more organized than I normally have it in me to be, so I find myself facing a last-minute panic. What is difficult about it? Well, I have to bring along my insurance and MOT certificates, as well as a form I am sent and a means of payment. (For non-UK readers, MOT stands for “Ministry of Transport” but it also means a test of roadworthiness that you have to have carried out once a year if your car is over three years old, which mine very definitely is.) I take all those along to the post office and can buy the new tax disc there.

    Now suppose I were to arrive back from an expedition to the post office, the aim of which had been to get a new tax disc, and say to my wife, “I can’t believe it. I thought I had everything I needed, but I didn’t, and now I’m going to have to make another trip. Damn.” What could she deduce? Well, in order for me to have everything I needed, the following statement would have had to be true.

  • I had my insurance certificate and I had my MOT certificate and I had the form and I had the means to pay.
  • So from my failure to get a tax disc, she could deduce that the above statement was false. But what does it take for a statement like that to be false? It just takes one little slip-up. So she could deduce the following statement.

  • I didn’t have my insurance certificate or I didn’t have my MOT certificate or I didn’t have the form or I didn’t have the means to pay.
  • What happens here is that NOT turns AND into OR. Or to be a bit clearer about it, the statement “not (P and Q)” is the same as the statement “(not P) or (not Q)”. In the tax-disc example we had four statements linked by “and”, so the rule was a generalization of the basic de Morgan law, which told us that “not (P and Q and R and S)” was the same as “(not P) or (not Q) or (not R) or (not S)”.

    As you might guess, the other de Morgan law is that NOT changes OR into AND. Suppose we vary the scenario above slightly. This time I am trying to open a bank account and I need some ID. I end up having to go back home and I say to my wife, “Damn, I didn’t manage to open the account, because they said that the only ID they would accept was a passport or a driving licence with a photo on it.” What could she deduce this time? Well, in order to open the account, I needed the following statement to be true.

  • Either I had my passport on me or I had a driving licence with photo on me.
  • What does it mean for that statement to be false? It means that I failed on both counts. In other words, this happened.

  • I did not have my passport on me and I did not have a driving licence with photo on me.
  • The more abstract rule here is that “not (P or Q)” is the same as “(not P) and (not Q)”.

    A very general and possibly helpful rule of thumb applies to negation, including to several of the examples above. It’s this.

    Negating something strong results in something weak, and negating something weak results in something strong.

    For instance, suppose you are given two statements, which we’ll call P and Q. Then the statement “P and Q” is quite strong because it tells you that both the statements P and Q are true. By contrast, the statement “P or Q” is fairly weak because all it tells you is that one or other of P and Q is true and you don’t know which. Why do I use the words “strong” and “weak”? Well, it is easier for “P or Q” to be true than it is for “P and Q” to be true. That means that if “P and Q” is true, then I am getting a lot of information, whereas if “P or Q” is true I am getting less information. If you still don’t find that intuitively clear, then consider the statements

  • n is prime and n is even
  • n is prime or n is even
  • The first statement tells us that n=2, which is an extremely strong piece of information — we get to know exactly what number n is. The second statement merely tells us that n is one of the numbers 2,3,4,5,6,7,8,10,11,12,13,14,16,17,18,19,20,22,… which is giving us much less information. So “strong” basically means “tells us a lot”.

    The rule of thumb is us that negating something strong — that is, pretty informative — gives us something weak — that is, not very informative — and vice versa. Therefore, de Morgan’s laws

  • “not (P and Q)” is the same as “(not P) or (not Q)”
  • “not (P or Q)” is the same as “(not P) and (not Q)”
  • are exactly what you would expect. The first law negates the strong statement “P and Q” and gets a weak statement “(not P) or (not Q)” and the second law negates a weak statement and gets a strong statement.

    For another example, consider the statement

  • This room is INCREDIBLY INCREDIBLY HOT.
  • That, I hope you will agree, is strong information: it describes a most unusual state of affairs. So we would expect that negating it produces a very weak statement. And indeed, if I were to say,

  • This room is not INCREDIBLY INCREDIBLY HOT.
  • you might well give me a funny look and ask, “Was there some reason that you expected it to be?” Note that the rule of thumb gives us a quick way of seeing that the negation of “This room is INCREDIBLY INCREDIBLY HOT” is not “This room is INCREDIBLY INCREDIBLY COLD.” After all, the second statement is also very strong, and we do not expect the negation of a strong statement to be strong.

    Double negatives.

    I haven’t mentioned all the basic logical laws that concern AND, OR and NOT. One important one is the rule that two NOTs cancel. If I say, “It is not the case that A is not a subset of B” then I mean that A is a subset of B. In general, “not (not P)” is the same as P.

    We can actually use that to deduce the second de Morgan law from the first. Here they are again.

  • “not (P and Q)” is the same as “(not P) or (not Q)”
  • “not (P or Q)” is the same as “(not P) and (not Q)”
  • To deduce the second, let me begin by applying the first to “not P” and “not Q”. (What I’m doing here is just like what you are allowed to do with an identity: I am substituting in a value. In this case, the first statement holds for any statements P and Q, so I am substituting in “not P”, which is a perfectly good statement, for P and “not Q” for Q.) I get this.

  • “not(not P and not Q)” is the same as “not not P or not not Q”
  • I’ve decided to dispense with some brackets here. Again just as with equations, there are conventions about what to do first when you don’t see brackets. And the convention is “do all your NOTs first”. So here “not P and not Q” means “(not P) and (not Q)”. It does not mean “not (P and not Q)”.

    Using the rule that two NOTs cancel, we can simplify the above law to this.

  • “not(not P and not Q)” is the same as “P or Q”
  • Now we can “apply NOT to both sides” (just as with equations, if two things are the same and you do the same to both then you end up with two things that are still the same). We get this.

  • “not not(not P and not Q)” is the same as “not(P or Q)”
  • And finally, using once again the fact that two NOTs cancel, we get to the second de Morgan law.

  • “not P and not Q” is the same as “not(P or Q)”
  • A philosophical digression.

    It would annoy some people if I left the discussion here, because some mathematicians feel strongly, and to many other mathematicians puzzlingly, that two NOTs do not cancel. That is, they maintain that “not (not P)” is not the same statement as P. That is because these mathematicians do not believe in the law of the excluded middle. If you believe that every statement is either true or false, then you can define (as I did) “not P” to be the statement that is true precisely when P is false and false precisely when P is true. But what if a statement doesn’t have to be true or false?

    I don’t recommend worrying about this, but let me try to explain why mathematicians who ask this kind of question are not mad (or not necessarily, at any rate). There are at least three reasons that one might decide, in certain contexts, that not every statement has to be true or false.

    The first is when we are dealing with statements that are not completely precise. Let me illustrate this with a few ordinary English sentences.

  • Tony Blair is happy.
  • The weather is awful.
  • He was out LBW.
  • Abolishing the 50% tax rate would be unfair.
  • Democracy is better than dictatorship.
  • Do you want to say of each of those sentences that there must be a fact of the matter as to whether they are true or not (even if we might not know which)? Sometimes we can be pretty sure that Tony Blair is happy, but what about when he had just got up this morning and was cleaning his teeth? Was it definitely the case that one of the two statements, “Tony Blair is happy” or “Tony Blair is not happy” was true and the other false? (Here I’m interpreting the second statement as “It is not the case that Tony Blair is happy”.) A more reasonable attitude would surely be to say that being happy is a rather complex and not entirely precisely defined state of mind, so there is a bit of a grey area.

    If you concede that there is this grey area, then how should you interpret the following sentence?

  • It is not the case that it is not the case that Tony Blair is happy.
  • Or to put it more concisely, “not not (Tony Blair is happy)”.

    When P is a vague sentence like “Tony Blair is happy” then it seems to me that a reasonable interpretation of “not P” is that it is sufficiently clear that P is false for it to be possible to state that confidently. Under this interpretation, “It is not the case that Tony Blair is happy” means that he is sufficiently clearly not happy for it to be possible to say so with confidence. Then “It is not the case that it is not the case that Tony Blair is happy,” means something like “It is clear that we cannot be clear that Tony Blair is not happy,” which is not the same as saying “It is clear that Tony Blair is happy.” When we say “Tony Blair is happy” we are ruling out the grey area, but when we say “not not(Tony Blair is happy)” we are allowing it. (Why? Because if Tony Blair’s mood is not clear to us, then we clearly cannot say with confidence that he is not happy, and therefore not not(Tony Blair is happy).) Perhaps if you asked him whether he was happy he would give a small sigh and say, “Well, I’m not unhappy.”

    Yes, you might say, but the great thing about mathematics is that it eliminates vagueness. So surely the above considerations are simply irrelevant to mathematics.

    That is by and large true, so let us consider a second type of statement.

  • There are infinitely many 7s in the decimal expansion of \pi.
  • e+\pi is irrational.
  • These are both famous unsolved problems. So we don’t know whether they are true or false. Worse still, Gödel has shown us that it is at least conceivable that one of these statements (or another like it) cannot be proved or disproved. (That’s a bit of an oversimplification of what Gödel’s theorem says, for which I apologize to anyone it irritates.) So if we don’t have a proof, or even any certainty that there is a proof, what gives us such a huge confidence that these statements must have a determinate truth value? What does it mean? The problem now is not vagueness, but rather the lack of any accepted way of deciding whether or not the statement is true.

    Suppose, for example, that we try to argue that even if we don’t know whether e+\pi is irrational, there must nevertheless be a fact of the matter one way or the other. We might say something like this: either there are two integers p and q sitting out there such that e+\pi=p/q or there aren’t. In principle we could just look through all the pairs of integers (p,q) and check whether they equal e+\pi. Either we would find a pair that worked, or we wouldn’t.

    Hmm … what is this “in principle” doing here? We live in a finite universe, so we can’t just look through infinitely many pairs of integers. So what happens in the actual universe? We find that at any one time the best we can hope for is to have looked through just finitely many pairs (p,q). What can we conclude if none of the corresponding fractions p/q is equal to e+\pi? Precisely nothing about whether e+\pi is irrational.

    Note, incidentally, that another “infinite algorithm” for solving the problem would simply be to work out the entire decimal expansion of e+\pi and then go back and see whether it is a recurring decimal or not. Again, we can’t do this algorithm in practice because we live in a finite universe.

    As a result of considerations like these, some mathematicians do not agree that a statement like “e+\pi is irrational” must have a determinate truth value. So again we have a grey area, but this time the reason is not vagueness but rather the lack of a proof.

    I should also make clear that most mathematicians (I think) do believe that there must be a fact of the matter one way or the other, regardless of what we can prove. I myself don’t, but I am in the minority there.

    A third reason for abandoning the idea that every statement must be either true or false is to insist on stricter standards for what counts as true. If you would like some idea of what I mean by this, I refer you to the excellent comment by Andrej Bauer below, and also to the Wikipedia article on intuitionism.

    [This section was rewritten in response to criticisms from Andrej Bauer and Michael Hudson-Doyle below. There is no reason to set it in stone at any point, so further criticisms are welcome if you have them.]

    Generalizing de Morgan’s laws.

    If you feel like doing a little exercise, you could try using de Morgan’s laws together with the associativity of addition to deduce that

  • “not(P and Q and R)” is the same as “(not P) or (not Q) or (not R).”
  • If you manage it, then that is a good sign: you are probably at, or well on the way to, the level of understanding of and fluency with “and”, “or” and “not” that you need to do undergraduate mathematics.

    SPOILER ALERT — I’M ABOUT TO GIVE A SMALL HINT, SO IF YOU DON’T WANT IT THEN SKIP THE NEXT SENTENCE, WHICH IS IN FACT THE LAST SENTENCE OF THIS POST.

    Hint: You should begin by putting the brackets back in and writing “P and (Q and R)” instead of “P and Q and R”.

    About these ads

    40 Responses to “Basic logic — connectives — NOT”

    1. Anonymous Says:

      One small correction. You wrote:

      Or to be a bit clearer about it, the statement “not (P and Q)” is the same as the statement “(not P) _and_ (not Q)”.

      I believe this should read:

      Or to be a bit clearer about it, the statement “not (P and Q)” is the same as the statement “(not P) _or_ (not Q)”.

      This is from the paragraph beginning, “What happens here is that NOT turns AND into OR.”

      Thank you for writing this excellent series. I am beginning undergraduate mathematics, though not at Cambridge, and think it will be very helpful to me.

      Thanks — I’ve corrected it now.

    2. andrejbauer Says:

      I really, really like this series of posts. I will direct my freshmen to it and highly recommend that they should read it.

      That said, I think the explanation of intuitionistic reasons for not accepting that two negations cancel is not a very good one. I have heard it many times and it never made any sense to me. Intuioionistic mathematicians do NOT think that there are vague statements, or statements with fuzzy, or mysterious in-between truth values (after all, it is intuitionistically the case that there is no truth value which is neither true nor false). Rather, intuitionistic mathematics has a different STANDARD OF WHAT TRUTH IS. Intuitionisticially, truth is not about how things happen to be, but rather about METHODS for finding out how things are. A statement is taken as true if there is a method for demonstrating it. For example, let us take the statement “Every infinite binary sequence either contains a 1, or all of its terms are 0″. This is obviously true classically. (Indidentally, intuitionistically it is obvious that there is no sequence which neither contains 1 nor is it all 0’s). But to establish the statement intuitionistically, we have to provide a method which decides, given a sequence, which of the two options hold. Whether such a method exists will depend on details such as: what do we mean by “method”, what does it mean that a “sequence is given”, what does it mean “to decide”, etc? Two explanations which helped me are: (1) think of method as “algorithm” and objects “given” as data structures, and (2) think of method as “continuous map” and objects “given” as points of a topological space. Under interpretation (1) our statement is invalid because there is no algorithm for deciding whether an infinite binary sequence (given as a program) is all 0’s. Under interpretation (2) our statement is invalid because the sequence of all 0’s is not an isolated point in the Cantor space $2^N$. If we took a more powerful notion of method, we could in fact make our statement intuitionistically true.

      • gowers Says:

        Many thanks for that — I wasn’t as confident of my explanation as I might have seemed to be. I should also say that I wasn’t really claiming that the phenomenon of vagueness was at the heart of the intuitionistic critique of classical mathematics, though I can see how what I wrote could be taken that way. Anyhow, thanks for your explanation. I’ll put a pointer to it in the post.

      • Gen Zhang Says:

        I’d like to add a little motivation to this (by no means the only motivation): computer algorithms are fundamentally finitary. There is a huge field of computational geometry which pretty much only has an existence because classical geometry assumes things like comparability of reals — whereas in reality it’s simply uncomputable whether two arbitrary reals are the same (note that it’s possible to be sure they’re different!).

      • Jack Says:

        “A statement is taken as true if there is a method for demonstrating it.”
        Hmm, can I say that this is more or less a matter about how one deals with INFINITE? As in the Peano axioms, mathematical induction is one of the axioms, which I think, is not accepted by the “intuitionistic mathematics”.

    3. Richard Baron Says:

      I am not at all shocked at the modest simplification of the content of Gödel’s first incompleteness theorem, but I am a little taken aback at the convention that “if” should be read as “if and only if”. Is this what mathematicians always do? I practise woolly philosophy, not precise mathematics, but I would have thought it would be safer to distinguish explicitly between “if” and “if and only if”, especially since the latter can be typed “iff”, which only demands one extra letter.

      On a pedagogical note, I wonder whether it is wise to use locutions like “p if q”. When one moves on to symbols, the student’s first inclination may be simply to put the arrow in place of “if”. But if the arrow runs from left to right, as it usually does, the expression then says the wrong thing: q if p. (This becomes the right thing if all ifs are iffs, but I have my doubts about that, as already noted.) It might be safer to start with locutions like “if p then q” (“If n = 2m then n is even”). Then putting in the arrow leaves the meaning unchanged. The disadvantage is that there is not just one word to replace with an arrow: the arrow has to replace “then”, and the “if” has to be deleted. But I hope it would seem natural to put the arrow in the middle, not at the start.

      • andrejbauer Says:

        @Richard: “if’ definitely gets used as “if and only if” in definitions, which is what the blog post talks about. In theorems mathematicians never confuse “iff” and “if and only if”. I think the word “when” is a good subtitute for “if” in definitions.

      • andrejbauer Says:

        Oh my, that “iff” shuld have been “if”. My apologies.

    4. Anonymous Says:

      Dear Professor Gower

      If you ever manage to get that bank account open you may find paying for you MOT online rather convenient too.

      Best regards,

      Daniel

      • gowers Says:

        I presume you mean the tax disc. The trouble with that is that it involves paying at least a week before you need the disc. That demands a level of organization that I don’t possess …

    5. Mark Bennet Says:

      On the MOT test … a long time ago Michael Flanders said something like “Now they want to test my car after I’ve had it for three years. Eventually they’ll get round to testing it before it leaves the factory.”

    6. ina Says:

      After en.wikipedia.org/wiki/Logical_connective , another good Wikipedia article is: http://en.wikipedia.org/wiki/Boolean_algebra. It shows how connectives are extended to set operations. It is then fun to generalise digital true/false values of 0 and 1, into probabilistic or fuzzy truth values for any real number between 0 and 1 ( or even weirder number systems or algebraic structures) and get fuzzy sets or probabilistic sets and see how logic connectives and set operations are extended to real numbers or weirder.

    7. ina Says:

      Another path to generalization is “n-ary logic”, although the term “n-ary” is ambiguous here because if you compare it to binary logic you might think n-ary means n-valued logic instead of 2-valued logic, but “n-ary” could also refer to the arity of the operations rather than the value-range of the logic. e.g. “and” and “or” are called binary-operations not because of the values 0 and 1 but because they take two arguments e.g. (x and y). (x or y). So a 3-ary “and” operator would be like 3and(x,y,z) and there are n-ary generalizations of distributivity e.g. (m,n)-rings with multiplication distributive over n-ary groups. And then you can get really weird with something like http://arxiv.org/abs/0808.3109

    8. Greg Martin Says:

      @andrejbauer: thank you for that nice explanation of intuitionistic math.

      @Richard Baron: it’s a convention (perhaps unfortunate, but nearly universal) that “if” should be read as “if and only if” *in definitions* (not in general). The rationalization, perhaps, is that every definition is an if-and-only-if statement (by definition?), so we suppress a few words.

      Pedagogically, I agree that I would avoid phrasing statements in the form “p if q” when teaching logic … why leave in more possibilities for confusion. However, I disagree with the reasoning that “p if q” is bad because it makes conversion to symbols harder. Using arrows and other symbols isn’t a way to understand logic – it’s a shortcut to use once logic is already understood. I much prefer keeping everything in sentence form: even when I write on the board during lectures I use sentences and words instead of arrows, upside-down A’s and E’s, and so on. I feel it’s closer to how we think, and I also feel it lessens the chance of confusion for the student – provided, of course, that we use unconfusing sentences whenever we can.

      • Terence Tao Says:

        I think the convention “if means iff for definitions” can be justified by observing that interpreting “if” as a simple material implication does not actually yield a definition, whereas interpreting “if” as an if-and-only-if does. So one can deduce this convention by elimination of the alternatives.

      • ML Says:

        The worry about using “if” to mean “iff” is that one won’t recognize an intended definition as a definition. If the whole context is prefaced by the word “Definition”, as it often is in math papers, then Prof. Tao’s justification works. If not, it doesn’t necessarily work.

      • mg262 Says:

        Even outside explicit ‘Definitions’, definitions are usually flagged in a couple of ways:

        1. In textbooks, terms being defined are generally in italics, bold or both. Many lecturers underline terms being defined in the same way.
        2. A large proportion of definitions use one of six or so special ‘defining’ verbs, such as ‘call’. (E.g. ‘We call f an injection if …’.) These verbs unambiguously tell you that you are dealing with a definition instead of an assertion.

        So there’s a little room for confusion, but not very much.

    9. Terence Tao Says:

      You’ve already touched upon this point in the post, but one feature of negations is that “not (adverb) (adjective)” is different from “(adverb) not (adjective)”, thus for instance “not incredibly hot” is not the same as “incredibly not hot”.

      When I first taught analysis, I used to use “absolutely divergent” and “conditionally divergent” as negations of “absolutely convergent” and “conditionally convergent” respectively. Only later did I realise just how confusing this was, and now avoid these terms (using instead “not absolutely convergent” or “not conditionally convergent” instead).

    10. Oscar Cunningham Says:

      The convention that “if” replaces “iff” in definitions is unusual for the following reason. Normally a bad convention is held in place because the effort and coordination required to change is too great. This is why current flows in the opposite direction to electrons, for example. But in this case this doesn’t hold true. Putting “iff” in your definitions isn’t going to confuse anybody, it will just make your definition more precise, which is a good thing. So why does no-one do it?

      • Doug Spoonwood Says:

        I’m not entirely sure, but I think there exist some authors who don’t think an “if” in a definition really means “iff” (I don’t understand how they think this, and I don’t recall where I read this). Also, if definitions have “iffs” in them, then one might claim that anywhere we can have an “iff” we can have a definition (as I understand them, the Polish school of logicians around the 1920s held this position). This would allow for very strange definitions as permissible, like in classical propositional logic defining the “weak law of identity” as “hypothetical syllogism” or any other theorem of classical propositional logic, e. g. I could define Cpp as CCpqCCqrCpr or CqCpq or any other theorem. Perhaps that isn’t a good criticism, perhaps very strange definitions should come as permissible. And perhaps that isn’t why “iff” gets avoided in definitions, but perhaps it does.

    11. Michael Hudson-Doyle Says:

      If you want these posts to be referenced and read at a later date, I’d recommend rewriting the philosophical discussion in terms of how Andrej Bauer puts it – I think it goes off into the weeds a bit as it is!

      Otherwise, I’m enjoying this series!

      • gowers Says:

        Actually, I stand by what I wrote in that section, except that it should not be taken as a description of intuitionism. That is, it is genuinely the case that the law of the excluded middle is not obviously appropriate for vague statements, and it is genuinely not clear to a non-Platonist like me that every well-formed mathematical statement should have a determinate truth value. What I might do is rewrite the passage to make it clearer that by expressing these views I am not describing intuitionism.

    12. George Says:

      Terence Tao has a multiple-choice Java Applet at http://www.math.ucla.edu/~tao/java/MultipleChoice/MultipleChoice.html

      One of the categories is Logic. If you are a student who is not sure if you already know the material in these posts here on logic then it might be worthwhile to try the 16 multiple choice logic questions on Terence Tao’s web and see how you do.

      Conversely if you know you did not know the material in these posts but now after reading them you think you do it might be worthwhile to test yourself and see if you do!

    13. Spencer Says:

      Just a short remark: You may have mentioned this already, I have not checked carefully, I admit, but since (Cambridge) term doesn’t start for at least another week, you might like to take care not to post too much material ahead of the beginning of term. If when a first-year student is told about this series of posts at the beginning of the Cambridge term, there are already four or five posts, then it looks like quite a lot of extra work already on top of a workload they are probably apprehensive about… even the obviously once you are up-to-date, keeping up-to-date is relatively easy.

      • gowers Says:

        I’m not quite sure what to think about that. On one side is the argument you give, while on the other is the argument that these posts are preliminary, and therefore best understood before term starts. I genuinely don’t know what the best policy is.

      • Aspirant mathmo Says:

        As an incoming Cambridge mathematics fresher, I’d say that much of what Professor Gowers has currently posted on basic logic is material many new undergraduates are likely to be familiar with, yet may not have encountered formal definitions/ explanations of. Although having a long list of posts may seem intimidating, the actual content of the introductory logic posts is not especially challenging if it has been encountered informally beforehand (yet it is still extremely worthwhile reading). My understanding of the first post in the series was that the logic posts are something of a “warm-up” for the rest of the blog… Given that much of this material may otherwise go assumed/unclarified by lecturers, I think the current approach of a post every couple of days on basic logic is a good way to go. That way, most of the basic logic can be dealt with before we start meeting more juicy material in lectures. I don’t know how many freshers will actually be reading this blog before lectures start though. Many thanks to Professor Gowers for the blog so far: I’m looking forward to reading more!

      • gowers Says:

        That’s quite reassuring. The intention was that it should be possible to read the posts without continually having to stop and think, or, worse, backtrack. If I’ve done what I wanted, then although the posts are quite long, they are also quicker to read than a much shorter segment of a textbook. Also, I have written a summing-up post that’s much shorter, so I’m hoping that people will read the longer posts fairly quickly, but not feel that they have to hold everything in their heads straight away (though eventually this is all stuff a mathematician needs to know). Rather, they can get the general idea from the longer posts and refer back to the summary if they need reminding of the key points. Or some people might prefer to read the summary and then refer to the posts if they find parts of the summary that they are not comfortable with.

        I’ll also repeat that if anyone reading this knows other freshers who might not know about it, I’d be grateful if you could spread the word.

      • Spencer Says:

        @gowers I agree. Which includes admitting that my remark was not helpful in any practical way. I don’t know what’s best either.

        @ Aspirant mathmo As you point out, the material won’t be too far removed from what the average incoming student already sort-of knows (though maybe just not presented in this style, like you say). However, despite it being difficult for me to imagine not having heard of Professor Gowers and his blog, I think even at Cambridge it might be a bit too optimisitc to suppose that the `average’ incoming student reads Gowers’s blog. One might even go so far as to argue that it is the less obviously ambitious students, i.e. those who aren’t already doing keen things like reading maths blogs that will need this kind of extra support the most.

        I don’t really know the answer, but I’ll at least make sure the first years at my college hear about these posts sooner rather than later in order to minimize the possible negative effect I conjectured. Regardless of how you choose to continue, I very much look forward to future posts. Many Thanks.

    14. Spencer Says:

      I was writing my 5.18 post before seeing your 5.14 post most recent one.

      Summaries and minimizing the need to backtrack seem like very good ways to help avoid the issues we’re talking about.

      • gowers Says:

        I think I’ll add a remark at the beginning of the first post, to the effect that the length of the posts is supposed to be offset by the ease with which they can be read.

    15. Roger Says:

      Lawyers and legal documents use double negatives all the time. A lawyer might say, “My client did not say a false statement.” This is taken as slightly weaker than “My client only made true statements.”

      You have some similar examples, but ordinary usage is sometimes just sloppiness. When double negatives are used in court, it is usually an attempt to use the words precisely.

    16. andrejbauer Says:

      @Roger: No. Induction is of course accepted by intuitionistic mathematics (where did you hear it wasn’t?!). The law of excluded middle has nothing to do with infinity, as it can fail on finite domains just as well.

    17. kim Says:

      professor Timothy,

      I have a question. It seems that the falsehood of a given statement is being defined in terms of the truth of another statement. How do we define truth? If we defined truth in terms of falsehood is there any circularity?

      Thanks.

    18. kim Says:

      You’ve also described two scenarios. One is where there are only two possibilities for the negation of a statement so it is unambiguous. But the other scenario is where there are several possible statements which imply the falsehood of the statement and we want to pick the one which is ‘least sufficient’. Is that always obvious?
      In the example where ‘a is not the largest element of A’, we could show that a is the least element of A or that there exists b and c such that b is larger than a and c is larger than a. Don’t these statements still prove that a is not the largest element of A?

    19. kim Says:

      Sorry I meant to write ‘there is only one possibility’.

    20. kim Says:

      could you explain what happens in a one element set. Is the element both the largest and the smallest?

    21. A Trip to Mathematics: Part-I Logic | MY DIGITAL NOTEBOOK Says:

      [...] Basic logic – connectives – NOT (gowers.wordpress.com) [...]

    22. godspeasant Says:

      I have had the following questions roaming around in my head for a while and I want to ask an expert on this subject for clarification. I am sure that these questions have been asked on numerous occasions since the dawn of man, but I would like to address them here again if I may.

      Aren’t you using logic to prove logic to be true? And isn’t that circular? I personally have my doubts over this true and false dichotomy through the observation of our universe. Surely, logic is a man-made creation that uses man-made definitions to describe events or object’s behavior. Indeed, it seems to be working well for day to day activities and has advanced us in society. But to say that something is true or that something is false is no different than saying that something is hot or cold, light or dark, positive or negative, matter or space. These can be vague depending on how you define it, but the definitions I give them below I think are precise.

      The examples I gave above do not truly exist in this universe, because one is the absence of the other. For one to exist, the other has to cease to exist. If we consider one degree above absolute zero as “heat”, or if we were to define one photon of light as “light”, or one proton as “positive”, then what we measure as cold, dark, and negative are nothing more than the absence of heat, photons, or protons. It seems to be that we have given the negation a definition when there is nothing there to define. Can nothing be defined?

      The space or matter definition needs to be defined on its own. One cannot have matter without it being contained in space itself. For example, a lake requires the rocks and the sand underneath it to exist; it couldn’t just float in the air. Even if it did float in the air, it requires the space in the air to float. In other words, matter needs a placeholder or container to exist.

      So there seems to be two values, hot vs cold, light vs dark, positive vs negative, matter vs space, but since one is the absence of the other, only one true value really exists. In one of your talks, “The Importance of Mathematics”, you give a presentation of knots. The knot at the very bottom of the slide represents what I am talking about in this post (and is my profile picture, the infinity symbol). It seems like there are two sides and two circles in the equation, but if you untwist the infinity symbol, or the symbol you had in your presentation, you get one circle. Therefore it seems as if these are two separate identities in our universe, but they are all just one in reality.

      I am very interested in this discussion, and if you can point me in the right direction, or if you can provide me with some writing or explanation of how the points I made here are flawed or supported, I would greatly appreciate it.

      Having said all that, I really appreciate the time you have put aside to educate people in writing. I am a strong supporter of this movement and I applaud your dedication towards the study of mathematics.

      Thank you again,
      Nima Farzaneh

    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,545 other followers

    %d bloggers like this: