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.

"Some computer science majors take discrete math"

S is the domain of all college students C(x) means "x is a computer science major" D(x) means "x takes discrete math"

Can someone please explain why the following statement is wrong according to the TA?

There exists x in S such that C(x) implies D(x)

???

I don't understand!

EDIT: I can see how it could be: There exists x in S such that C(x) AND D(x), but I don't see why an implication is wrong for SOME x in S

share|improve this question
6  
What kind of TA tells you that your statement is wrong but won't explain why? –  Rahul Jan 27 '12 at 20:57
    
Haha, no she tried! So did half of the class, but I'm pretty thick skulled when I think I'm right (and they didn't have as convincing reasons as the ones below). –  user13327 Jan 27 '12 at 21:02
2  
Haha, I totally understand. I've made a fool of myself in classes a few times, arguing with the instructor over something everyone else can see is true. –  Rahul Jan 27 '12 at 21:11

3 Answers 3

up vote 13 down vote accepted

The statement is wrong, among other reasons, because the statement

$C(x)$ implies $D(x)$

is true for any $x$ that is not a computer science student, and for any $x$ that takes discrete math. In particular, the statement

There exists $x\in S$ such that $C(x)$ implies $D(x)$. $\qquad\qquad\qquad$ (1)

would be true if nobody is a computer science major. However, I think most people agree that

Some computer science majors take discrete math

should be considered false if there are no computer science majors at all.

Also, the statement (1) would be true if there is at least one person taking discrete math, whether or not that person is a computer science major. So, in a university in which at least one person takes Discrete Math, but no computer science major does, the statement "There exists $x\in S$ such that $C(x)$ implies $D(x)$" would be true, but the statement "Some computer science majors take discrete math" would be false.

What you need to remember is that an implication is true if the antecedent is false, or if the consequent is true. You don't need the antecedent to be true.

What you actually want is:

There exists $x\in S$ such that $C(x)$ and $D(x)$.

share|improve this answer
    
Ahhh, I think I understand now. Thank you very much! –  user13327 Jan 27 '12 at 20:55
    
We're not reading carefully enough here, or the example comes as poorly constructed. The "some" here is NOT that of classical logic, since the plural "majors" gets used. merriam-webster.com/dictionary/some oxforddictionaries.com/definition/some –  Doug Spoonwood Jan 28 '12 at 14:27
1  
@Doug and Arturo: I've removed several of the extremely off topic discussion on English grammar. Off-topic I can generally tolerate. But not when it starts devolving into tones of voice that is dangerously close to becoming uncivil. –  Willie Wong Jan 31 '12 at 9:25

Remember that $C(x)\to D(x)$ is logically equivalent to $\lnot C(x)\lor D(x)$, which in words is ‘$x$ is not a computer science major, or $x$ takes discrete math (or both)’. Your statement, therefore, can be translated into English as

there is a college student who takes discrete math or is not a computer science major (or both).

Suppose that there is exactly one college student who takes discrete math, and he’s not a computer science major. Then your statement is true, but ‘some computer science majors take discrete math’ isn’t. Thus, yours can’t be the same statement.

share|improve this answer
    
This helped tremendously, thank you! –  user13327 Jan 27 '12 at 20:57

First off, the statement as stated isn't quite so easy to interpret in classical logic, since by rules of English grammar "some" in the sentence necessarily refers to a plural "majors", while "some" in classical logic doesn't necessarily refers to a plural. I'll guess that the writer of the statement almost surely meant to write "at least one computer science major takes discrete math." With that in mind it can get interpreted in classical logic.

For that statement, the TA probably has in mind "There exists x in S such that C(x) AND D(x)". This is NOT logically equivalent to "There exists x in S such that C(x) implies D(x)". If you interpret the statement as "There exists x in S such that C(x) implies D(x)" then you probably can reasonably get charged with over-interpretation, since, in some sense, "There exists x in S such that C(x) implies D(x)" more often ends up true than "There exists x in S such that C(x) AND D(x)".

It does hold that if "There exists x in S such that C(x) AND D(x)", then "There exists x in S such that C(x) implies D(x)". So, such an implication isn't wrong for some x in S per se. Such an implication gets entailed by the TA's interpretation. However, it does come as wrong to say that if "There exists x in S such that C(x) implies D(x)", then "There exists x in S such that C(x) AND D(x)". So, such an implication comes as wrong given that you take it as equivalent to the "and" interpretation.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.