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.

Why is this true?

$(\exists x)(P(x) \Rightarrow (\forall y) P(y))$

share|improve this question
10  
Either $(\forall y) P(y)$ or not. If the former, then the statement is true, if the latter then for some $x$ we have $\lnot P(x)$, and hence the statement is true. –  copper.hat Jun 5 '13 at 20:54
2  
Actually, I'm not sure this is a true statement. If your domain is empty, then $\forall y: P(y)$ is true vacuously, but $\exists x: P(x)\implies \forall y: P(y)$ is not true. –  Thomas Andrews Jun 5 '13 at 21:07
1  
@NickKidman Yes, since $S\lor \neg S$ is provable. –  Git Gud Jun 5 '13 at 21:14
1  
Smullyan calls this the "drinker's paradox": there exists a person $p$ such that if $p$ drinks, then everyone drinks. –  MJD Jun 5 '13 at 21:14
1  
If 12 is prime, then every natural number is prime. –  GEdgar Jun 17 '13 at 12:59

9 Answers 9

up vote 19 down vote accepted

Since this may be homework, I do not want to provide the full formal proof, but I will share the informal justification. Classical first-order logic typically makes the assumption of existential import (i.e., that the domain of discourse is non-empty). In classical logic, the principle of excluded middle holds, i.e., that for any $\phi$, either $\phi$ or $\lnot\phi$ holds. Since I first encountered this kind of sentence where $P(x)$ was interpreted as "$x$ is a bird," I will use that in the following argument. Finally, recall that a material conditional $\phi \to \psi$ is true if and only if either $\phi$ is false or $\psi$ is true.

By excluded middle, it is either true that everything is a bird, or that not everything is a bird. Let us consider these cases:

  • If everything is a bird, then pick an arbitrary individual $x$, and note that the conditional “if $x$ is a bird, then everything is a bird,” is true, since the consequent is true. Therefore, if everything is a bird, then there is something such that if it is a bird, then everything is a bird.
  • If it is not the case that everything is a bird, then there must be some $x$ which is not a bird. Then consider the conditional “if $x$ is a bird, then everything is a bird.” It is true because its antecedent, “$x$ is a bird,” is false. Therefore, if it is not the case that everything is a bird, then there is something (a non-bird, in fact) such that if it is a bird, then everything is a bird.

Since it holds in each of the exhaustive cases that there is something such that if it is a bird, then everything is a bird, we conclude that there is, in fact, something such that if it is a bird, then everything is a bird.

Alternatives

Since questions about the domain came up in the comments, it seems worthwhile to consider the three preconditions to this argument: existential import (the domain is non-empty); excluded middle ($\phi \lor \lnot\phi$); and the material conditional ($(\phi \to \psi) \equiv (\lnot\phi \lor \psi)$). Each of these can be changed in a way that can affect the argument. This might not be the place to examine how each of these affects the argument, but we can at least give pointers to resources about the alternatives.

  • Existential import asserts that the universe of discourse is non-empty. Free logics relax this constraint. If the universe of discourse were empty, it would seem that $\exists x.(P(x) \to \forall y.P(y))$ should be vacuously false.
  • Intuitionistic logics do not presume the excluded middle, in general. The argument above started with a claim of the form “either $\phi$ or $\lnot\phi$.”
  • There are plenty of philosophical difficulties with the material conditional, especially as used to represent “if … then …” sentences in natural language. If we took the conditional to be a counterfactual, for instance, and so were considering the sentence “there is something such that if it were a bird (even if it is not actually a bird), then everything would be a bird,” it seems like it should no longer be provable.
share|improve this answer
    
What if your domain is empty? That is, if $\exists x: Q$ is false for all statements $Q$? –  Thomas Andrews Jun 5 '13 at 21:09
    
