Showing that ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x)

Question

Q(x, y) := “Student x did exercise y in the book”

R(x) := “Student x gets an A in the class”

So my goal is to show that the following equivalency holds:

∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x) (Note the exact parenthesis)

So the preceding statement would loosely translate to “If a student does at least one problem, they get an A in the class.”

However, everyone (classmates, TAs, professors, friends) disagrees with with my claim and, to the contrary, says that the statement the statement ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) translates to:

"If a student does ALL exercises, they get an A in the class."

I'm going a little crazy over being told I'm incorrect and still not being convinced of it. Any help would be so greatly appreciated!

I have chosen very simple sets consisting of 1 student (me!) and only 2 book exercises, so the sets are small enough that I can write out the truth tables easily. I know that in order to complete my proof, I must show that it works for all sets of students and exercises, but it's pretty clear that it would also extend to all sets of Students and Exercises if I wanted to take up a few more pages.

1. Let the set S = {Nathan} (Note: S is supposed to be the set of students)

2. Let the set E = {1, 2} (Note: S is supposed to be the set of book exercises)

3. In English, I want to show that the statement ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) translates to “If a student does at least one problem, they get an A in the class”

4. Let P be the following statement: ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) )

5. In English, we may interpret this as “for all pairs of x and y, the implication “Q(x, y) → R(x)” holds.

6. Because the statement is true for all elements in S and S only contains 1 element, we can simply rewrite this as (book reference 1): ∀y ∈ E ( Q(Nathan, y) → R(Nathan) )

7. Because the implication holds for every y ∈ E, and there's only 2 elements in E, we can exhaustively write this as the conjunction of all possible Q(Nathan, y) (book reference 1): [ Q(Nathan, 1) → R(Nathan) ] ∧ [ Q(Nathan, 2) → R(Nathan) ]

By truth table, I will show that the preceding statement is logically equivalent to the following statement:

[ Q(Nathan, 1) ∨ Q(Nathan, 2) ] → R(Nathan)

However, for the sake of fitting all my columns in one line, let:

A = Q(Nathan, 1)

B = Q(Nathan, 2)

R = R(Nathan)

So I need to show that the following logical equivalency holds: (A → R) ∧ (B → R) ≡ (A ∨ B) → R

A   B   R   A-->R   B-->R   (A-->R)^(B-->R) (A ∨ B) (A ∨ B) → R
T   T   T   T       T       T               T       T           
T   T   F   F       F       F               T       F           
T   F   T   T       T       T               T       T           
T   F   F   F       T       F               T       F           
F   T   T   T       T       T               T       T           
F   T   F   F       F       F               T       F           
F   F   T   T       T       T               F       T           
F   F   F   F       T       T               F       T           

8. Because the truth tables for (A → R) ∧ (B → R) and (A ∨ B) → R are identical, they are logically equivalent.

9. ∴ The statement P can be written as: ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ [ Q(Nathan, 1) → R(Nathan) ] ∧ [ Q(Nathan, 2) → R(Nathan) ] ≡ [ Q(Nathan, 1) ∨ Q(Nathan, 2) ] → R(Nathan)

10. Now let Q be the following statement (I ultimately want to show that Q ≡ P): ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x)

11. In English, we can interpret this as “For all students, if a student does at least one exercise they get an A in the class.”

12. Because the set S only has 1 element, we can rewrite this as (book reference 2): (∃y ∈ Exercises Q(Nathan, y)) → R(Nathan)

13. Because the set E only contains only 2 elements, we can exhaustively write this as the disjunction of of all possible Q(Nathan, y) (book reference 2): (Q(Nathan, 1) ∨ Q(Nathan, 2)) → R(Nathan)

14. ∴ The statement Q can be written as: ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x) ≡ (Q(Nathan, P1) ∨ Q(Nathan, P2)) → R(Nathan)

So per #9, I have shown that: ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ [ Q(Nathan, 1) ∨ Q(Nathan, 2) ] → R(Nathan)

And per #13, I have shown that: ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x) ≡ (Q(Nathan, 1) ∨ Q(Nathan, 2)) → R(Nathan)

15. ∴ ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x)

So I have shown that (at least, for my simple example sets of S = {Nathan} and E = {1, 2}), the translation of the original statement ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) can be written as:

∀x ∈ S              (∃y ∈ E Q(x, y))                →   R(x)
[ for all students ][ doing at least one problem ][ will get you an A in the class ]

So the question is: Am I correct or incorrect? And if I'm incorrect, where is my error?

I really, really appreciate any help! My question is very long only because prior attempts to “sum up” my argument have yielded unfruitful, so I wanted to show the entirety of my logic.

