Express the statement which have universal quantifier

Question

Let C(x, y) mean that student x is enrolled in class y, where the domain for x consists of all students in your school and the domain for y consists of all classes being given at your school. Express each of the statement by a simple sentence. I have a statement: $$\exists x\exists y\forall z((x\ne y)\land(C(x,z)\to C(y,z))$$ And the answer in the book: "There exist at least two students such that if one is enrolled in every course, then the other is."

However, I think the answer should be: "There exist at least two students such that every course for which one is enrolled in, is enrolled in by the other."

Are they different? Which sentence is true?. Please explain for me.

Thanks!

Answer 1

No, you are correct.

I would indeed read $\exists x~\exists y~\forall z~(x\neq y\wedge (C(x,z)\to C(y,z)))$ as "There exists two distinct things, such that for anything, in which the the first is enrolled, the second is also enrolled." You can also write this as: $$\exists x~\exists y~(x\neq y\wedge \forall z~(C(x,z)\to C(y,z)))$$

---

The book's answer would be for $\exists x~\exists y~(x\neq y\wedge (\forall z~C(x,z)\to\forall z~C(y,z)))$, which in Prenex form would be: $$\exists x~\exists y~\exists z~\forall w~(x\neq y\wedge (C(x,z)\to C(y,w))) $$

So clearly not the same thing.

Answer 2

You are correct, the book is wrong. Taking a set-theoretic view, write $C(x)$ for the set of classes that $x$ is enrolled in, i.e. $z\in C(x)\iff C(x,z)$.

The formula can then be written as $$\exists x\exists y(x\neq y)\land\forall z(z\in C(x)\to z\in C(y))$$ which is to say $$\exists x\exists y(x\neq y)\land(C(x)\subseteq C(y))$$ That is, the set of classes $x$ is enrolled in is a subset or equal to the set of classes $y$ is enrolled in.

The book's statement holds whenever there are at least two students and at least one of them is not enrolled in all classes. In particular, if there were two students each enrolled in one class and those classes are different, then the book's statement holds, but your statement and the formula does not.

Answer 3

I think that they are different (and in fact, I don't think that either are correct). If we turned the answer in the back into quantifiers, it would be $\exists x \exists y ( ( \forall z (C(x,z)) ) \implies( \forall z(C(y,z)) ) )$.

If we turned your answer back into quantifiers, it would be $\exists x \exists y \forall z(C(x,z) \implies C(y,z) \wedge C(y,z) \implies C(x,z))$ (Since the way you worded it seems to imply both implications; this is probably what the textbook was trying to avoid)

Your answer is closer.

I think the answer should actually be: "There exist a first and second student such that for every course, the students are distinct and the first being enrolled in the course implies that the second is enrolled in the course."

Note that the way that the quantifiers are presented, the statment can be true even if there is only one student but no courses since the students $x$ and $y$ need to be distinct for every course which is always the case if there are no courses. To illustrate this, consider the true statment $(\forall x \in \emptyset)(0 \neq 1)$.

What they probably should have written for the question is $\exists x \exists y(x\neq y \wedge \forall z (C(x,z) \implies C(y,z) ) ) $