If the domain is empty, then we need a new notion of the interpretation of a term, because the the interpretation function has no domain elements to map variables to. Intuitively, though, we should expect any sentence $\exists x. \dots$ to be false if the domain is empty. Free logic considers this possibility. –  Joshua Taylor Jun 5 '13 at 21:13
1  
@ThomasAndrews I just meant that the semantics of classical first order logic are typically defined in terms of a semantic interpretation function $\cal I$ and a variable mapping $\nu$ (which maps each variable to an element of the domain) that says that a sentence $\forall x. \phi(x)$ is true if and only if the interpretation function and every variable mapping $\nu'$ (which is the same as $\nu$ for each variable excepting that it may differ on $x$) make $\phi(x)$ true. –  Joshua Taylor Jun 5 '13 at 21:27
1  
@ThomasAndrews Regarding $\exists x.(P(x) \lor \lnot P(x))$: this sentence is a theorem of classical first-order logic. It is easy to prove by contradiction. Suppose $\lnot\exists x.(P(x) \lor \lnot P(x))$. Then $\forall x.\lnot(P(x) \lor \lnot P(x)$, and this is equivalent to $\forall x.(\lnot P(x) \land \lnot\lnot P(x))$, which is equivalent to $\forall x.(\lnot P(x) \land P(x))$, which is false if the universe of discourse is non-empty, which existential import ensures. Therefore, $\exists x.(P(x) \lor \lnot P(x))$. –  Joshua Taylor Jun 5 '13 at 21:37
1  
@ThomasAndrews Right, if you don't have existential import, then the sentence isn't necessarily true. Classical first-order logic doesn't require the assumption of “some axiom that implies non-empty discourse,” though; it's built into the inference rules. E.g., $\forall x.x=x$ should be true whether the universe is empty or not. But by universal elimination we may infer $a=a$, and from that, by existential introduction, $\exists x.x=x$, which implies that the domain is not empty. Free logic is a fascinating topic, and attempts to address these types of issues. –  Joshua Taylor Jun 5 '13 at 23:56

Hint: The only way for $A\implies B$ to be false is for $A$ to be true and $B$ to be false.

I don't think this is actually true unless you know your domain isn't empty. If your domain is empty, then $\forall y: P(y)$ is true "vacuously," but $\exists x: Q$ is not true for any $Q$.

share|improve this answer
    
I'm probably looking at this the wrong way. But suppose P(x) means x is a person. Doesn't it say "There exists something that is a person, so everything is a person."? –  Mats Jun 5 '13 at 20:54
1  
Instead of $A \Rightarrow B$, think of $\lnot A \lor B$. –  copper.hat Jun 5 '13 at 20:56
    
That's the problem with implication in logic. $A\implies B$ is not a statement about "for all," it is a statement about specific instances. That can be a little confusing. If it is not true that all things are people, say, Z is my dog. Then since $P(Z)$ is false, we know that $P(Z)\implies Q$ for any statement $Q$. So $\exists x: P(x)\implies Q$. –  Thomas Andrews Jun 5 '13 at 20:57
    
So in my case, there exists something that isn't a person, hence the whole statement is true? –  Mats Jun 5 '13 at 21:00
3  
@Matts Not quite. $\forall x.(P(x) \to \forall y.P(y))$ says that "there is an $x$ such that if $x$ is a person, then …". It does not make the assertion that "there is an $x$ such that $x$ is a person." –  Joshua Taylor Jun 5 '13 at 21:03

The examples with birds or drinkers were designed to make this simple logical truth sound paradoxical. Perhaps an example from ordinary mathematics will dispel the air of paradox. Consider a nonempty set $X$ and a function $f:X\rightarrow\{0,1\}$. Does the following proposition seem strange and unintuitive?

Theorem. There is an element $m\in X$ such that, if $f(m)=1$, then $f(x)=1$ for all $x\in X$.

Proof. The function $f$ has an absolute minimum. (The domain is nonempty and the range is a finite set of numbers.) Let $m$ be a point in $X$ where $f$ attains its minimum value. Clearly, if $f(m)=1$, then $f(x)=1$ for all $x$.

Really, all that logical formula is saying is that the truth value ($1$ for true, $0$ for false) of the "propositional function" $P(x)$ attains its minimum.

share|improve this answer
2  
The resolution of this paradox bothered me until I read this. It seemed irrelevant to declare $x$ to be "either anything, or a counterexample if there is one", since neither one is really a uniform description of a deciding element. But phrasing it like this makes it feel more acceptable since regardless of whether $f \cong 1$, the description of a deciding element is the same. –  Ryan Reich Jun 5 '13 at 23:39
    
In mathematics, there's no such thing as an uniform description. –  justt Jun 17 '13 at 14:35

In mathematics, if not in philosophy, the domain of quantification is usually made explicit in statements. If we let the domain be some set $U$, your statement becomes

$$\exists x\in U (P(x) \Rightarrow \forall y\in U (P(y))$$

or equivalently

$$\exists x(x\in U \wedge (P(x) \Rightarrow \forall y(y\in U\Rightarrow P(y))))$$ Then you can formally prove this statement is true iff $U$ is non-empty as sketched here:

For non-empty $U$, consider two cases:

$$\forall y\in U (P(y))\lor \neg\forall y\in U (P(y))$$

In each case, obtain

$$\exists x\in U (P(x) \Rightarrow \forall y\in U (P(y))$$ For empty U, assume to the contrary that

$$\exists x\in U (P(x) \Rightarrow \forall y\in U (P(y))$$

and obtain a contradiction.

Full text of formal proof at http://dcproof.com/Mats.htm

share|improve this answer

In classical logic the following equivalence is logically valid: $$ \exists x (\varphi\Rightarrow\psi)\Longleftrightarrow(\forall x\varphi\Rightarrow\psi) $$ providing that $x$ is a variable not free in $\psi$. So the formula in question is logically equivalent to $\forall xP(x)\Rightarrow\forall yP(y)$.

Looking at the poblem from a slightly different perspective. Either (i) all objects in the domain of discourse have property $P$, i.e. $\forall y P(y)$ is true or (ii) there is $a$ in the domain for which $P$ fails, i.e. $\neg P(a)$ is true. In (i) $P(x)\Rightarrow\forall y P(y)$ must be true, so $\exists x(P(x)\Rightarrow\forall y P(y))$ is true. In (ii) $P(a)\Rightarrow\forall y P(y)$ must be true, therefore the sentence in question must be true as well.

share|improve this answer

The location of the parentheses is crucial here. Note that $(\exists x)(P(x) \Rightarrow (\forall y) P(y))$ is very different from $(\exists x)(P(x)) \Rightarrow (\forall y) P(y))$. To see why the former statement is true, consider its negation which is

$$\forall x (P(x) \wedge \neg \forall P(x)) \equiv \forall x(P(x) \wedge \exists x \neg P(x))$$

which is clearly false if your domain is nonempty. In classical logic, we restrict to nonempty domains, so your original statement will always be true.

share|improve this answer

Translate it to english:

In any universe of things, there can always be found an instance which, if it has some property, then all other things have that property.

For any given property, you can find an instance in a set of things to make it true. (As long as that set is not the empty set, by the way; existential assertions are false for empty sets.)

  • If none of the things have the property, then you can choose any one of them. Call that chosen instance $a$. $P(a) \Rightarrow (\forall y) P(y)$ is vacuously true, because $P \Rightarrow Q$ is true whenever $P$ is false.

  • If all of the things have the property, then you can also choose any of them to be the instance $a$. $P(a) \Rightarrow (\forall y) P(y)$ is then true because $P(a)$ is true, and $(\forall y) P(y)$ is true.

  • If some things have the property but not others, then you just choose one which does not have the property to be the instance $a$. Then $P(a) \Rightarrow (\forall y) P(y)$ is, again, vacuously true on account of $P(a)$ being false.

But let's look at it by taking the contradiction and seeing where it leads: $\neg(\exists x)(P(x) \Rightarrow (\forall y) P(y))$

In any universe of things, there cannot be found an instance such that if it has some property, then all other things have that property.

we can move the negative inside: $(\forall x)\neg(P(x) \Rightarrow (\forall y) P(y))$

In any universe of things, for every one of its elements, it is false that if a given property holds true of the element, then it holds for all other elements.

Then we can integrate the $\neg$ into the formula by way of $\neg (Q \rightarrow P) = Q \land\neg P$ to arrive at: $(\forall x)(P(x) \land\neg (\forall y) P(y))$

But this asserts $P(x)$ for all $x$; i.e. that if we think of any property $P$, all things have that property! This is clearly absurd for any nonempty set; we can come up with all kinds of properties $P$ which holds only for some things in a set, or none at all.

share|improve this answer

Here's a different approach: this can be fairly-straightforwardly proved from simple boolean algebra, starting from a tautology. $$ ((\forall y)P(y)) \lor (\lnot (\forall x) P(x)) \\ ((\forall y)P(y)) \lor ((\exists x)\lnot P(x))\\ (\text{anything} \Rightarrow (\forall y)P(y)) \lor ((\exists x)(P(x) \Rightarrow \text{anything})) \\ ((\forall x)(P(x) \Rightarrow (\forall y)P(y))) \lor ((\exists x)(P(x) \Rightarrow (\forall y)P(y))) \\ ((\exists x)(P(x) \Rightarrow (\forall y)P(y))) \lor ((\exists x)(P(x) \Rightarrow (\forall y)P(y))) \\ (\exists x)(P(x) \Rightarrow (\forall y)P(y)) $$

share|improve this answer

To add a proof in Fitch style, natural deduction:

2  | |__________ ~Ex(Px -> VyPy)   New Subproof for ~ Introduction
3  | | |________ Pa                New Subproof for -> Introduction
4  | | | |_____b                   variable for Universal Introduction
5  | | | | |____ ~Pb               New Subproof for ~ Introduction
6  | | | | | |__ Pb                New Subproof for -> Introduction
7  | | | | | |   _|_               5,6 _|_ Introduction
8  | | | | | |   VyPy              7 _|_ Elimination
.  | | | | | <-------------------- end subpproof
9  | | | | |     Pb -> VyPy        6-8 -> Introduction
10 | | | | |     Ex(Px -> VyPy)    9 Existentional Introduction
11 | | | | |     _|_               2,10 _|_ Introduction
.. | | | | <---------------------- end subpproof
12 | | | |       ~~Pb              5-11 ~ Introduction
13 | | | |       Pb                12 ~~ Elimination
.. | | | <------------------------ end subpproof
14 | | |         VyPy              4-13 Universal Introduction
.. | | <-------------------------- end subpproof
15 | |           Pa -> VyPy        3-14 -> Introduction
16 | |           Ex(Px -> VyPy)    15 Existentional Introduction
17 | |          _|_                2,16 _|_ Introduction
.. | <---------------------------- end subpproof
18 |            ~~Ex(Px -> VyPy)   2-17 ~ Introduction
19 |            Ex(Px -> VyPy)     18 ~~ Elimination

This is the shortest I managed, I don't think a shorter proof using the standard introduction and elimination rules exist

For explanation I compare this "paradox" with:

If the last person has left the room, all people have left the room.

Therefore

There is a person if he has left the room, all people have left the room.

The first statement is a truism , so how can the last statement not be one?

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.