Am I correct in the following:

If the domain is all students, and C(x,y) is the predicate of x having chatted with y. Then the sentence

There is a student in this class who has chatted with exactly one other student

Can be represented as $$\exists x\exists y(y\ne x\land \forall z(z\ne x\to(z=y\leftrightarrow C(x,z))))$$

Which is logically equivalent to:

$$\exists x \exists y[(x\neq y) \land\forall z ([z=x] \lor[(z\neq y) \lor C(x,y)] \land [\lnot C(x,y) \lor (z = y)])]$$

The negation of which would be:

$$\forall x \forall y [(x=y) \lor \exists z([z\neq x] \land [(z =y) \land \lnot C(x,y)] \lor[C(x,y) \land(z \neq y)])]$$

That is also logically equivalent to:

$$\forall x \forall y [(x = y) \lor \exists z([z \neq x] \land [C(x,y) \leftrightarrow (z \neq y)])]$$

Which can be translated to: All students have spoken with at least one other student or themselves?


2 Answers 2


The negation would be: For all students x, either x has chatted with no other students or x has chatted with more than one other student.

[This is just ruling out x chatting with exactly one other student.]

  • 1
    $\begingroup$ How does $\exists z([z \neq x] \land [C(x,y) \leftrightarrow (z \neq y)])$ mean more than one? $\endgroup$ Jan 17, 2019 at 0:45
  • $\begingroup$ @Elliott I was negating the statement in yellow of OP's posted question. The sentence of your comment is one the OP obtained, and I didn't think it was right. $\endgroup$
    – coffeemath
    Jan 17, 2019 at 4:10

As coffeemath indicated, the negation should of course end up being that every student either ends up chatting with no other students, or with two or more.

However, the logic expression you got at the end does not translate as such. And that's because you made a small mistake. Note that your $C(x,z)$ became $C(x,y)$, and that should not have happened. Indeed, you final expression should have been:

$$\forall x \ \forall y (x =y \lor \exists z (z \not = x \land [C(x,z) \leftrightarrow z \not =y]))$$

Ok, but how does that mean that every student ends up chatting with no other students, or with two or more? That is still not immediately obvious, so let me explain.

First, I would recommend rewriting it as:

$\forall x \ \forall y (x \not = y \rightarrow \exists z (z \not = x \land [C(x,z) \leftrightarrow z \not = y])) \tag{1}$

This is still hard to parse in English, but at least it starts with two different students $x$ and $y$ and now of course we want to make sure that either they didn't chat at all, or that they did chat but there is a third student $z$ that $x$ chatted with as well. In other words, we want to show that if $x$ and $y$ did chat, then there must be some third student $z$ that $x$ chatted with as well.

Ok, so let's suppose $x$ and $y$ chatted. Given $(1)$ and given that $x$ and $y$ are different, we know that there is some $z$ that is different from $x$ such that $C(x,z) \leftrightarrow z \not =y$.

Now, if $z=y$ then the right side is false, and hence the left side is false as well, and hence $x$ did not chat with $z=y$ .. but we assumed $x$ did chat with $y$, so we have a problem. So, $z$ is some other than $y$, and therefore $x$ did chat with $z$.

And so there you go: as soon as $x$ chats with some other student $y$, then there has to be some third student $z$ that $x$ chats with as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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