Why is this true? $(\exists x)(P(x) \Rightarrow (\forall y) P(y))$

Why is this true?

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


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.

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


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.


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.


Here's a different approach: this can be fairly-straightforwardly proved from simple boolean algebra, starting from a tautology.$\quad$ $$ ((\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)) $$