Can somebody explain quantifier negation equivalence?

Question

I am unsure of how to prove that the following statement of First Order Logic holds:

$$ ¬∀x¬P(x) ↔ ∃xP(x)$$

The proof scheme available to me is that I cannot use axioms (such as De Morgan's Laws) and must instead construct a formal proofs using only the relation and quantifier rules afford to use in First Order / Propositional Logic.

For the same reasoning as above, I also want to know why the following identity holds

$$ ¬∃x¬P(x)↔∀xP(x) $$

(this seems to be related to the above statement and am wondering if there is a related reason as to why this holds and the above statement also holds)

Answer 1

As mentioned in my comment, to prove $A$ ↔ $B$, you need to assume $A$ and derive $B$. And then assume $B$ and derive $A$.

Informal Argument

Assume: ∃xP(x)

• Then for some value $a$, $P(a)$ is true. Now let's consider the claim that for every possible value of $x$, $P(x)$ is not true. This statement is clearly false, as we know that $P(a)$ is true. Therefore, the negation of this statement is true. But that's exactly what we need ¬∀x¬P(x). This says that it is not the case that $P(x)$ is false for all $x$ - which is exactly what we have just shown.

Now assume: ¬∀x¬P(x)

• We want to show that there exists at least one value of $x$ such that $P(x)$ is true. Intuitively, it should be fairly clear why this is the case, as we have it is not the case that $P(x)$ is false for all $x$ and so there must be an $x$ such that $P(x)$ does hold. Usually with statements that seem almost self explanatory, then these are most easily dealt with by looking for a contradiction. So let's assume that there is no value of $x$ such that $P(x)$ is true and work from there.

Formal Proof

More formally, we need to use a proof system. And quite a nice one for this type of argument would be Fitch.

And for the other implication direction, we use the argument:

Answer 2

Are there some details being left out? I think it clears up if you designate which set $x$ is being drawn from. Suppose $x\in N$. Then $\exists x \in N, P(x)$. This conflicts with $\forall x \in N, \lnot P(x)$.

$\lnot (\forall x \in N, \lnot P(x))\iff \exists x\in N, P(x)$.

To negate, exists becomes forall and vice versa, and P gets negated, almost like multiplying by -1.

Answer 3

Assembly $\neg (\exists x(\neg Q(x)))$ is noted differently $(\forall x) Q(x)$(by definition)

Otherwise written $\neg (\exists x(\neg Q(x))) \iff (\forall x) Q(x)$

If we apply this to $\neg P(x)$, we obtain : $$(\forall x) \neg P(x)\iff \neg ((\exists x)\neg \neg P(x))\iff \neg ((\exists x) P(x))$$ And finally what you want.