How to prove negations of quantifiers?

Question

It is well known that the negation of "for all x, P(x)" is "not exists an x such that not P(x)".

Same on the other side, the negation of "there exists an x such that P(x)" is "not for all / any x, not P(x)".

Is there proof of these concepts or are they taken as given axioms or self-evident concepts?

Answer 1

Simple answer is that those concepts are taken as "axioms". Those are fundamentals of logic and its existence.

If not all people wear blue shirts, then there must be people who don't wear blue shirts.

If there are no people who ride dinosaurs, then that means that everyone doesn't ride a dinosaur.

Answer 2

Quantificational logic has a clear formal semantics defined for these two logical operators: it basically provides a formal way of defining what the statements mean.

First: an interpretation $I$ for a logic sentence $\varphi$ is defined as a set of objects (called its domain $D$), together with mappings from all constant symbols, function symbols, and predicate symbols to these objects, functions defined over these objects, and sets of tuples of these objects, respectively.

Second: using an interpretation $I$, we can then define what it takes for some sentence $\varphi$ to be true according to some interpretation $I$. We will write this as $I \vDash \varphi$. This definition will be spelled out for all logical symbols, including the quantifiers.

In particular, the formal semantics for quantifiers is defined as:

$$I \vDash \forall x \ \varphi(x) \text{ iff for all objects } d \in D: I[d/c] \vDash \varphi(c)$$

$$I \vDash \exists x \ \varphi(x) \text{ iff for some object }d \in D: I[d/c] \vDash \varphi(c)$$

where $I[d/c] $ is the interpretation that extends interpretation $I$ by interpreting a new constant symbol $c$ ('new' as in: one that does not already occur in $\varphi(x)$) as object $d$

Third: The logical equivalence of two sentences $\varphi$ and $\psi$ is now defined as:

$$\varphi \Leftrightarrow \psi$$

$$ \text{ iff }$$

$$\text{For any interpretation } I: I \vDash \varphi \text{ iff } I \vDash \psi $$

Using these definitions, we can now prove an equivalence like $\neg \forall x \ \varphi(x) \Leftrightarrow \exists x \ \neg \varphi(x)$:

For any interpretation $I$ with domain $D$:

$$I \vDash \neg \forall x \ \varphi(x)$$

$$\text{iff (by semantics of }\neg )$$

$$\text{not }I \vDash \forall x \ \varphi(x)$$

$$\text{iff (by semantics of }\forall$$

$$\text{not for all objects }d \in D: I[d/c] \vDash \varphi(c)$$

$$\text{iff (by pure logic)}$$

$$\text{for some object }d \in D: \text{ not }I[d/c] \vDash \varphi(c)$$

$$\text{iff (by semantics of }\neg)$$

$$\text{for some object } d \in D: I[d/c] \vDash \neg \varphi(c)$$

$$\text{iff (by semantics of }\exists)$$

$$I \vDash \exists x \ \neg \varphi(x)$$

So, since we have now shown that for any interpretation $I$:

$$I \vDash \neg \forall x \ \varphi(x) \text{ iff } I \vDash \exists x \ \neg \varphi(x)$$

we have that

$$\neg \forall x \ \varphi(x) \Leftrightarrow \exists x \ \neg \varphi(x)$$

I'll leave the proof that:

$$\neg \exists x \ \varphi(x) \Leftrightarrow \forall x \ \neg \varphi(x)$$

to you as an exercise