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.

There seems to be two forms of the conditional statement in predicate logic.

$$\forall x\,(P(x)\Rightarrow Q(x))$$

versus

$$(\forall x\in S)\Rightarrow Q(x)$$

$$S=\{x:P(x)\}$$

Are these equivalent? I'm a bit confused in the second form because It looks like $Q(x)$ is an open sentence however I know that this is just the universal statement:

$$(\forall x\in S)Q(x)$$

albeit written more explicitly. Are these two statements the same? Is the scope different? If the scope is restricted, or if they are not the same, what is their difference? To me the first says "for every $x$, if $x$ is $P(x)$ then $x$ is a $Q(x)$" and the second says "for every $x$ that is a $P(x)$, aforementioned $x$ is a $Q(x)$". Is more presupposed in this case?

share|improve this question
1  
Yes, they're equivalent. Remember that $\in$ is simply a binary predicate, so $(\forall{x \in Y})\;\varphi(x)$ merely abbreviates $\forall{x} (x \in Y \rightarrow \varphi(x))$. Similarly we abbreviate $\exists{y} (y \in Z \rightarrow \psi(y))$ as $(\exists{y \in Z})\;\psi(y)$. In your case, $P(x) \Leftrightarrow x \in S$, so $\forall{x} (x \in S \rightarrow Q(x)) \Leftrightarrow \forall{x} (P(x) \rightarrow Q(x))$. –  Benedict Eastaugh Jul 31 '12 at 18:34
    
@BenedictEastaugh Shouldn't the '$\rightarrow$' following the '$\exists$' quantifier be a '$\wedge$'? –  Dan Christensen Aug 1 '12 at 4:52
    
Yeah, that's a typo, thanks for pointing it out. Unfortunately I can't edit my comment now. –  Benedict Eastaugh Aug 1 '12 at 11:48
    
I've removed analysis tag. I don't really see relevance of this tag for this question. –  Martin Sleziak Aug 2 '12 at 8:57

2 Answers 2

up vote 2 down vote accepted

Your second formula "$(\forall x \in S)\Rightarrow Q(x)$" is not well-formed at all. What comes to the left of $\Rightarrow$ must be a complete formula, and "$\forall x\in S$" is not a complete formula -- it's a dangling quantifier with no body formula.

It is true, however, that $(\forall x \in S) Q(x)$ (without the spurious $\Rightarrow$) is the same as $(\forall x)(x\in S \Rightarrow Q(x))$ -- usually the former is considered a mere abbreviation of the latter.

share|improve this answer
    
thats what I had thought, but the form I had posted was from a book I am studying, so idk If that means there was a mistake made or simply a difference in conventions. thank you for you answer. –  skyfire Jul 31 '12 at 18:41
    
To be fair, this technically doesn't answer the question, (you don't explain the connection between the two forms). Sry to remove the accept, I jumped the gun. All it really needs is a summary of what benedict has written however. –  skyfire Jul 31 '12 at 18:55
    
The "connection" between the two forms is that the first one has meaning and the second doesn't. The third one is usually considered an abbreviation of the first, as I explain in my second paragraph. –  Henning Makholm Jul 31 '12 at 19:41
    
fair enough, I just thought I would leave it open a little while longer in case others were interested in adding insight. but the connection I was speaking of was in reference to $$\forall x\,(P(x)\Rightarrow Q(x))$$. in your answer the connection you mention is between $(\forall x \in S) Q(x)$ and $(\forall x)(x\in S \Rightarrow Q(x))$. which doesn't make explicit the connection between the element test $x\in S$ and $P(x)$. Thats all. –  skyfire Jul 31 '12 at 21:08

You can easily prove that $$S=\{x:P(x)\}\rightarrow (\forall x(P(x)\rightarrow Q(x))\leftrightarrow (\forall x\in S)Q(x))$$ where $$(S=\{x:P(x)\})\equiv \forall x (x\in S \leftrightarrow P(x))$$and $$(\forall x\in S)Q(x)\equiv \forall x(x\in S \rightarrow Q(x))$$ See my formal proof at http://www.dcproof.com/skyfire.htm

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.