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.

The negation of :

∃x ∀y (P(x,y) ⇒ Q(x,y))

is:

∀x ∃y ¬(P(x,y) ⇒ Q(x,y))

But I am not sure about the last part (¬(...)). Is that negation well done, in the sense that couldn't be done more concisely?

share|improve this question
5  
You mean by replacing it with $P(x,y)\wedge\neg Q(x,y)$? –  Jonas Meyer Jan 26 '11 at 15:46
    
That's it. Thank you. –  Nerian Jan 26 '11 at 15:50
3  
@Myself: No, that is the contrapositive to P implies Q, and they are equivalent, not negations of one another. –  hardmath Jan 26 '11 at 16:18
1  
@Nerian: The negation of "for all $\epsilon\gt 0$, $P(\epsilon)$" is "there exists $\epsilon\gt0$ such that $\neg P(\epsilon)$." Just "for all $\epsilon\gt0$" isn't a statement that can be negated. –  Jonas Meyer Jan 26 '11 at 16:36
1  
@Nerian: Typically $(\forall\epsilon>0)P(\epsilon)$ is written $(\forall\epsilon)(\epsilon>0\to P(\epsilon))$, while $(\exists\epsilon>0)P(\epsilon)$ is written $(\exists\epsilon)(\epsilon>0\land P(\epsilon))$. Now since the negation of $P\to Q$ is $P\land\lnot Q$, the negation of $(\forall\epsilon>0)P(\epsilon)$ becomes $(\exists\epsilon>0)(\lnot P(\epsilon))$. Therefore the negation of the statement you wrote would be $\exists\epsilon>0\forall n_0\exists n\geq n_0 (|x_n-a|\geq\epsilon)$. –  Apostolos Jan 26 '11 at 16:56
show 5 more comments

1 Answer

up vote 6 down vote accepted

The best way to approach these problems is to go step by step by the definition and tautologies that you know. For example:

  • $\lnot \exists x\varphi \iff \forall x\lnot\varphi$, and
  • $\lnot\forall x\varphi\iff \exists x\lnot\varphi$

Both useful in the case of the quantifiers, we want to negate an implication we use two facts, $x\rightarrow y \iff \lnot x\lor y$ and DeMorgan's law. Together we have:

$\lnot(x\rightarrow y)\iff \lnot(\lnot x\lor y) \iff x\land\lnot y$.

Now we proceed to negate the sentence at hand: $$ \begin{align} \lnot ( \exists x\forall y\ (P(x,y)\rightarrow Q(x,y)) &\iff \forall x \lnot (\forall y\ (P(x,y)\rightarrow Q(x,y)) \\ &\iff \forall x \exists y\ \lnot(P(x,y)\rightarrow Q(x,y)) \\ &\iff \forall x \exists y\ \lnot(\lnot P(x,y)\lor Q(x,y)) \\ &\iff \forall x \exists y\ (P(x,y)\land\lnot Q(x,y)) \end{align}$$

share|improve this answer
add comment

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.