A little paradox

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

If you are reasonably comfortable with the kind of basic logic needed in an undergraduate course, then you may enjoy trying to find the flaw in the following argument, which must have a flaw, since I’m going to prove a general statement and then give a counterexample to it. If you find the exercise extremely easy, then you may prefer to hold back so that others who find it harder will have a chance to think about it. Or perhaps I should just say that if you don’t find it easy, then I think it would be a good exercise to think about it for a while before looking at other people’s suggested solutions.

First up is the general statement. In fact, it’s a very general statement. Suppose you are trying to prove a statement Q and you have a hypothesis \forall x\in X\ P(x) to work with. In other words, you are trying to prove the statement

(\forall x\in X\ P(x))\implies Q\ .

Now if R and S are two statements, then R\implies S is true if and only if either R is false or S is true. Hence what we are trying to prove can be rewritten as follows.

(\neg(\forall x\in X\ P(x)))\vee Q\ .

Now we can bring the \neg inside the \forall as long as we convert the \forall into \exists, so let’s do that. What we want to prove becomes this.

(\exists x\in X\ \neg(P(x)))\vee Q\ .

I’ll assume here that we haven’t done something foolish and given the name x to one of the variables involved in the statement Q. So now I’m going to use the general rule that (\exists x\in X\ R(x))\ \vee\ Q is equivalent to \exists x\in X(R(x)\ \vee\ Q) to rewrite what we want to prove as the following.

\exists x\in X\ (\neg(P(x))\ \vee\ Q)\ .

Finally, let’s rewrite what’s inside the brackets using the \implies sign.

\exists x\in X\ (P(x)\implies Q)\ .

Every single step I took there was a logical equivalence, so the conclusion is that if you want to show that \forall x\in X\ P(x) implies Q, your task is the same as that of finding a single x\in X such that P(x)\implies Q.

Now let me give a counterexample to that useful logical principle. Let X be a set of real numbers. Define the diameter of X to be \sup\{|u-v|:u,v\in X\}. I’ll write it \mathrm{diam}(X).

Consider the following implication.

(\forall x\in X\ |x|\leq 1)\implies\mathrm{diam}(X)\leq 2\ .

That is clearly correct: if every element of X has modulus at most 1, then X is contained in the interval [-1,1], so clearly can’t have diameter greater than 2.

But then, by the logical principle just derived, there must be a single element of X such that if that element has modulus at most 1, then the diameter of X is at most 2. In other words,

\exists x\in X\ (|x|\leq 1\implies\mathrm{diam}(X)\leq 2)\ .

But that is clearly nonsense. If all we know is that one particular element of X has modulus at most 1, it can’t possibly imply that X has diameter at most 2.

What has gone wrong here? If you can give a satisfactory answer, then you will have a good grasp of what mathematicians mean by “implies”.

About these ads

