Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What does ~= mean? Perhaps $\neq$? – Alex Becker Jul 6 '12 at 5:19
X does not equal y I didn't know how to do the symbol ≠ – LF4 Jul 6 '12 at 5:21
I reformatted the question using LaTeX markup. Please verify that it is correct as it appears now. – Alex Becker Jul 6 '12 at 5:24
Yes it is correct. Didn't know this site supported TeX formatting. Thank you for the information. – LF4 Jul 6 '12 at 5:26
up vote 2 down vote accepted

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.

share|cite|improve this answer

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."

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.