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 and you have a hypothesis to work with. In other words, you are trying to prove the statement

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

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

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

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

Every single step I took there was a logical equivalence, so the conclusion is that if you want to show that implies , your task is the same as that of finding a single such that .

Now let me give a counterexample to that useful logical principle. Let be a set of real numbers. Define the *diameter* of to be . I’ll write it .

Consider the following implication.

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

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

But that is clearly nonsense. If all we know is that one particular element of has modulus at most 1, it can’t possibly imply that 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”.

December 9, 2013 at 5:43 pm |

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.

December 9, 2013 at 7:18 pm

Yes, that’s the first mistake I noticed and unfortunately it caused me to stop looking for others until I read this.

December 9, 2013 at 5:55 pm |

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.)

December 9, 2013 at 6:04 pm |

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

December 9, 2013 at 6:14 pm |

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?

December 9, 2013 at 6:41 pm |

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 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…

December 9, 2013 at 6:46 pm |

There is no mathematical error here. 😉

December 9, 2013 at 8:23 pm |

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)

December 9, 2013 at 9:50 pm |

Let x be the element with the greatest modulus.

December 9, 2013 at 10:51 pm

What if there isn’t such an element?

December 10, 2013 at 11:16 am

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.

December 10, 2013 at 11:55 am

…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).

December 11, 2013 at 8:36 am

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.

December 9, 2013 at 10:52 pm |

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.

December 9, 2013 at 11:27 pm |

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

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

December 9, 2013 at 11:31 pm

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

December 9, 2013 at 11:59 pm |

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?

December 10, 2013 at 1:09 am |

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

December 10, 2013 at 1:51 am |

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.

December 10, 2013 at 8:49 am |

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.

December 10, 2013 at 9:01 am |

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).

December 10, 2013 at 5:12 pm |

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 varies (or in a subtly different universe in which 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 does not commute with the existential quantifier . In particular, the sentence

is true, but the sentence

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

December 10, 2013 at 5:14 pm

(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.)

December 10, 2013 at 8:17 pm |

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’.

December 11, 2013 at 2:00 pm

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.

December 11, 2013 at 1:16 am |

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 from .

So, for instance, in order to prove:

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.

December 11, 2013 at 1:23 am |

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.

December 11, 2013 at 4:09 am |

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.

December 11, 2013 at 4:16 am

The translation should be: “There are some elements in X such that if these elements have modulus at most 1, then the diameter of X is at most 2.”

December 11, 2013 at 3:37 pm |

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.

December 11, 2013 at 6:15 pm |

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!

December 19, 2013 at 11:56 am

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.

December 13, 2013 at 6:52 pm |

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.

December 15, 2013 at 5:26 pm |

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

December 16, 2013 at 1:56 pm |

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.

December 18, 2013 at 11:31 am |

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

to

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.

December 18, 2013 at 11:35 am

Whoops, I missed a bracket in the second bit of LaTeX error (Tim, please feel free to correct it and delate this comment). I meant to say:

to

December 19, 2013 at 11:00 am |

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

December 19, 2013 at 1:20 pm |

The rule of quantifiers movement which concerns us is:

with the restriction that the variable does not appear in .

The paradox is created because there is no rule

regardless if has as free variable .

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

and are not equivalent .

In the language of predicate logic the proposition

is written as and so if we apply the rule of movement of quantifiers we have

While the proposition is written as

, hence

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

is equivalent to the proposition

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

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

if has no free occurrences of then we have the equivalent proposition

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 for the logical operator implies and the symbol for tautologically equivalent propositions .

December 19, 2013 at 1:40 pm |

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.

December 19, 2013 at 4:37 pm |

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) )

December 19, 2013 at 10:12 pm |

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

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:

And yes, that would indeed be nonsense.

January 6, 2014 at 2:44 am

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.

December 21, 2013 at 10:52 am |

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.’

December 22, 2013 at 5:15 pm

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 nthat 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.

December 23, 2013 at 6:19 pm

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.

December 23, 2013 at 10:55 pm

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.

December 21, 2013 at 1:09 pm |

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.

December 30, 2013 at 9:23 pm |

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.

January 5, 2014 at 4:06 am |

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.

January 9, 2014 at 9:02 am |

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

January 11, 2014 at 11:20 pm |

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.

January 16, 2014 at 1:28 pm |

“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).

February 2, 2014 at 2:36 am |

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.

February 4, 2014 at 9:13 pm |

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

February 24, 2014 at 5:50 am |

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.)

May 3, 2014 at 1:52 pm |

It seeems to me that the problem is that the counterexample is not really a counterexample. In the proof, you assume that Q does not depend on x which allows you to make a crucial step (before which everything works fine even in your counterexample). But that does not hold for the statement about the diameter of X. The statement is correct, however it probably is not very interesting exactly because it only works for Qs that have got nothing to do with Ps.

Or am I missing something?

April 1, 2017 at 12:10 pm |

There is no problem with this proof. The proof that you wrote is in classical logic. In intuitionistic logic, we can not prove the same theorem. There exists a Kripke model K such that

1) K forces (for all x A(x)) –> Q

2) but K does not force exists x (A(x) –> Q)

The intuitive reason behind it is that

for all x A(x) or exists x not A(x)

is not constructive or in computability sense, it is not decidable.

If we think the implication in A –> B as a universal machine that construct a proof of B by getting a proof of A as input (BHK interpretation),

A –> B

and

not A or B

are not alike.

So, by knowing the set X, we can not construct or compute a real number ‘b’ in X such that

|b| diam(X)<= 2