So I was practicing nested quantifiers for class, and I came to an answer which I think is right, but the book gave something slightly different. For starters, the context of the question is this:
- Let $S(x)$ be the predicate “$x$ is a student”, $F(x)$ be the predicate “$x$ is a faculty member”, and $A(x, y)$ be the predicate “$x$ has asked $y$ a question”, where the domain consists of all people associated with your school.
h) Some student has never been asked a question by a faculty member.
My answer to this = $∃x∃y(S(x) ∧ F(y) → ¬A(y, x))$
The books answer = $∃x(S(x) ∧ ∀y(F(y) → ¬A(y, x)))$
Does the $∀y$ have to be in the middle of the expression to be correct? Does the book show it this way because it's clearer where the nesting occurs?
Best Answer
Not necessarily; see Prenex normal form equivalences : $(\forall y\phi )\land \psi$ is equivalent to $\forall y(\phi \land \psi)$.
Thus, $∃x[S(x) ∧ ∀y(F(y) → ¬A(y, x))]$ and $∃x∀y[S(x) ∧ (F(y) → ¬A(y, x))]$ are equivalent.
Having said, that, the book's transaltion sounds more similar to natural language :