56 Responses to “A little paradox”

  1. Noone Says:

    This is NOT the solution to the paradox: in the general logic statement, you need X non-empty in order to use the general rule that existential quantification commutes over disjunction.

  2. Jason Rute Says:

    This is like the paradox: “There exists a person x at the pub such that if x is drinking, then everyone is drinking.” (Think worst case scenario, i.e. the teatotaler if there is one.)

  3. Tom Says:

    This reminds me of 3 here: http://www.vex.net/~trebla/weblog/any-all-some.html (It is the “paradox” as Jason mentions).

  4. Tom Says:

    Tim: do you think it’s worth making a new post for those who want to make “spoiler” comments without giving anything away to others working on the problem?

  5. Terence Tao Says:

    In a similar spirit: it is an easy theorem that there exists a real number T such that if all zeroes of the Riemann zeta function on the strip \{ \sigma+it: 0 \leq \sigma \leq 1; 0 \leq t \leq T \} lie on the critical line, then the Riemann hypothesis is true. Unfortunately, T is ineffective, and this does not reduce RH to a finite computation…

  6. Veky (@veky) Says:

    There is no mathematical error here. ;-)

  7. Gavin Says:

    This comment contains spoilers (unless it is wrong).

    In the last formula, it is asserted that there is one value of x for which the bracketed formula is true. Using that an implication is true only if either the part after the arrow is true, or the part before the arrow is false, then there are two possibilities depending on whether diam(X) le 2. If diam(X) le 2, then the part after the arrow is true, and so the bracketed part is true for all x. If diam (X) gt 2, then the formula reduces to stating that there exists an x such that |x| > 1. Since we assumed that diam (X) > 2, it is easy to prove that such an x exists. So the formula is confirmed to be true.

    I believe the paradox results from misinterpreting the scope of the existential qualifier. It does not say (there exists x with |x| <= 1) implies (diam (X) <= 2). There might be another way to misinterpret it, but I'm not sure. It is a funny statement: you are saying that there is an x for which the implication is true, and since this x exists, we can deduce the right-hand side of the implication (that latter part is the incorrect bit). It is as if we've used x twice. Of course, the implication is true only in the logical, truth-table sense – not in a "proof" sense.

    (please delete other comments – part of it disappeared due to problems with less than and greater signs)

  8. hjk Says:

    Let x be the element with the greatest modulus.

    • gowers Says:

      What if there isn’t such an element?

    • hjk Says:

      Ah. Oops. So what I wrote would have to just be more of an intuitive explanation of why there’s no paradox – the goal is to find the special x which makes the predicate [mod(x) -> diam(X) leq 2] true. To actually prove it, it is probably easier to use some other logical form, like the first one, than actually constructing the element.

      The part following “But that is clearly nonsense” would best translate as

      [There exists an x, s.t. mod(x) leq 1] -> [diam(X) leq 2]

      which is a different logical statement (e.g. here -> connects two statements to create a new statement, as opposed to constructing a new predicate requiring further quantification as in the first case).

      Is this related to the idea that when mathematicians informally write something like

      P(x) implies Q

      they really/usually mean something like

      (For all x)[P(x) -> Q]

      where -> is a connective between predicates/statements, while implies is a statement about predicates/statements? So saying

      There exists an x such that P(x) implies Q

      would be better said as

      (There exists an x such that)[if P(x) then Q],

      or

      (There exists an x such that)[P(x) -> Q],

      where ‘->’ and ‘if…then’ are simply understood as defining a new statement/predicate from two other statements/predicates, which may require further quantification to be true or false.

    • hjk Says:

      …assuming that this is the intended meaning of “There exists an x such that P(x) implies Q”.

      The alternative translation being

      [There exists an x such that P(x)] -> [Q]

      which, again, is a different statement and where the ambiguity arises.

      (PS I have a theory that if anyone follows up on a particularly short comment they leave on the internet then the next comment(s) they leave will be excessively long and unclear).

    • hjk Says:

      So I’d summarise by saying that when trying to make a mathematical (as opposed to metamathematical) statement as clearly as possible, it’s best to stick to if…then language, without the word ‘implies’.

      This clarifies the difference between eg

      If [there exists an x st P(x)] then [B]

      and

      (there exists an x st) [if P(x) then B]

      as mathematical statements.

      ‘If…then’ can then be clearly discussed in terms of compound statements. The rules for proving such statements (metamathematical rules) can be discussed separately, in terms of ‘implies’ etc if need be.

  9. Theresia Says:

    I think that it is unfortunate that people often insist on logical definitions of “implies” with students who are seeing proofs for the first time. Then at the exam, the student writes a logically correct implication and it is marked wrong.

    You give a nice example, but I think that it is more complicated than necessary for the actual issue, unless you disagree with me about the issue.

  10. Lior Silberman Says:

    First, after the first formula you are always using “implies” in the propositional sense rightarrow despite keeping the notation Rightarrow from the logical implication in the first formula.

    Second, in your argument with logical implication you are ignoring the fact that X is also a variable in the formula — and (being the free variable) it needs to be chosen first. Once X is chosen, it has a member which signals whether the diameter is more than 2 (see jhk’s answer above)

    • gowers Says:

      Your second paragraph is roughly the answer I would also give. But I think you meant to say that once X is chosen, it has a member that signifies whether the implication (in the truth-table sense) is correct.

  11. tyr42 Says:

    I’m having a hard time with it. I found one case where this doesn’t hold, and that’s if the set X is empty, thus making anything that starts with \exists x \in X vacuously false. But that’s not the whole problem with it.
    Is the error in moving the “or Q” inside the exists clause?

  12. mlb Says:

    there exists an x is the outermost qualifier so as long as we can find one value of x such ~P(x) the statement is trivially true since false => Q is always true regardless of Q. Alternatively if we cannot find an X where abs(x)>1 then Diam(X) is in fact less than 2 so the final statement is true just misdescribed

  13. Siddhartha Gadgil Says:

    Most people will consider

    False => True

    to be nonsense as well, and the same with

    (1=2) => All elephants are pink

    Vacuous implication is a wonderful thing.

  14. Cristóbal Camarero Says:

    A formalization in Coq. Note that we need some inhabitant of X.

    Require Import Classical.
    Theorem paradox:
    forall (X:Type) (P:X->Prop) (Q:Prop) (dummy:X),
    ((forall x:X, P x)->Q)

    (exists x:X, P x->Q).
    Proof.
    intros. apply conj.
    - intros. apply NNPP.
    intro N.
    assert(R:=not_ex_all_not _ _ N). clear N. simpl in R.
    destruct(classic Q) as [HQ|HQ].
    + specialize(R dummy). apply R. auto.
    + apply HQ. apply H. intros. specialize(R x).
    apply NNPP. intro N. apply R. intros HP. exfalso. auto.
    - intros E H. destruct E as [x Hx]. apply Hx. apply H.
    Qed.

  15. Tom Says:

    Spoilers within!

    As has been pointed out, the formula is indeed correct. What seems to be “incorrect” is using the English word “implies” in our interpretation of the formula. It is an unnatural usage.

    However, if you replace the existential with a function mapping $X$ to an $x$ that the existential guarantees to exist (a procedure called Skolemization) the interpretation becomes much more natural. The formula becomes “$f(x) \le 1 \Rightarrow diam(X) \le 2$” which *is* natural to read as “implies” as we realise we can take $f$ to be “an element of maximal modulus”.

    (Actually that interpretation of $f$ doesn’t quite work, as a maximal element need not exist. You could take f to be “an element of $X$ of modulus $\le 1$ if one exists, otherwise one of modulus $\gt 1$ and the interpretation of the formula become slightly less natural, but still works will I think).

  16. Terence Tao Says:

    One can also use modal logic to clarify the apparent disconnect between what is formally true and what is “intuitively” true. Working in a modal universe in which X varies (or in a subtly different universe in which X is a fixed set of variables, but the numerical values assigned to these variables vary from universe to universe), the problem is that the necessitation quantifier \Box does not commute with the existential quantifier \exists. In particular, the sentence

    \Box \exists x \in X: (|x| \leq 1 \implies \hbox{diam}(X) \leq 2)

    is true, but the sentence

    \exists x \in X: \Box (|x| \leq 1 \implies \hbox{diam}(X) \leq 2)

    is not; the problem is that the x that exists in the first sentence is not uniform across all possible worlds.

    • Terence Tao Says:

      (small correction: “vary from universe to universe” should be “vary from world to world”, where one thinks of the modal universe as a collection of many possible worlds.)

  17. Emilio Says:

    I think the main mistake is to confuse the logical inference rule called “modus ponens” of first-order logic with the logical connective “if … then …” propositional calculus, when in fact he says, “Now if R and S are two statements, then R → S is true if and only if either R or S is false is true.” And this is the alternative way of making it in the propositional calculus, the logical connective “→” by the connectives “¬” and “∨”. In fact, if Q is what you have to prove, Q can be deduced from the fact that ∀ x ∈ XP (x) is true and that
    ∀ x ∈ X P (x) → Q is true (“modus ponens”). Instead, in the propositional calculus, the proposition ∀ x ∈ XP (x) → Q is true, not only when ∀ x ∈ XP (x) and Q are both true, but even when Q is true ∀ x ∈ XP (x) is false.
    Also at the end is well chosen concrete example. If in fact arises
    ∀ x ∈ XP (x) = ∀ x> 0, x * y> 0, and Q = y> 0, at the end is not seen no ‘paradox’.

    • Emilio Says:

      If R and S are two statements, then R→ S is true if and only if either R is false or S is true.
      From ∃x∈X(¬P(x)∨Q) to ∃x∈X(P(x)→Q), Q is a statement, but ¬P(x) is NOT a statement.

  18. NaN Says:

    I’ve noticed precisely such a knot a few times before when using, for want of a better phrase, logical symbol pushing; and each time, instead of resolving it in my head, I’ve taken recourse to ‘natural reasoning’ to avoid confusing \vdash from \implies.

    So, for instance, in order to prove:

    (\forall x \in X ~ |x|\leq 1) \implies (diam(X)\leq 2)

    I would simply assume the antecedent and prove the consequent. That is, I’ve been using the Deduction theorem way before I even knew its name.

  19. NaN Says:

    Somehow my comment above makes me seem less than the idiot that I truly am, so I should add that I don’t know how to resolve this paradox and its making me (only slightly) nervous OR i wish there was an edit button somewhere.

  20. Jean Pierre M. (@genepeer) Says:

    The english translation is not “There must be a single element…” but “There is at least one element…” This interpretation is clearly not nonsense.

    To prove me wrong, you’d have to show that “For all elements of X, their modulus is at most 1 and the diameter of X is greater than 2″ which is clearly nonsense.

  21. Emilio Says:

    If R and S are two statements, then R→ S is true if and only if either R is false or S is true.
    From ∃x∈X(¬P(x)∨Q) to ∃x∈X(P(x)→Q), Q is a statement, but ¬P(x) is NOT a statement.

  22. Emilio Says:

    If I can prove that ALL even numbers are the sum of two primes not necessarily distinct, then I proved Goldbach’s conjecture. If X is the set of even numbers, Goldbach’s conjecture G and P (x) means “to be the sum of two prime numbers blah blah blah …”, this thing can be formally expressed as follows:

    ∀ x ∈ X P (x) → G

    Now, it is known that if A and B are two statements, then the statement A → B is logically equivalent to the statement ¬ A ∨ B. So we have the following logical steps:

    ¬ (∀ x ∈ X P (x)) ∨ G

    (∃ x ∈ X ¬ P (x)) ∨ G

    ∃ x ∈ X (¬ P (x) ∨ G)

    ∃ x ∈ X (P (x) → G)

    After this series of steps that seem all correct, i get the latest formula which means: even if I can find JUST ONE even number that is the sum of two primes then I proved Goldbach’s conjecture!

    • Martin Hairer Says:

      Your first statement is obviously true since it is just the tautology “if the Goldbach conjecture is true then the Goldbach conjecture is true”. The final statement is more subtle, but it is still true. Indeed, either the Goldbach conjecture is true or it isn’t.

      If it is, then the statement is true since any premise (true or not) implies a true conclusion. If the Goldbach conjecture happens to be wrong, then the statement is still true since you will be able to find an even number $x$ which is a counterexample, so that $P(x)$ is false and a false premise implies any conclusion.

  23. asenseofmystery Says:

    The problem is that “implies” in propositional logic is much more broad than the usual English usage of implies, which suggests causation. For instance, any two true statements imply one another in propositional logic, e.g., “The sun rising tomorrow implies Obama is the US President” is a true statement.

    With the example above, in the final implication, either there exists a counterexample to P (there exists an element of x with norm greater than one) and we are in a vacuously true situation. Or else no counterexample exists to P (all elements have norm less than one) and this implies (in the English usage) Q (indeed, diameter less than one means, among other things, that the diameter is less than two). But in this case, whatever x we chose in the existential quantifier, P is true (as well as Q) and we are in the situation where true implies true, in the very weak logical proposition sense.

  24. Vincenzo Iovino Says:

    it seems that the rule of absorbing Q inside the quantifier is not valid.
    In fact the set X could be empty.
    If x is empty the first formula does not imply the latter.
    Q or Exists x in X such thast P(x) is not equivalent to
    exists x in X such that (P(x) or Q).
    In fact the latter is false when X is empty and Q is true.
    The first instead is true when X is empty and Q is true

  25. Niall Says:

    What has gone wrong here? If you can give a satisfactory answer, then you will have a good grasp of what mathematicians mean by “implies”.

    Well, I’m a mathematician and what I mean by implies (A=>B) is that because A is true, it follows that B is true. There’s a finiky three dot symbol for this type of implies or “it follows that”, but I prefer the arrow and I suspect many others do as well.

    Like a lot of mathematical symbols, meaning depends on context. the “=>” symbol in logic has a much more restricted meaning that the “=>” or “implies” used in other branches, where it is treated a more of less a one way “”. In particular “=>” in logic includes the vaccuous case which I don’t even enters in even the slightest way into the vast majority of proofs in mathematics outside of formal logic.

  26. Richard Baron Says:

    I come to this a week late, and what follows may merely re-state what earlier commentators have said.

    The transformation of the task upwards through the chain of reasoning works. If there exists an element such that its being P implies Q, then we can show that Q by showing that all elements are P. (The existence of an element with the property that its being P would imply Q, conveniently tells us that X is not empty.)

    The transformation downwards does not work, as the counter-example shows. The dodgy step is the move from

    (\exists x\in X\ \neg(P(x)))\vee Q

    to

    \exists x\in X\ (\negP(x))\ \vee\ Q)\ .

    This is a move from

    “either there is an x that isn’t P, or Q”

    to

    “there is an x such that either it isn’t P, or Q”.

    The former tells you to check all the members of X (in the example, to check that none has a modulus exceeding 1). The latter tells you that there is some particular member of X which, if it turns out to be P, has magical powers of implication.

  27. JF Puget Says:

    It is all about quantifier scope. i won’t say more in order to not spoil the post.

  28. Κιουβρέκης Γιάννης Says:

    The rule of quantifiers movement which concerns us is:

    \forall x \phi \rightarrow \psi \leftrightarrow \exists x \left (\phi \rightarrow \psi \right)

    with the restriction that the variable x does not appear in \psi .

    The paradox is created because there is no rule

    \left(\left(\exists x \ in X \neg P(x) \right) \vee Q \right) \leftrightarrow \left (\left(\exists x \in X \left (\neg P( x) \vee Q \right) \right) \right)

    regardless if Q has X as free variable .

    More strictly, if we assume that the Q is a single predicate of X ie Q (X) then the propositions

    \forall X \left[\left(\exists x \in X \neg P (x) \right) \vee Q (X) \right] and \forall X\left[\exists x\in X\left(\neg P(x)\vee Q(X)\right)\right] are not equivalent .

    In the language of predicate logic the proposition \forall X \left[\left(\forall x \in X P(x) \right) \rightarrow Q (X) \right]

    is written as \forall X \left [\forall x \left(x \in X \rightarrow P (x) \right) \rightarrow Q \right] and so if we apply the rule of movement of quantifiers we have

    \forall X\left[\forall x\left(x\in X\rightarrow P(x)\right)\rightarrow Q(X)\right] \Leftrightarrow \forall X\exists x\left(\left(x\in X\rightarrow P(x)\right)\rightarrow Q(X)\right)\Leftrightarrow \forall X\exists x\left[\left(x\in X\wedge \neg P(x)\right)\vee Q(X)\right]\Leftrightarrow \forall X\exists x\left[\left(x\in X\vee Q(X)\right)\wedge\left(\neg P(x)\vee Q(X)\right)\right]

    While the proposition \forall X\left[\exists x\in X\left(\neg P(x)\vee Q(X)\right)\right] is written as

    \forall X\left[\exists x\left((x\in X)\wedge\left(\neg P(x)\vee Q(X)\right)\right)\right], hence

    \forall X\left[\exists x\left((x\in X)\wedge\left(\neg P(x)\vee Q(X)\right)\right)\right]\Leftrightarrow \forall X\exists x\left(\left((x\in X)\wedge \neg P(x)\right)\vee\left((x\in X)\wedge Q(X)\right)\right)\Leftrightarrow \forall X\exists x\left(\left(x\not\in X\vee P(x)\right)\rightarrow (x\in X\wedge Q(X)\right)\Leftrightarrow \forall X\exists x\left(\left(x\in X\rightarrow P(x)\right)\rightarrow (x\in X\wedge Q(X)\right)

    Concerning the example you mentioned – which is a proof of why these two propositions are not equivalent – we have that the proposition

    \forall X \left (\forall x (x\ in X \rightarrow | x | \leq 1) \rightarrow diam (X) \leq 2 \right)

    is equivalent to the proposition

    \forall X \exists x \left (\left (x \in X \rightarrow | x | \leq 1 \right) \rightarrow diam (X) \leq 2 \right)

    which creates semantics problems.But if we look the equivalent proposition which is

    \forall X \exists x \left (diam (X)> 2 \rightarrow \left ((x \in X) \wedge | x |> 1 \right) \right)

    which translates “for all X there exists x so that if the diameter of X is greater than 2 then x belongs to X and the distance of x from 0 is greater than 1 ” the semantics problems which the reader may face are less than before.

    If we apply the rule for quantifiers movement

    \exists x (\phi \rightarrow \psi) \leftrightarrow \phi \rightarrow \exists x \psi if \phi has no free occurrences of x then we have the equivalent proposition

    \forall X \left (diam (X)> 2 \rightarrow \exists x \left ((x \ in X) \wedge | x |> 1 \right) \right)

    then the English translation is

    ” For each set X if the diameter of X is greater than 2 then there is an x such that x belongs to X and the distance from 0 is greater than 1 ” and the meaning is obvious.

    ** We used the symbol \rightarrow for the logical operator implies and the symbol \Leftrightarrow for tautologically equivalent propositions .

  29. Martin Hairer Says:

    The final conclusion is indeed “clearly nonsense” but it is nevertheless true (at least if we all agree that X is not empty). Indeed, if the diameter of X is less than 2, then anything would imply that, true or false. If on the other hand the diameter is more than 2, then there it contains an x greater than 1, so that |x| ≤ 1 is false and a false premise implies any conclusion.

    It is equally true that the Riemann hypothesis implies Fermat’s last theorem (Andrew Wiles proved that) or that that the existence of a pink elephant implies FLT (idem). It just breaks the implicit promise that the premise is somehow relevant to the conclusion.

  30. Marc Says:

    Maybe it should be noticed that X remains free in the expression:

    ∀x∈X P(x)

    So this should be rewritten first, I suppose:

    ∃X ( ∀x∈X P(x) )

    Now we could also notice that the fragment:

    ∀x∈X P(x)

    is actually an abbreviation of:

    ∀x (x∈X → P(x)

    which introduces an important shift in the conclusion.
    Indeed,

    (∀x (x∈X → P(x)) → Q

    leads to:

    (∃x)( (x∉X→Q) & (P(x)→Q) )

  31. Mark Dettinger Says:

    I think the error only lies in the verbal description. The last formula is still correct:

    \exists x \in X (|x| \leq 1 \implies diam(X) \leq 2)

    But then the text goes on:

    “But that is clearly nonsense. If all we know is that one particular element of X has modulus at most 1, it can’t possibly imply that X has diameter at most 2.”

    However, the second sentence does not describe the formula correctly. What it describes is this:

    (\exists x \in X (|x| \leq 1)) \implies diam(X) \leq 2

    And yes, that would indeed be nonsense.

    • Leon Says:

      Here is how to get from the last formula to the verbal description: the formula says that there is an x in X such that the following statement holds:

      If all we know is that x has modulus at most 1, then that implies X has diameter at most 2.

      Now this statement is nonsense for any given x. Thus the last formula is false.

      ———

      I think the solution lies in the meaning of “implies,” as others have said.

  32. Mark Bennet Says:

    The problem here seems related to a comment made by Bill Thurston in his paper “On Proof and Progress in Mathematics” (top of page 5) which says, ‘It’s interesting that although “or”, “and” and “implies” have identical formal usage, we think of “or” and “and” as conjunctions and “implies” as a verb.’

    • gowers Says:

      Thanks for that quote. Actually, in a way I disagree with Thurston that “or”, “and” and “implies” have identical formal usage, though it is hard to explain what I mean by that, when it seems obviously false. Roughly speaking, it’s fine to say “P and Q” or “P or Q” when we have two statements P and Q that contain nothing but free variables. But it’s very rare to say that P implies Q when P and Q do not involve free variables.

      That’s not quite true as stated, so let me illustrate with an example in an effort to say what I mean. Suppose I say “‘n is a prime greater than 2′ implies ‘n is odd’”. Then what I’m really saying is that for every n that holds. So n isn’t (despite appearances) a free variable. It’s slightly complicated because I could be in the middle of the argument and I might have said at some point “Let n be an integer such that P(n)” and I might have deduced that n is a prime greater than 2. So technically n would be a free variable. But it would be the kind of “arbitrary positive integer” rather than some fixed integer.

      I wouldn’t, for instance, find it natural to say “’17 is a prime greater than 2′ implies ’17 is odd’” because that suggests the possibility that 17 is not a prime greater than 2. (I would find it natural to say, “17 is a prime greater than 2. Therefore, 17 is odd.” But that’s different, and is appealing to the more general fact about all n.)

      So I would say that “implies” is a verb because if we say “P(x) implies Q(x)” we are talking about a certain relationship between a general instance of P and a general instance of Q. But if we say “P(x) and Q(x)” we are talking about a specific x and are asserting that both P(x) and Q(x) hold.

    • Mark Bennet Says:

      I realised that I was using “implies” in two different senses when I was an undergraduate. I would write a proof “A implies B implies C” (often a longer chain) meaning “If I know A to be true then I can establish the truth of C by proving that B is true as an intermediate step” or something of the kind. But this is not the same kind of statement as either “(A implies B) implies C” or “A implies (B implies C)” and that always worried me a bit. The kind of implication I use in an informal way in a proof is associative. The same word, two different ideas. I think Thurston’s idea of a “verb” comes from the informal version.

    • markdettinger Says:

      I think that, in a proof, a chain like “A implies B implies C” is actually a shorthand notation of “(A implies B) and (B implies C)”, similar to “a < b < c" in arithmetics. In a strict sense, such a chain is syntactically incorrect, if you think of "<" as a binary operator that takes two numbers and returns a boolean. However, everybody knows you actually mean a<b and b<c.

  33. Florian FIscher Says:

    For any A, B let’s take X={1,2}, A=P(1), B=P(2), Q = A⋀B
    The result
    ∃x∈X (P(x)⇒Q)
    becomes
    (A ⇒ (A⋀B)) ∨ (B ⇒ (A⋀B))
    Using (A⋀B)⇒A and (A⋀B)⇒B, we have.
    (A ⇒ B) ∨ (B ⇒ A)

    This proves what I’ll call “Florian’s all-connectedness theorem”:
    ∀A, B : (A ⇒ B) ∨ (B ⇒ A)

    It proves the extraordinary fact that everything is connected. For any 2 facts A and B, if B doesn’t follow from A, then A follows from B.

  34. George K Says:

    It looks like there is a problem because the nature of what is to be proved appears to have changed after all the transformations. At first, the task is to show Q, given that all the x’s are P. But afterwards, the is to exhibit an x with the bizarre property of its being P implying Q. So it looks like the problem has changed from being about to Q to being about the x’s.

    But consider how you would go about proving that second (purportedly different) claim. If you can’t exhibit the x with that bizarre property (how could you?), the best way to prove it would be to assume it is false and then find a contradiction. Then you are assuming that all the x’s are such that they are P and Q is false. But this is exactly what you would have gotten if you had tried to prove the original statement by contradiction. So the two really are equivalent, since their negations are.

  35. cody Says:

    What Terry’s answer highlights is that some of the steps you are using are not intuitionistically valid in a precise sense: the equivalence does not hold in intuitionist logic. This usually indicates that you are using classical reasoning in a fundamental way, here that either $X$ has diameter less than 2 or not. In general, reformulations that use classical logic are significantly less intuitive (hence the word “intuitionistic”) e.g. the drinker’s paradox. In practice, truly classical reasoning is quite rare.

  36. Carnival of Mathematics #106 – December 2013 | The Aperiodical Says:

    […] an interest in propositional logic should be wary of reading Tim Gowers‘ blog post ‘A small paradox‘, which may well blow their minds, as he somehow manages to construct a demonstrably false […]

  37. Wayne Says:

    Late to the party, I confess. The primary issue that struck me upon first reading the “paradox” was that “x” is somehow “implicitly bound” by the predicate “diam(X)”.

    The original logical argument, as applied to the counter-example, appears legitimate until the violation of the “we haven’t done something foolish” prior to the promotion of the existential quantifier.

  38. John Beattie Says:

    “But that is clearly nonsense. If all we know is that one particular element of X has modulus at most 1, it can’t possibly imply that X has diameter at most 2.”

    I think this does not match the formula. For that sentence I would give this formula:

    forall X \subset R, (\exists x \in X, |x| \le 1) \implies diam(X) \le 2 (*)

    Sorry for the non-latex.

    (*) differs from the last formula in your post because of the bracketing. (*) is certainly false as your counter-example shows.

    It is also interesting to convert the last formula of your post to its contra-positive and then move the constant proposition out of the scope of the \exists x. That does say something interesting:

    \forall X \subset \R, diam(X) > 2 \implies (\exists x \in X, |x| > 1).

  39. ericthoma Says:

    It is a lot easier to see to the heart of the issue here by considering the negation of the last statement. If there does not exist such an $x$, then every $x$ must have a modulus $le 1$ and $diam(X) > 2$, from the definition of $\rightarrow$.

    Then, the second to last statement would also be false, as the left part is true and the right part is false. By establishing the contrapositive, we see that indeed the second to last statement implies the last statement.

  40. The arrow thing | New-cleckit dominie Says:

    […] whether you need the symbol at all until you arrive at formal logic and start romping among its counterintuitive results — until, that is, you have thoughts to express for which the level of precision represented […]

  41. Ustun Yildirim Says:

    There is no mistake here.

    Saying “But that is clearly nonsense. If all we know is that one particular element of X has modulus at most 1, it can’t possibly imply that X has diameter at most 2.” is similar to saying that the following is clearly nonsense. If my cat is black, then 1+1=2. Important thing to note is that “1+1=2″ is true regardless of my cat’s color (even existence of my cat).

    In that sense, if diam(X) \le 2, then there is nothing to worry about. We can choose any x in X either with |x| \le 1 or |x| > 1, the conclusion, and hence, the implication is true. However, if diam(X) > 2, then surely we can find x with |x| > 1 which makes the implication true, since premise is false.

    If there is no element in X, then premises in both statements are vacuously true and thus, the conclusions and the implications have the same values. Since both conclusions are the same, namely diam(X) \le 2, both statements have the same truth value. (Of course, the natural definition would be diam(empty set) = 0 which makes both statements true.)

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

%d bloggers like this: