2

I am reading the book How to prove it, and doing some of the exercise.

In section 2.2, it asked us to negate the statement: Everyone has a roommate who dislike everyone. And then reexpress the results as equivalent positive statements.

My trial: Let $R(x,y)$ means $x$ is a roommate of $y$. And L(x,y) means $x$ likes $y$.

$$\forall x \exists y (R(x,y) \to \forall z(\neg L(y,z)))$$ negate this and get $$\neg \forall x \exists y (R(x,y) \to \forall z(\neg L(y,z))$$ The answer is $$\exists x \forall y(R(x,y) \land \exists z (L(y,z)))$$

The answer is very similar to the correct answer, $\exists x \forall y (R(x,y) \to \exists z(L(y,z)))$

After some investigation, I found that if I set the first equation to be $$\forall x \exists y (R(x,y) \land \forall z(\neg L(y,z)))$$ then I will get the correct answer.

So, my question is what is the difference between the equation that used "if" and the one used "and".

I am confused because in another question: Everyone who is majoring in math has a friend who needs help with his homework. I wrote the logical form as $$\forall x (M(x) \to \exists y(F(x,y) \land H(y)))$$. where $M(x)$ means $x$ is a math major, $F(x,y)$ means $x$ is a friend of $y$ and $H(y)$ means $y$ needs help on homework.

Can I write it as $$\forall x (M(x) \land \exists y(F(x,y) \land H(y)))$$.

JOHN
  • 1,176
  • 9
  • 26
  • In the initial formula, consider the case where you pick a $y$ who is not a roommate of $x$. In particular, what if no one is the roommate of $x$? – Derek Elkins left SE Feb 03 '19 at 04:03
  • Recall that $P\land Q$ is logically equivalent to $\neg(P\to \neg Q)$. –  Feb 03 '19 at 04:18

1 Answers1

1

$\forall x ~\exists y ~(R(x,y) \to \forall z(\neg L(y,z)))$ says "For everyone ($x$) there exists someone ($y$) who, if they ($y$) are the first person's ($x$) roommate, then they ($y$) will dislike everyone." &nbsp Thus it is not what you want.

In section 2.2, it asked us to negate the statement: Everyone has a roommate who dislike everyone.

Recall, universal statements are restricted by conditional and existential statements are restricted by a conjunction. $$\forall x\in A: P(x)\iff \forall x~(x\in A\to P(x))\\\exists y\in B: Q(y)\iff \exists y~(y\in B\land Q(y))$$

You want to say "For every person there exists a person, who is their roommate and dislikes everyone".   Here the implcit domain is people and the restriction is on the existential (to roommates of the first entity).   It is, basically: $$\forall x{\in}\text{People}~\exists y{\in}\text{RoommatesOf}(x)~\forall z{\in}\text{People}:\lnot L(y,z)$$

Hence:$$\forall x~\exists y~(R(x,y)\land\forall z~(\lnot L(y,z)))$$

I am confused because in another question: Everyone who is majoring in math has a friend who needs help with his homework. I wrote the logical form as $$\forall x (M(x) \to \exists y(F(x,y) \land H(y)))$$. where $M(x)$ means $x$ is a math major, $F(x,y)$ means $x$ is a friend of $y$ and $H(y)$ means $y$ needs help on homework.

Now, here you are restricting both the universal entities and the existential entities: $$\forall x{\in}\text{MathMajors}~\exists y{\in}\text{FriendsOf}(x): H(y)$$

Graham Kemp
  • 129,094
  • Thank you! If I took "universal statements are restricted by conditional and existential statements are restricted by a conjunction." as given, I understand now.

    But I am not very convinced on this statement. Can you explain a bit more?

     – JOHN Feb 03 '19 at 05:16