- #1
honestrosewater
Gold Member
- 2,142
- 6
I'm browsing around waiting for my books to arrive, and I came across http://people.cornell.edu/pages/ps92/414/LogicalOpLogicQuantifiers.pdf (PDF) site that says [tex]\forall x P(x) \Rightarrow \exists x P(x)[/tex]. They don't define [tex]\Rightarrow[/tex], but I imagine it bears the same relation to [tex]\rightarrow[/tex] as [tex]\Leftrightarrow[/tex] bears to [tex]\leftrightarrow[/tex]. Anyway, how would you prove [tex]\forall x P(x) \Rightarrow \exists x P(x)[/tex]?
[tex][\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)][/tex] 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 [tex]\exists x \neg P(x)[/tex] and [tex]\exists x P(x)[/tex] cannot both be false (at once), but I'm stumped.
Does it have something to do with how they define the quantifiers? They define [tex]\forall x P(x)[/tex] as [tex][P(x_1) \wedge P(x_2) \wedge ... \wedge P(x_n)]\ \mbox{where} \ [x_1, x_2, ..., x_n][/tex] are (exhaustively) the members of x. [tex]\exists x P(x)[/tex] is defined the in same way but as a disjunction.
I suspect I'll be kicking myself about this.
[tex][\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)][/tex] 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 [tex]\exists x \neg P(x)[/tex] and [tex]\exists x P(x)[/tex] cannot both be false (at once), but I'm stumped.
Does it have something to do with how they define the quantifiers? They define [tex]\forall x P(x)[/tex] as [tex][P(x_1) \wedge P(x_2) \wedge ... \wedge P(x_n)]\ \mbox{where} \ [x_1, x_2, ..., x_n][/tex] are (exhaustively) the members of x. [tex]\exists x P(x)[/tex] is defined the in same way but as a disjunction.
I suspect I'll be kicking myself about this.
Last edited by a moderator: