4
$\begingroup$

So I'm studying for a final- and one of the study questions is "Express (as simply as you can) each of the following sentences without the use of universal quantification:"

a) (∀x)(∃y)(∀z)[P(x,y,z)]

And I'm stuck- the textbook mentions nothing here. At first I thought that maybe it was a tricky set of negations, but I think that would just leave me with (∃x)(∀y)(∃z)[¬P(x,y,z)].

The solution to the problem is apparently ¬(∃x)¬(∃y)¬(∃z) ¬P(x,y,z)

So far the closest I can think is to go from

(∀x)(∃y)(∀z)[P(x,y,z)]            (Start) ¬( (∀x)(∃y)(∀z)[P(x,y,z)] )       (Negate the whole thing) (∃x)(∀y)(∃z)[¬P(x,y,z)]           (Thus swap all quantifiers, negate the inside) ¬( (∃x)(∀y)(∃z)[¬P(x,y,z)] )      (Negate Everything again)               ¬(∃x)(∃y)(¬∃z)[P(x,y,z)]          (Instead of swapping existential quantifiers,                                     negate them. But we still have no negation on y,                                     and we had to negate the negation on the inside?) 

2 Answers 2

4

Perhaps adding many more parentheses will make more sense:

$(\forall x)~(~(\exists y) ~(~(\forall z)~P(x,y,z)~)~)$.

Negate 4 times; this is equivalent to doing nothing to the proposition, so this step is justified.

$\neg\neg\neg\neg(~(\forall x)~(~(\exists y) ~(~(\forall z)~P(x,y,z)~)~)~)$.

Take the first negation inside:

$\neg\neg\neg(~(\exists x)~(~(\forall y) ~(~(\exists z)~\neg P(x,y,z)~)~)~)$.

Take the second negation inside, stop after you've negated the $\forall y$.

$\neg\neg(~(\forall x)~(~(\exists y) ~(~\neg(\exists z)~\neg P(x,y,z)~)~)~)$.

Take the third negation inside, stop after you've negated the $\forall x$.

$\neg(~(\exists x)~(~\neg(\exists y) ~(~\neg(\exists z)~\neg P(x,y,z)~)~)~)$.

This is the answer.

The point is that negating a quantified statement like $(\forall x)P(x)$ always results in a statement like $(\exists x)\neg P(x)$, even if $P(x)$ itself is a quantified statement. So there's no difference in meaning if you go down to the last level of the statement or not.

  • 0
    Ah, Ok. Thanks a ton!2012-12-10
2

Especially knowing the answer, I would try going backwards to "simplify" the solution.

$\neg(\exists x)\neg(\exists y)\neg(\exists z)\neg P(x,y,z)$ $(\forall x)\neg\neg(\exists y)\neg(\exists z)\neg P(x,y,z)$ $(\forall x)(\exists y)\neg(\exists z)\neg P(x,y,z)$ $(\forall x)(\exists y)(\forall z)\neg\neg P(x,y,z)$ $(\forall x)(\exists y)(\forall z) P(x,y,z)$

Run these steps backwards and you have the solution. Alternatively, if you want to repeatedly negate on the outside and bring the negations in, you can do that as well:

$(\forall x)(\exists y)(\forall z) P(x,y,z)$ $\neg\neg(\forall x)(\exists y)(\forall z) P(x,y,z)$ $\neg(\exists x)(\forall y)(\exists z)\neg P(x,y,z)$ $(\forall x)(\exists y)\neg(\exists z)\neg P(x,y,z)$ $\neg\neg(\forall x)(\exists y)\neg(\exists z)\neg P(x,y,z)$ $\neg(\exists x)\neg(\exists y)\neg(\exists z)\neg P(x,y,z)$

  • 0
    It's not so much that $P$ is ignoring negations as that there is a rule $\psi=\neg\neg\psi$ that allows us to cancel and add double negatives, but only if they are adjacent. If I wanted to cancel the negatives in $\neg(\exists z)\neg P$, I would need to apply De Morgan's law to get the negations adjacent: $\neg(\exists z)\neg P=(\forall z)\neg\neg P=(\forall z) P$. Of course, I don't want to do this, and no law says I have to apply any particular rule on any give statement, so statements can "ignore negations" as long as they like.2012-12-10