Register to reply

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

by honestrosewater
Tags: exists, implies
Share this thread:
honestrosewater
#1
Feb12-05, 05:38 PM
PF Gold
honestrosewater's Avatar
P: 2,330
I'm browsing around waiting for my books to arrive, and I came across this (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.
Phys.Org News Partner Science news on Phys.org
World's largest solar boat on Greek prehistoric mission
Google searches hold key to future market crashes
Mineral magic? Common mineral capable of making and breaking bonds
Hurkyl
#2
Feb12-05, 06:35 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,098
I'm not sure of the technicalities involved... this implication is true iff [itex]\exists x[/itex] is.
mathwonk
#3
Feb12-05, 06:58 PM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,453
the statement (for all x, P(x)) does not imply the statement (for some x, P(x)).


i.e. there might not be any x's. if there do exist some x's, then the implication is true.

thius is hurkyl's point.

honestrosewater
#4
Feb12-05, 07:15 PM
PF Gold
honestrosewater's Avatar
P: 2,330
(for all x, Px) implies (there exists some x, Px)?

So if I'm interpreting [tex]\Rightarrow[/tex] correctly, they're wrong. I'm interpreting [tex]\forall x P(x) \Rightarrow \exists x P(x)[/tex] to mean that [tex]\forall x P(x) \rightarrow \exists x P(x)[/tex] (material implication) is a tautology. I'm interpreting it this way because that's what logical equivalence ([itex]\Leftrightarrow[/itex]) means for bi-implication or the biconditional ([itex]\leftrightarrow[/itex]).

Edit: If you assume [tex][\mbox{(x is empty)} \rightarrow \forall x (Px)][/tex], 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).)
honestrosewater
#5
Feb14-05, 02:08 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Well, that the same language can speak meaningfully about both empty and non-empty universes is very interesting to me (What does that say about the language?). But I guess I should take this to the philosophy>logic forum.
xxxx0xxxx
#6
May11-11, 12:35 PM
P: 68
Well Grasshopper,


[tex] \forall x P(x) \Leftrightarrow \neg \exists x \neg P(x) [/tex]

Which is why you can't prove it.

To prove it, something must first exist in the universe of discourse, call it "a"

[tex] a\ exists \bigwedge \forall x P(x) \Rightarrow \exists x P(x) [/tex]

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....
xxxx0xxxx
#7
May11-11, 01:47 PM
P: 68
x is empty meaning x is the empty set, a specifically defined set that exists axiomatically in ZF.

This is not the same as the statement "x does not exist", i.e. that something, call it "x", specifically does not exist in the universe of discourse.

For example "the empty set does not exist" is a contradiction in ZF, since by axiom, it does exist in the universe of discourse for ZF.

Prove the empty set exists in ZF:

1) suppose the empty set doesn't exist (Prove a contradiction)
2) But the empty set does exist (axiom of ZF)
3) the empty set exists and the empty set doesn't exist (contradiction, Q.E.D.)


Register to reply

Related Discussions
Prove a^2 + b^2 = 3(s^2 + t^2) implies both a and b must are divisible by 3 Linear & Abstract Algebra 13
F'(z)=0 implies f is not 1-1 near z Calculus 4
Show that ((p implies q) and (q implies r)) implies (p implies r) is a tautology Calculus & Beyond Homework 2
How can I show that G=8pT implies the equivalence principle ? Special & General Relativity 18
New Paper: GR implies no dark matter Special & General Relativity 5