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.

I am self-studying Daniel Velleman's "How to Prove It."

In the exercises for section 2.1, for question # 1b, I got a different answer than he did (his answer is in the back of the book).

I think my answer is equivalent to his, and I also think I see yet another equivalent answer.

But since I'm learning, I'm not confident enough that my answers really are equivalent, so I hope someone here can help me.

The question is to "analyze the logical form" of the following statement: "Nobody in the calculus class is smarter than everybody in the discrete math class."

Velleman's answer is: $$ \lnot \exists x (C(x) \land \forall y (D(y) \to S(x,y)))) $$

I can see that, but it appears the following are fine too. In fact, it looks to me like you have a choice whether or not to use If-Then at all, and if you want to use it, you have 2 separate places where you could put it.

Is this also correct? $$ \lnot \exists x (C(x) \land (\forall y (D(y) \land S(x,y)))) $$

And is this also correct? $$ \forall x (C(x) \to (\lnot \forall y D(y) \land S(x,y))) $$

EDIT: Here's a third attempt, added later. Is this equivalent? $$ \forall x (C(x) \to \exists y (D(y) \land S(y, x))) $$ where S(y,x) is defined as "y is as smart as or smarter than x"

If those are not correct, please help me understand why not?!?!*

Thanks.

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

As a general rule of thumb, most (negated) universal English language sentences will be translated as a (negated) universal conditional, while (negated) existential sentences will be translated as a (negated) existential conjunction. If you get universal conjunctions or existential conditionals in your translation, then you might want to double check your answer. For instance, the universal fragment of your first answer, "$\forall y (D(y) \wedge S(x,y))$," translates as "Everyone is in the discrete math class and $x$ is smarter than everyone," whereas you wanted to say "$x$ is smarter than anyone who is in the discrete math class," or equivalently, "Everyone who is in the discrete math class is such that $x$ is smarter than them."

In general, if your English sentence has the form "Everything that is $\phi$ is $\psi$," your translation will be along the lines "$\forall x (\phi \rightarrow \psi)$," whereas "$\forall x (\phi \wedge \psi)$" says, "Everything is both $\phi$ and $\psi$," which is a much stronger claim. Similarly, "Some $\phi$ is $\psi$" gets translated as "$\exists x (\phi \wedge \psi)$," whereas "$\exists x (\phi \rightarrow \psi)$" says, "Something is such that if it's $\phi$, then it's $\psi$," or rather "Something is either not $\phi$ or $\psi$," which is a much weaker claim. "No one that is $\phi$ is $\psi$" is typically translated as "$\forall x (\phi \rightarrow \neg\psi)$". But there are equivalent formulations of each of these sentences as well.

Your edited answer is almost correct. However, "$S(y,x)$" is not logically equivalent to "$\neg S(x,y)$", and you want the effect that your $x$ is only not smarter than your $y$. But if you just replace "$S(y,x)$" with "$\neg S(x,y)$", then your new answer will be correct. Also acceptable translations of this sentence include:

  • $\forall x (C(x) \rightarrow \neg \forall y(D(y) \rightarrow S(x,y)))$
  • $\neg \exists x(C(x) \wedge \neg \exists y (D(y) \wedge \neg S(x,y)))$
share|improve this answer
    
Thanks, that is very helpful. Your last example has too many "negations of negations" for me to wrap my mind around. I'll have to spend some time on that tomorrow. But I do like that it presents an alternative with no If-Then, and I see that it had to avoid "forall" in order to do so. So I think this confirms my hypothesis -- I was looking for a guideline to when I'd need an If-Then, and it appears the answer is when I'm inside the scope of a "forall" but I want to make a statement about a subset of the universe. Does that sound right to you? –  Charlie Flowers Apr 26 '13 at 6:24
    
That's the idea. You rarely encounter an existential sentence with a conditional inside, so If-Then sentences are usually found just in the scope of "forall"s. And yes, the idea is that having a conditional inside the scope of the "forall" is a way of making a claim about some subset of the universe. –  Alex Kocurek Apr 26 '13 at 6:35
add comment

The first of your proposed alternatives says that

There is no person $x$ who is both in the calculus class, and for whom it is true that:

     "every person $y$ is both in the discrete math class and is dumber than $x$".

The second one says that

For any person $x$, if they are in the calculus class, then it is not the case that

     "every person $y$ is both in the discrete math class and is dumber than $x$".

As long as there exists at least one person not in the discrete math class, then both of these proposed alternatives will necessarily be true, whereas the original statement can still be false; thus, they are not equivalent.

share|improve this answer
    
OK, thanks. So I think you're telling me that my problem is I'm including in the "conversation" people who are not even in the Discrete Math class, where I was supposed to exclude them. Is that right? And if so, can you see a way to exclude them without using an If-Then? –  Charlie Flowers Apr 26 '13 at 5:01
1  
I think I see a rule. If I'm inside of a "for all" statement, but I actually want to make a statement about a subset of the universe, I'm going to have to use an If-Then. Is that right? –  Charlie Flowers Apr 26 '13 at 5:16
1  
@CharlieFlowers: I think that's a good way of phrasing it. –  Zev Chonoles Apr 26 '13 at 5:34
add comment

I'm familiar with this book. The problems in this section are getting you ready for the manipulations to come in the subsequent sections. If you haven't gotten that far, it's difficult to give an explanation using the very few tools developed up to this point in the text. The good news is that even if you don't quite get this problem, as you continue in the book you'll gain insight and eventually it will make sense.

Unfortunately neither of your alternate solutions is correct. You really need an implication, not $\wedge$. It turns out that $x\rightarrow y$ is equivalent to $\neg x \vee y$, while you have $x\wedge y$, which is quite different.

As the other solution points out, in certain situations your solution differs from the original.

share|improve this answer
    
thanks for your response. I think I have figured out my mistake, and I'd word it like this: "If you're inside a 'forall', and you want to make a statement about a subset of the universe, the only way to do so is with an If-Then (aka, 'implication')." Do you agree? –  Charlie Flowers Apr 26 '13 at 5:19
    
Certainly implication is one way to refer to a subset of the universe. Another way is with or, due to the equivalence I mentioned above. –  vadim123 Apr 26 '13 at 13:05
    
Excellent. Thank you. I was aware of the equivalence you mentioned, and in my mind using it is the same as using an implication. I was wondering if there were other equivalents that don't rely on implication. At this point, I think the answer is yes, but only if you re-word the statement to use existential qualifiers instead of universal qualifiers. Thanks again. –  Charlie Flowers Apr 26 '13 at 16:06
    
$\neg x \vee y \vee z$ is yet another way, that is neither of the above. There are other examples too. Sorry, your rule of thumb doesn't quite work. –  vadim123 Apr 26 '13 at 16:10
    
OK, so there are equivalences I don't know about yet that the book will cover soon. That's good. Thanks. –  Charlie Flowers Apr 27 '13 at 4:22
show 1 more comment

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.