Negating a quantified statement (no negator to move?!)

Question

Introduction to Languages and The Theory of Computation (click to read the content of the book)

(This is not an exercise, but actual content from the blook explaining quantified statements)

The general procedure for negating a quantified statement is to reverse the quantifier (change ∀ to ∃, and vice versa) and move the negation inside the quantifier. ¬(∀x(P (x))) is the same as ∃x(¬P (x)), and ¬(∃x(P (x))) is the same as ∀x(¬P (x)). In order to negate a statement with several nested quantifiers, such as

1

$$∀x(∃y(∀z(P (x, y, z)))) $$

apply the general rule three times, moving from the outside in, so that the final result is

2

$$∃x(∀y(∃z(¬P (x, y, z))))$$

---

I don't get how they applied the general rule three times. More specifically, I don't get what you are supposed to do when there isn't a negator to move.

They write that you are supposed to "flip the ∃ and ∀" and move the negator, but what if there isn't a negator in the first place as is the case with statement #1?

Answer 1

You're considering a method on how to negate propositions. Negating a proposition is formally just adding a $\lnot$-symbol in front of the whole proposition. That is, if we have a statement $A$, the negation would be $\lnot A$.

So your textbook is talking about negating $\forall x \exists y \forall z P(x,y,z)$. The negation then is $\lnot (\forall x \exists y \forall z P(x,y,z))$, which can be converted to another form $\exists x \forall y \exists z \lnot P(x,y,z)$ by logical rules.

(Consider for example the propositions "All apples are green" $\forall x P(x)$. If you negate this proposition you get "Not all apples are green" which is equivalent to "There is an apple that is not green". Formally: $\lnot \forall x P(x)\Leftrightarrow \exists x \lnot P(x)$)

If you don't want to negate a proposition, then you don't have to add a $\lnot$ and you don't have to swap quantifiers.

Answer 2

\begin{align}\neg(\forall x,\exists y,\forall z, P(x,y,z))&=\exists x,\neg(\exists y,\forall z, P(x,y,z))\\&=\exists x,\forall y,\neg(\forall z,P(x,y,z))\\&=\exists x,\forall y,\exists z,\neg P(x,y,z)\end{align}

Answer 3

Another way to look at it:

1. $\neg \forall x: \exists y: \forall z: P(x,y,z) \space \space$ (initial premise)

2. $\neg \neg \exists x: \neg \exists y: \forall z: P(x,y,z) \space \space$ (replaced "$\forall x:$" with "$\neg \exists x: \neg $")

3. $\neg \neg \exists x: \neg \neg \forall y: \neg \forall z: P(x,y,z) \space \space$ (replaced "$\exists y:$" with "$\neg \forall y: \neg $")

4. $\neg \neg \exists x: \neg \neg \forall y: \neg \neg \exists z: \neg P(x,y,z)\space \space$ (replaced "$\forall z:$" with "$\neg \exists z: \neg $")

5. $\exists x: \forall y: \exists z: \neg P(x,y,z)\space \space$ (removed each "$\neg \neg$")