Book reference 1 (Discrete Mathematics and Its Applications 7th edition page #41): http://books.google.com/books?id=55GaBAAAQBAJ&pg=PA41&lpg=PA41&dq=%22When+all+the+elements+in+the+domain+can+be+listed%22&source=bl&ots=5mLN0LEs9c&sig=tADpIczl2xdN6fmTz9Zy0Lk3BqU&hl=en&sa=X&ei=I4VCVMfmIoWWyQScn4HICg&ved=0CB4Q6AEwAA#v=onepage&q=%22When%20all%20the%20elements%20in%20the%20domain%20can%20be%20listed%22&f=false

Book reference 1 (Discrete Mathematics and Its Applications 7th edition page #46): http://books.google.com/books?id=55GaBAAAQBAJ&pg=PA43&lpg=PA43&dq=%22When+all+elements+in+the+domain+can+be+listed%22&source=bl&ots=5mLN0LEtig&sig=iwWaDDu8MfPesB3bOLFBcdsAcos&hl=en&sa=X&ei=5YVCVOP7Ns2ryATo-oDQBA&ved=0CB4Q6AEwAA#v=onepage&q=%22When%20all%20elements%20in%20the%20domain%20can%20be%20listed%22&f=false

Answer 1

Your interpretation is correct. One way to see this is to look at the negation of the statement:

$$\begin{align*} \neg\forall x\,\forall y\,\big(Q(x,y)\to R(x)\big)&\equiv\exists x\left(\neg \forall y\,\big(Q(x,y)\to R(x)\big)\right)\\ &\equiv\exists x\,\exists y\left(\neg\big(Q(x,y)\to R(x)\big)\right)\\ &\equiv\exists x\,\exists y\big(Q(x,y)\land\neg R(x)\big)\;. \end{align*}\tag{1}$$

This is true provided that there are a student $S$ and an exercise $e$ such that $S$ did $e$ but did not get an A in the class. Suppose, then, that $S$ was the only student in the class who did even one of the exercises, $S$ did only exercise $e$, and $S$ did not get an A in the class. Then $(1)$ is true, so the original statement

$$\forall x\,\forall y\,\big(Q(x,y)\to R(x)\big)$$

is false. If $S$ gets an A, however, $(1)$ becomes false: $Q(x,y)$ is false unless $x=S$ and $y=e$, in which case $R(x)=R(S)$ is true and $\neg R(S)$ is false. But $(1)$ is the negation of the original statement, which is therefore true in this setting — even though just one student has answered a question, and that student has answered only one question.

Everyone else appears to be thinking of the statement

$$\forall x\big(\forall y\,Q(x,y)\to R(x)\big)\;.$$

You can of course also let the class be $\{x_1,\ldots,x_n\}$ and the set of exercises by $\{y_1,\ldots,y_m\}$. Then

$$\begin{align*} \forall x\,\forall y\,\big(Q(x,y)\to R(x)\big)&\equiv\forall x\Big(\big(Q(x,y_1)\to R(x)\big)\land\ldots\land\big(Q(x,y_m)\to R(x)\big)\Big)\\ &\equiv\forall x\Big(\big(\neg Q(x,y_1)\lor R(x)\big)\land\ldots\land\big(\neg Q(x,y_m)\lor R(x)\big)\Big)\\ &\equiv\forall x\Big(\big(\neg Q(x,y_1)\land\ldots\land\neg Q(x,y_m)\big)\lor R(x)\Big)\\ &\equiv\bigwedge_{i=1}^n\Big(\big(\neg Q(x_i,y_1)\land\ldots\land\neg Q(x_i,y_m)\big)\lor R(x_i)\Big)\;. \end{align*}$$

For each student $x_i$ in the class this says

$$\big(\neg Q(x_i,y_1)\land\ldots\land\neg Q(x_i,y_m)\big)\lor R(x_i)\;,$$

i.e., either $x_i$ does no question at all, or $x_i$ gets an A in the class. If $x_i$ does even just one question, the only way for this to be true is for $x_i$ to get an A in the class. Thus, the original sentence does indeed say that each student who does at least one question gets an A in the class.

Answer 2

Here's a proof I came up with that works for any finite set S and E that uses propositional expansion to show: $\forall x \forall y (Q(x, y) \to R(x)) \equiv \forall x (\exists y Q(x, y) \to R(x))$

$\text{The set } S = \{x_1, x_2, \ldots, x_n\} \\\text{The set } E = \{e_1, e_2, \ldots, e_m\} $

$\begin{align*}\forall x \forall y (Q(x, y) \to R(x))\equiv \\\forall y (Q(x_1, y) \to R(x_1)) \land && \text{propositional expansion of } \forall x \\\forall y (Q(x_2, y) \to R(x_2)) \land \\ \ldots \land \\\forall y (Q(x_n, y) \to R(x_n))\equiv \\ [Q(x_1, e_1) \to R(x_1)] \land \ldots \land [Q(x_1, e_m) \to R(x_1)] && \text {propositional expansion of } \forall y \\ [Q(x_2, e_1) \to R(x_2)] \land \ldots \land [Q(x_2, e_m) \to R(x_2)] \\ \ldots \land \\ [Q(x_n, e_1) \to R(x_n)] \land \ldots \land [Q(x_n, e_m) \to R(x_n)] \\\equiv \\ [ (Q(x_1, e_1) \lor \ldots \lor Q(x_1, e_m)) \to R(x_1) ] \land && \text {note 1} \\ [ (Q(x_2, e_1) \lor \ldots \lor Q(x_2, e_m)) \to R(x_2) ] \land \\\ldots \land \\ [ (Q(x_n, e_1) \lor \ldots \lor Q(x_n, e_m)) \to R(x_n) ] \equiv \\ [ (\exists y Q(x_1, y) \to R(x_1)] \land && \text{note 2} \\ \ldots \land \\ [ (\exists y Q(x_n, y) \to R(x_n) ] && \text{note 3} \\\equiv \\\forall x (\exists y Q(x, y) \to R(x)) \end{align*}$

$\text{note 1: } (p_1 \to q) \land (p_2 \to q) \land \ldots \land (p_n \to q) \equiv (p_1 \lor p_2 \lor \ldots \lor p_n) \to q \\\text{note 2: } (P(x_1) \lor P(x_2) \lor \ldots \lor P(x_n)) \equiv \exists x P(x) \text{ (reverse propositional expansion)} \\\text{note 3: } (P(x_1) \land P(x_2) \land \ldots \land P(x_n)) \equiv \forall x P(x) \text { (reverse propositional expansion)} $