(for all x, Px) implies (there exists some x, Px)?

by honestrosewater
Tags: exists, implies
 PF Gold P: 2,330 I'm browsing around waiting for my books to arrive, and I came across this (PDF) site that says $$\forall x P(x) \Rightarrow \exists x P(x)$$. They don't define $$\Rightarrow$$, but I imagine it bears the same relation to $$\rightarrow$$ as $$\Leftrightarrow$$ bears to $$\leftrightarrow$$. Anyway, how would you prove $$\forall x P(x) \Rightarrow \exists x P(x)$$? $$[\forall x P(x) \rightarrow \exists x P(x)] \Leftrightarrow [(\neg \forall x P(x))\ \vee \ \exists x P(x)] \Leftrightarrow [\exists x \neg P(x)\ \vee\ \exists x P(x)]$$ right? I don't know any more rules to apply to evaluate that nor how to construct a truth table for propositions with quantifiers. I need to show that $$\exists x \neg P(x)$$ and $$\exists x P(x)$$ cannot both be false (at once), but I'm stumped. Does it have something to do with how they define the quantifiers? They define $$\forall x P(x)$$ as $$[P(x_1) \wedge P(x_2) \wedge ... \wedge P(x_n)]\ \mbox{where} \ [x_1, x_2, ..., x_n]$$ are (exhaustively) the members of x. $$\exists x P(x)$$ is defined the in same way but as a disjunction. I suspect I'll be kicking myself about this.
 Emeritus Sci Advisor PF Gold P: 16,091 I'm not sure of the technicalities involved... this implication is true iff $\exists x$ is.
 PF Gold P: 2,330 (for all x, Px) implies (there exists some x, Px)? So if I'm interpreting $$\Rightarrow$$ correctly, they're wrong. I'm interpreting $$\forall x P(x) \Rightarrow \exists x P(x)$$ to mean that $$\forall x P(x) \rightarrow \exists x P(x)$$ (material implication) is a tautology. I'm interpreting it this way because that's what logical equivalence ($\Leftrightarrow$) means for bi-implication or the biconditional ($\leftrightarrow$). Edit: If you assume $$[\mbox{(x is empty)} \rightarrow \forall x (Px)]$$, what happens to universal instantiation? (UI: for all x, (Px), therefore, (Pc), where c is some arbitrary element of the universe (which is assumed to be empty).)
 P: 68 Well Grasshopper, $$\forall x P(x) \Leftrightarrow \neg \exists x \neg P(x)$$ Which is why you can't prove it. To prove it, something must first exist in the universe of discourse, call it "a" $$a\ exists \bigwedge \forall x P(x) \Rightarrow \exists x ¬P(x)$$ is provable. Your proposition is invalid for all models based on the empty set. Or, in other words, your proposition is valid for all universes of discourse except the one universe in which nothing exists. Logic is spooky....