Prove that $\left\{\neg(\forall x \in M:a(x))\right\}\Leftrightarrow \left\{\exists x \in M: \neg a(x)\right\}$

Question

Let $a(x)$, $x \in M$ be a form of statement.

Prove that $\left\{\neg(\forall x \in M:a(x))\right\}\Leftrightarrow \left\{\exists x \in M: \neg a(x)\right\}$

I have started by trying to translate this to "human" language:

Exactly when not for all x in M a(x) is necessary, we have that there exists an x in M so that we have the negation of a(x).

Sorry my English but did I translate this correctly? My translation doesn't really help me finding a solution to this task though...

But the left side is saying that we have for all negations of x in M the negation a(x).

If every x, so says the left side, has a negation of a(x), then there basically must be (exists) at least one x which satisfies the right side. So it must be true for sure... Damn this is really complicated.

I would be very interested in seeing a correct proof of this, please.

Answer 1

Another way to look at this is to know that the negation of "all" is "not all", as opposed to "none at all."

Let $M$ be the set of all males. Let $a(x)$ denote "x is an A-student." So say we start with someone claiming $$\forall x \in M:a(x)$$

That means that what's being claimed is: "every male student is an A-student."

But perhaps Mary notices that the claim is false, because she knows for a fact that John (a male student) has only a C-average, and hence is not an A-student.

What Mary noted is a "counterexample" to the claim that every male student is an A-student. Hence, Mary is justified in concluding, "No....$$\lnot(\forall x \in M:a(x))\tag{1}$$ Indeed, she knows that there exists a male student (John) who is not an A-student, i.e., $$(\exists x \in M: \lnot a(x)).\tag{2}$$

That is, $(1),$ and $(2)$ are equivalent

---

Note that the negation of $\exists x \in M: a(x)$ is $\lnot(\exists x \in M: a(x))$ which means that there does not exist any $x \in M$ such $a(x)$; which is equivalent to saying $(\forall x\in M: \lnot a(x))$

Answer 2

$$\left\{\neg(\forall x \in M:a(x))\right\}\Leftrightarrow \left\{\exists x \in M: \neg a(x)\right\}\tag{*}$$

Consider two statements in "human" language:

• (A) For every $x$ in $M$, $a(x)$ is true;
• (B) There exists $x$ in $M$ such that $a(x)$ is not true.

What $(*)$ says is that (A) is not true if and only if (B) is true.

To prove $(*)$, you need to show two directions:

• Suppose (B) is true, show that (A) cannot be true.
• Suppose (A) is not true, show that (B) must be true?