Why does "Some student has asked every faculty member a question" translate to $\forall y (F(y) \to \exists x (S(x) \lor A(x, y)))$?

280 Views Asked by At

Context: I'm in undergrad discrete math, this is a textbook question from Discrete Mathematics and its Applications 7th edition
Here's the question:

Let S(x) be the predicate "x is a student," F(x) the predicate "x is a faculty member," and A(x, y) the predicate "x has asked y a question," where the domain consists of all people associated with your school. Use quantifiers to express the following statement.
Some student has asked every faculty member a question.

This is what the textbook says is the correct answer:
$$\forall y (F(y) \to \exists x (S(x) \lor A(x, y)))$$ I mostly understand how this is correct, but shouldn't it be $\land$ instead of $\lor$ ?

2

There are 2 best solutions below

0
On

Note that bounded quantifiers are translated as follows:

"There exists some student $x$ such that $P(x)$" is translated as $\exists x (S(x) \land P(x))$.

"For all faculty members $y$, $P(y)$" is translated as $\forall y (F(y) \to P(y))$.

In my view, the obvious meaning of this sentence is that there exists a student $x$ such that for all faculty members $y$, $x$ has asked $y$ a question. That is,

$$\exists x (S(x) \land \forall y (F(y) \to A(x, y))$$

The alternate interpretation (and in my view the less natural interpretation of the English phrase) is that for all faculty members $y$, there exists a student $x$ such that $x$ has asked $y$ a question. This is translated as

$$\forall y (F(y) \to \exists x (S(x) \land A(x, y))$$

So as you say, it should be $\land$ and not $\lor$.

0
On

Further to Mark's answer, whose correction $$\exists x (S(x) \land \forall y (F(y) \to A(x, y))$$ I second:

Some student has asked every faculty member a question.

This is what the textbook says is the answer: $$\forall y \bigg(F(y) \to \exists x \big(S(x) \lor A(x, y)\big)\bigg).$$

I mostly understand how this is correct, but shouldn't it be $\land$ instead of $\lor$ ?

  1. By flipping the $\lor$ to an $\land,$ the book's suggested answer becomes “every faculty member has been asked, by some student, a question”, which is still wrong (here, I disagree with Mark that this new answer is merely an unnatural interpretation of the given English sentence).
  2. Notice that the book's suggested answer is logically equivalent to $$\forall y \bigg(F(y) \to \exists x A(x, y)\bigg)\lor \exists x S(x),$$ i.e., “Either every faculty member has been asked, by someone in the domain of discourse (perhaps a janitor), a question, or there is some student”, which is of course egregiously incorrect.