Difference between "$\forall k\in [m] $ there exists an optimal $O$ S.T. $Gk\subseteq O$" and "$\forall k\in [m] Gk\subseteq O$ where $O$ is optimal"

25 Views Asked by At

During a test (The details of the question are irrelevant) I used, while proving the optimality of an algorithm, the following argument:

$$1. \forall k\in[m],\,\,G_{k}\subseteq O,\ \text{ where $O$ is an optimal solution}$$ Points were deducted and the grader claimed I should have used:

$$2. \forall k\in[m]\text{ there exists an optimal solution }O\text{ S.T. }G_{k}\subseteq O$$

To me these two statements seem identical. Is there in fact a logical difference?

Nitpick away.

P.S. If there are more appropriate tags then the ones I used feel free to change them.

1

There are 1 best solutions below

0
On BEST ANSWER

Your statement is ambiguous, since you have not explained how the variable $O$ is quantified. Are you claiming that $G_k\subseteq O$ for every $O$ which is an optimal solution? Or that there is some particular optimal solution $O$ such that $G_k\subseteq O$ for every $k$? Or that for each $k$, there is an optimal solution $O$ (possibly a different one for different $k$) such that $G_k\subseteq O$? These three statements are all different, and what you wrote could be interpreted as any of them. In contrast, your grader's version is perfectly precise, and can only mean the third option.