Disproving a predicate-logic claim

Question

The following question is taken from UCLA's Logic quiz:

Let $P(n,m)$ be a property about two integers $n$ and $m$. If we want to disprove the claim "There exists an integer $n$ such that $P(n,m)$ is true for all integers $m$", then we need to prove that ___?

I understand that the correct answer is

For every integer $n$, there exists an integer $m$ such that $P(n,m)$ is false.

I am not sure why this option is incorrect:

There exists an integer m such that $P(n,m)$ is false for all integers $n.$

After all, if I show the existence of an $m^*$ such that $P(n, m^*)$ is false for all $n,$ then there cannot exist an $n^*$ such that $P(n^*,m)$ is true for all $m$. What am I missing?

Answer 1

As an example, suppose $P(n,m)$ is "$n+m$ is even."

Then the statement to refute is

There exists an integer $n$ such that (($n+m$ is even) for all integers $m$).

This is indeed false. I'm adding parentheses to avoid ambiguities in English language meaning.

The correct negation is

For every integer $n$, (there exists an integer $m$ such that ($n+m$ is not even)).

This is true.

Your other statement would be

There exists an integer $m$ such that (($n+m$ is not even) for all integers $n$).

This is false! No single $m$ will make $n+m$ always odd for all possible $n$.

The order of quantifiers matters. In the correct negation, we need one $m$ for each $n$ which makes $P(n,m)$ false, but $m$ can depend on $n$. Your other statement claims there's one $m$ which will make $P(n,m)$ false no matter what $n$ is. That's a stricter condition, not in general equivalent.