Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The negation of :

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


∀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|cite|improve this question
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
@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
@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
@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
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|cite|improve this answer

Your Answer


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.