Question

For two different persons \(x\) and \(y\), the predicate \(M(x, y)\) denotes that \(x\) knows \(y\).
Consider the following statement.
There is a person who does not know anyone else, but that person is known by everyone else.
Which one of the following expressions represents the above statement?

• A. \((\exists y)(\forall x)\, ((x \neq y) \rightarrow (M(x, y) \wedge \neg M(y, x)))\)
• B. \((\forall y)(\exists x)\, ((x \neq y) \rightarrow (M(x, y) \wedge \neg M(y, x)))\)
• C. \((\exists y)(\exists x)\, ((x \neq y) \rightarrow (M(x, y) \wedge \neg M(y, x)))\)
• D. \((\forall y)(\forall x)\, ((x \neq y) \rightarrow (M(x, y) \wedge \neg M(y, x)))\)

Hint:

The sentence describes exactly one special person, so use one existential quantifier for that person and one universal quantifier ranging over everyone else.

Answer 1

The Correct Option is A

Step 1: A good way to check a first-order translation without trusting intuition alone is to test it against a small concrete example universe and see if the formula behaves the way the English sentence demands.

Step 2: Imagine three people, $y$, $a$, $b$, where $y$ knows nobody else ($\neg M(y,a)$ and $\neg M(y,b)$) and both $a$ and $b$ know $y$ ($M(a,y)$ and $M(b,y)$). This is exactly the scenario the English sentence describes, so a correct formula must come out true here, and it should not require this to hold for every person in the universe, only for the one special person $y$.

Step 3: Check option (D), $(\forall y)(\forall x)$. This demands the pattern $M(x,y) \wedge \neg M(y,x)$ hold for EVERY pair, so it would also require $a$ to be known by everyone and know nobody, which is false in our example since $a$ knows $y$. So a universal outer quantifier is too strong and option (D) fails on this test case.

Step 4: Check option (C), $(\exists y)(\exists x)$. This only needs one witness pair, so it would already be satisfied by the pair $(y,a)$ alone, even if a third person $c$ both knew $y$ and was known by $y$, which would break "known by everyone else" for $y$. So an inner existential quantifier is too weak, it does not force the pattern across ALL other people, and option (C) fails.

Step 5: Check option (B), $(\forall y)(\exists x)$. This says every single person has some other person who knows them and whom they do not know, a claim about the entire population's social structure rather than about one special isolated-yet-famous person. This is a different and much broader statement than the one given, so option (B) does not match either.

Step 6: Only option (A), $(\exists y)(\forall x)\, ((x \neq y) \rightarrow (M(x,y) \wedge \neg M(y,x)))$, survives: it picks out one specific $y$ (existential outer) and forces the knows/does-not-know pattern to hold against every other person (universal inner), matching both halves of the English sentence exactly.

\[ \boxed{(\exists y)(\forall x)\, ((x \neq y) \rightarrow (M(x,y) \wedge \neg M(y,x)))} \]