3
$\begingroup$

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?

  • 5
    You mean by replacing it with $P(x,y)\wedge\neg Q(x,y)$?2011-01-26
  • 0
    That's it. Thank you.2011-01-26
  • 0
    Or $\lnot Q \implies \lnot P$.2011-01-26
  • 3
    @Myself: No, that is the contrapositive to P implies Q, and they are equivalent, not negations of one another.2011-01-26
  • 0
    If I have: ∀ε>0 The negation is just : ∃ε>0 I don't have to negate te comparison, right?2011-01-26
  • 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.2011-01-26
  • 0
    @Jonas: Oh, sure. The whole statement is: ∀ε>0 ∃n0 ∀n≥n0 (|xn−a|<ε).2011-01-26
  • 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)$.2011-01-26
  • 0
    @hardmath: You're right obviously. This just isn't my day.2011-01-26
  • 0
    @Myself: No biggie. If I were you, I could say I wasn't Myself today!2011-01-26

1 Answers 1

6

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