Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been trying to solve the following exercise of Velleman's "How To Prove It":

Prove $\exists x(P(x)\to \forall yP(y))$.

Could anybody give a hint on this? I guessed some transformations could be made to the problem, but I'm not quite sure...

Thanks!

share|improve this question
1  
Bear in mind that a false statement implies anything. –  hardmath Sep 8 '12 at 1:56
3  
This is called the Drinker paradox. –  MJD Sep 8 '12 at 2:03
    
@MJD: That's interesting; the article suggests that the proposition is not intuitionistically valid, which answers a question I was about to ask. –  Trevor Wilson Sep 8 '12 at 2:07

2 Answers 2

up vote 4 down vote accepted

Alternatively (to add to @William's answer) proceed by Reductio: so suppose $$\neg\exists x(Px \to \forall yPy)$$which is equivalent to $$\forall x\neg(Px \to \forall yPy).$$ The only thing we can do is pick some object from the domain [here we do have to assume a non-empty domain] and instantiate to get $$\neg(Pa \to \forall yPy)$$A negated conditional is only true if the antecedent is true and consequent is false, hence $$Pa$$ $$\neg\forall yPy$$ From the latter we have $$\exists y\neg Py$$ An existential is only true if witnessed by some object, name it $b$, so $$\neg Pb$$ What else do we know about $b$? We have to appeal to the universal quantified claim (our only option here) so $$\neg(Pb \to \forall yPy)$$ Another negated conditional, so for it to be true its antecedent has to be true, i.e. $$Pb$$ And we have hit a contradiction. Our original supposition is ruled out, and we are done.

Of course, what we've got here is a (commented version of a) proof in a standard tree system of logic. And what it illustrates is how, in simple cases like this, the production of a proof in such a system is often more or less automatic (you don't need to think strategically, but just grind out doing the only sensible thing at each stage). It isn't for nothing that books such Richard Jeffrey's and Wifrid Hodges texts on logic-by-trees (and many later ones) have proved so popular for intro courses, as beginners find tree systems particularly easy to use.

share|improve this answer
    
The transformations I mentioned (the ones I wasn't sure could be made) were precisely universal and existential instantiation. As you've stated, we have to assume that the universe of discourse is not empty in order to use them. Maybe because the problem doesn't state anything about the universe of discourse I considered it should not be possible to assume something about an originally "undefined" object. Now the question seems clear to me, though. Thanks! –  Fred Sep 8 '12 at 18:30

Depending on what are exactly the logical axioms of your first order logic, the proof would be a bit different.


Intuitively, consider whether $(\forall y)P(y)$ holds. If it does then any $x$ would make $P(x) \Rightarrow (\forall y)P(y)$ hold. Hence $(\exists x)(P(x) \Rightarrow (\forall y)P(y))$.

The other case is that $\neg(\forall y)P(y)$. Let $x$ be such that $\neg P(x)$. Then for this particular $x$, $P(x) \Rightarrow (\forall y)P(y)$ since the conditional is not satisfied. Thus $(\exists x)(P(x) \Rightarrow (\forall y)P(y))$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.