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
    Ohh. Well, that makes a lot more sense. Our textbook basically says that something like (∀x) (∃y) (∀z) P(x,y,z) is thought of as (∀x),(∃y),(∀z),P(x,y,z). Not that they nest. Thank a ton, everyone!2012-12-10
  • 0
    OK, I just caught one last thing- and I THINK I know the reason why, but I would rather make sure. Why is it four negations instead of three? three negations would end us with ( (∃x) ( ¬(∃y) ( ¬(∃z) ¬P(x,y,z) ) ) ). Is the reason just because it's mod two, and thus cancels out in its entirety? (E.G. when rearranging things like this, you can only do negations in twos?) Basically, long story short, why do we need that last negation?2012-12-10
  • 0
    We only need it because we want our original statement and our final statement to be equivalent statements. If we negated three times then our resulting statement would be the negation of our original statement. If all we wanted was to apply negations until we didn't have universal quantifiers, then three would be sufficient, but if we want to make sure the statements are equivalent then we tack on the fourth one.2012-12-10
  • 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
    Would you mind elaborating a bit more on what's going on here? I'm missing something. I'll use your second example. It looks like you're double negating the entire thing- the first negation (third line) I follow, and then you negate again and I'm confused at line 4. Why does z not change? Why is p still negated?2012-12-10
  • 0
    In the first part he's just working backwards from the solution you have, so don't worry about that. In the second half, he starts with your original statement, then starts negating it consecutively. Then he takes the negations inside one at a time. The point is knowing when you stop "cascading" the negations down, you don't need to bring every negation down to P(x,y,z).2012-12-10
  • 0
    Is there any resources I could look at on this then? My textbook (is very bad) only mentions negations in an absolute sense- in that something like line 2 to line 3 is possible. It doesn't indicated that you can stop cascading, or anything of the sort.2012-12-10
  • 0
    It is an application of De Morgan's laws for quantifiers that $\neg(\exists x)\psi=(\forall x)\neg\psi$ and $\neg(\forall x)\psi=(\exists x)\neg\psi$ for any statement $\psi$. When you "cascade" negations through multiple quantifiers, you are repeatedly applying these rules. There is nothing saying you need to apply them so many times, though: you can stop whenever you like.2012-12-10
  • 0
    Most likely no textbook will tell you that you can stop cascading, 1) because this never really comes up in real math and 2) it's really part of the proposition that talks about negation of quantifiers.2012-12-10
  • 0
    OK, so I think I'm understanding a bit better, but there's some things confusing me- first off, should I assume that line two is ¬¬[(∀x)(∃y)(∀z)P(x,y,z)], and line three is then ¬[(∃x)(∀y)(∃z)¬P(x,y,z)]? This makes sense, and on line four it looks like he swapped the quantifiers- except for z, letting the negation 'hang'. Why, however, does P not cancel out and become un-negated? And then in line 5, I'm reading it as ¬¬[(∀x)(∃y)¬(∃z)¬P(x,y,z)], which seems to follow sense and work (minus how P continues to ignore negations)... but the second negation is somehow only attached to x.2012-12-10
  • 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