# Elementary logic. Negation

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?

-
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

• $\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}