Expressing statements in positive way

Question

I have been working on this problem from Velleman's How to prove book:

Negate these statements and then reexpress the results as equivalent positive statements.
(a) There is someone in the freshman class who doesn’t have a roommate.

I solved the question like this:

F(x) = x is in the freshman class
R(x,y) = x has roommate y.

Original Statement:

• ∃x F(x) ∧ ¬R(x,y)

Negate:

• ¬∃x F(x) ∧ ∃y¬R(x,y)
• ∀x¬(F(x) ∧ ∃y¬R(x,y))
• ∀x¬F(x) ∨ ∀yR(x,y)
• ∀x∀y ¬F(x) ∨ R(x,y)
• ∀x∀y F(x) -> R(x,y)

And translated back to english like this:

Someone in the freshman class has a roommate.

I have been verifying my answers from here and according to it the solution is ∀x[F(x)→∃yR(x,y)]. Can somebody point out the right way of doing this?

Answer 1

The error is in the "formalization" of the first statement; you have to start with :

$∃x(F(x) \land \lnot ∃yR(x,y))$

because the "non-existence" of roommates is "relative to" the freshman student; thus, the second existential quantifier must be in the scope of the first one.

Denaying it, we have that [remember that : $\lnot(P \land Q)$ is equivalent to : $(\lnot P \lor \lnot Q)$] :

$∀x (\lnot F(x) \lor ∃yR(x,y))$

which is [remember that : $(\lnot P \lor Q)$ is equivalent to : $(P \rightarrow Q)]$ :

$∀x (F(x) \rightarrow ∃yR(x,y))$.

Answer 2

The problem here is in your original translation (we assume the universe of discourse to be people):

(a) There is someone in the freshman class who doesn’t have a roommate.

Note that your original translation has left $y$ as a free variable.

I. "There exists someone $x$ ( such that $x$ isin the freshman class, and such that for all $y$, it is not the case that $x$ has roommate $y$.)"

II. Alternatively, we can write this as "There exists someone $x$ (such that $x$ is in the freshman class and there is no one $y$ such that $x$ has roommate $y$.")

So this can be written, using your key, $$I.\;\;\exists x \Big(F(x) \land \forall y(\lnot R(x,y))\Big)$$

$$II. \;\;\exists x\Big(F(x) \land \lnot \exists y(R(x,y))\Big)$$

Note that $I$ becomes $II$ by taking the portion $\forall y \lnot (R(x, y))$ and writing this as $\lnot \exists y(R(x,y))$.

Now negating $(II)$, we have

$$\begin{align} \lnot\exists x\Big(F(x) \land \lnot \exists y(R(x, y))\Big) &\equiv \forall x\Big(\lnot\Big(F(x) \land \lnot \exists y(R(x,y))\Big)\Big) \\ \\ &\equiv \forall x\Big(\lnot F(x) \lor \lnot \lnot \exists y(R(x,y))\Big)\\ \\ &\equiv \forall x\Big(\lnot F(x) \lor \exists y(R(x, y))\Big)\\ \\ &\equiv \forall x\Big(F(x) \rightarrow \exists y(R(x, y))\Big) \end{align}$$

...which translates to "Every freshman has a roommate."