1
$\begingroup$

Problem 1 is really simple but 2 is confusing me a little. I'm going on the assumption that $x$ and $y$ are both students and they are saying $z$ is the class? Is it really as simple as what I wrote or am I missing something?

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 these statements by a simple English sentence.

1) C(Randy Goldberg, CS 252)
2) $\exists x\exists y\forall z((x\neq y) \land (C(x, z)\to C(y, z)))$

1) The student Randy Goldberg is enrolled in the class CS252.
2) All classes have multiple students.

Or should 2 be: Each class has two different students enrolled in it.

  • 0
    Yes it is correct. Didn't know this site supported TeX formatting. Thank you for the information.2012-07-06

3 Answers 3

2

Statement 2 means that, there is some distinct pair of students $x,y$ such that for any class $z$ if student $x$ is enrolled in class $z$ then student $y$ is enrolled in class $z$.

Edit: I read the quantifiers backwards. Fixed.

2

There EXIST two distinct students such that FOR ALL classes (One student being in the class IMPLIES the other being in the class).

More simplified:

"There are two students where one student takes all the classes that the other takes."

2

Answers by Alex Becker and Robert Mastragostino describe another statement: $P_3:\exists x(S(x)\land \exists y(S(y)\land (x\neq y) \land \forall z(L(z) \to C(x, z)\to C(y, z))))$

where $S(x)$ means “$x$ is a student” and $L(x)$ means “$x$ is a class”. I suppose that your logic is 1-sorted, i. e., variables range over classes and students.

I denote your statement 2 as $P_2$. We cannot prove $P_2$ and $P_3$ equivalent. Suppose that there are 2 classes and no students. Then $P_2$ is true: take those classes as $x, y$; $x\neq y$ is true; for all $z$, $C(x, z)$ is false because it makes no sense for a class to be enrolled in something. $P_3$ is false because we can not choose $x$ because there are no students.

The correct translation of $P_2$ is “there are $x$ and $y$ such that for every $z$, $x$ and $y$ are distinct and if $x$ is enrolled in $z$ then $y$ is enrolled in $z$”. You must not tell words “student” and “class” because there is no $S$ and $L$ in $P_2$.

If you want to learn more, I recommend to consider a logic with sorts $S$ (students) and $L$ (classes). In this logic there are similar statements: $P_4: (\exists x\in S(\exists y\in S(\forall z\in L((x\neq y) \land C(x, z)\to C(y, z)))))$

$P_5: (\exists x\in S(\exists y\in S((x\neq y) \land \forall z\in L(C(x, z)\to C(y, z)))))$

Answers by Alex Becker and Robert Mastragostino describe $P_5$. Note that $(x\neq y)$ sits in different places in $P_4$ and $P_5$. We cannot prove $P_4$ and $P_5$ equivalent. Suppose that there are only 1 student and no classes. Then $P_5$ is false and $P_4$ is true.