# Order of statements in implication

The question is from Exercise 13 of part 1.4 in Rosen's "Discrete Mathematics and Its Applications" (5th edition): "let $M(x,y)$ be "$x$ has sent y an e-mail message", where the universe of discourse consists of all students in your class".

The sentence to be translated to predicate language is: "g) there is a student in your class who has sent everyone else in your class an e-mail message"

My solution is:

$$\exists x \ \forall y \ \ (M(x,y)\implies x \neq y)$$

The solution in the instructor's manual of Rosen's book has the statements of the implication in reverse:

$$\exists x \ \ \forall y \ \ (x \neq y \implies M(x,y))$$

Which one is correct? To me it seems that the solutions manual is incorrect. The solution from the manual is true if the antecedent is F and the consequent T, which would mean that if the student is himself/herself, then he/she has sent himself/herself an e-mail message, so it seems to be wrong in my mind because the original idea was to exclude sending messages to oneself. The first solution allows x to send y an e-mail message only if it is not sent to oneself and if the e-mail is not sent, then it doesn't matter to whom it is sent.

An other approach by the writing the negation of your statement and the book's statement :

• The negation of $\exists x \ \forall y \ \ (M(x,y)\implies x \neq y)$ is : For all $x$ there exist $y$ such that $x$ sent $y$ an email and ($x$ and $y$ is the same person).

In other word :

For all $x$, $x$ sent an email to himself.

• The negation of $\exists x \ \ \forall y \ \ (x \neq y \implies M(x,y))$ is :

For all $x$ there exist $y$ such that $x$ is different from $y$ and $x$ didn't send an email to $y$

In other word :

For all $x$ there exist $y$ different from $x$ such that $x$ didn't send an email to $y$.

You can see that this second statement is the exact negation of the one wanted.

Note that for the statement of the negation I used the fact that $(P \Longrightarrow Q)$ is the same as $\lnot P \vee Q$

• Ok, so the negation of $\exists x \ \forall y \ \ (M(x,y)\implies x \neq y)$ is $\forall x \ \exists y \ \ (M(x,y) \land x = y \ )$ and the negation of $\exists x \ \ \forall y \ \ (x \neq y \implies M(x,y))$ is $\forall x\ \exists y \ \ (x \neq y \land \neg M(x,y))$. Now it is much clearer for me – MPO Aug 3 '15 at 10:43
• That's right. I am happy to hear that. I want to point out to pay attention to the quantifiers if they rule $P$ only or the whole implication as they do in this case. – Aymane Fihadi Aug 3 '15 at 11:13

Statement $1$ is $\exists x\forall y (M(x,y) \implies x\ne y)$

This can be interpreted as:

There exists a student such that for all students, if student $x$ has sent student $y$ an email, student $x$ is not student $y$.

This doesn't implies that the student has sent everyone but themselves an email, or even any student an email, just that they haven't sent an email to themselves.

Statement $2$ is $\exists x\forall y (x\ne y \implies M(x,y))$

This is correct. It can be interpreted as:

There exists a student $x$ such that for all students, if student $x$ is not student $y$, then they have sent student $y$ an email.

And statement $2$ also means that student $x$ has not sent an email to themselves.