Negate the following statements formally so that no negation symbol remains:
(i) $ \ \ \forall y \exists x (y>0 \to x \leq 0 ) \ $
(ii) $ \ \forall x \forall y \exists z(x <z \leq y ) \ $
Answer:
My approach is as follows:
(i)
The negation of the statements in (i) without negation symbol is
$ \exists y \ \ s.t. \ \ \forall x (x>0 \to y \leq 0) \ $
(ii)
Given
$ \forall x \forall y \ \exists z \ ( x <z \leq y ) \ \\\sim \forall x \forall y \ \exists z \ ( x <z \wedge z \leq y ) $
The negation is given as
$ \exists x \exists y \ \ s.t. \ \ \forall z \ ( x \geq z \wedge z > y ) $
Am I true ?
Is there any help ?
Best Answer
For both problems we start by using $\neg(\forall xP(x))\equiv\exists x(\neg P(x))$ and then $\neg(\exists xP(x))\equiv\forall x(\neg P(x))$.
(i) Negate $\forall y\exists x(y>0\to x\leq 0)$.
First we get: $$\exists y\forall x(\neg(y>0\to x\leq 0))$$ Next we note that $A\to B\equiv \neg A\vee B$: $$\exists y\forall x(\neg(y<0\vee x\leq 0))$$ Then apply DeMorgan's Law to finish: $$\exists y\forall x(y>0\wedge x\geq 0)$$
(ii) Negate $\forall x\forall y\exists z(x<z\leq y)$. First we get: $$\exists x\exists y\forall z(\neg(x<z\leq y))$$ Split the compound inequality: $$\exists x\exists y\forall z(\neg(x<z\wedge z\leq y))$$ Then apply DeMorgan's Law to finish: $$\exists x\exists y\forall z(x>z\vee z\geq y)$$