Velleman's How to Prove it Question. (2.2 Ex. 1.b)

Question

I have a question, regarding this exercise, I've noted this across some other exercises but wanted to clear it up.

The exercise is to negate the statement and re-express the result as an equivalent positive statement.

This one specifically states: "Everyone has a roommate who dislikes everyone.

So the first step is to translate it to a logical statement, for which I get this:

$$\forall x \exists y (R(x,y) \land \forall x\neg L(y,x))$$

and after negation

$$\exists x \forall y(R(x,y) \to \exists x L(y,x))$$

But when I check the answer in the book I see this as the answer

$$ \exists x \forall y(R(x,y) \to \exists z L(y,z)) $$

So my question is, Why do they use another variable (in this case "$z$") to speak about the "everyone that the roommate dislikes" when it could be the same "$x$" we first use to speak to the "everyone that has a roommate"?.

Thanks again for any help! (:

Answer 1

The variable $x$ is already fixed at that point in the statement as the person such that no roommate of this person dislikes everyone. As a result we can't define $x$ to stand for someone else. So the issue with the statement you have as a logical statement is the "$\exists x$" that appears after $x$ has already been fixed. We could remove this and obtain a valid statement:

$$\exists x\forall y(R(x,y) \to L(y,x))$$

However, this statement means something different than what we want; namely "There is a person that is liked by every one of his roommates."

Now this actually goes back to your original statement, which should be $$ \forall x \exists y(R(x,y) \land \forall z \neg L(y,z)) $$ for similar reasons.

Answer 2

Your answer is just fine; you can indeed 'reuse' variables in just the way you do.

And in fact your translation is logically equivalent to the book's. So your answer is perfectly correct.

I am sure the book chose to use a new variable, though, since it helps the reader to conceptually parse the statement as each variable gets a unique role: The $x$ is the 'person who has a roommate', the $y$ is the 'roommate', and the $z$ is the 'person that the roommate dislikes'. Whereas if you recycle the $x$, the $x$ takes on a different role depending on which quantifier's scope it is in, so many people find that a little more confusing.

In sum, there is indeed no need to use a new variable, but it can make the sentence a little easier to understand.