Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?)
share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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! –  sPease Dec 10 '12 at 7:49
    
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? –  sPease Dec 10 '12 at 7:57
    
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. –  kigen Dec 10 '12 at 8:03
    
Ah, Ok. Thanks a ton! –  sPease Dec 10 '12 at 8:04
add comment

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)$$

share|improve this answer
    
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? –  sPease Dec 10 '12 at 7:16
    
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). –  kigen Dec 10 '12 at 7:19
    
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. –  sPease Dec 10 '12 at 7:22
    
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. –  Mario Carneiro Dec 10 '12 at 7:33
    
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. –  kigen Dec 10 '12 at 7:34
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.