Negation of Quantified Statements

Question

I was wondering if someone could walk me through how to do this type of question, my teacher didn't really explain it well enough for me to follow along.

QUESTION: Let D = E = {−3, 0, 3, 7}. Write negations for each of the following statements and determine which is true, the given statement or its negation. Explain your answer.

(i) ∀x ∈ D, ∃y ∈ E such that x + y = 0.

(ii) ∃x ∈ D such that ∀y ∈ E, x + y = y.

(iii) ∀x ∈ D, ∃y ∈ E such that xy ≥ y.

(iv) ∃x ∈ D such that ∀y ∈ E, x ≤ y.

Answer 1

Hint

(i) $∀x ∈ D \ ∃y ∈ E \ (x + y = 0)$.

Consider the expression $(x + y = 0)$ : it expresses a "condition" on $x$ and $y$.

We have to "test" it for values in $D = E = \{ −3, 0, 3, 7 \}$, and specifically we have to check if :

for each number $x$ in $D$ there is a number $y$ in $E$ (which il the same as $D$) such that the condition holds (it is satisfied).

The values in $D$ are only four : thus it is easy to check them all.

For $x=-3$ we can choose $y=3$ and $x+y=0$ will hold.

The same for $x=0$ and $x=3$.

For $x=7$, instead, there is no way to choose a value for $y$ in $E$ such that $7+y=0$.

In conclusion, it is not true that : for each number $x$ in $D$ ...

Having proved that the above sentence is FALSE, we can conclude that its negation is TRUE.

To express the negation of a quantified formula, we have to consider that $\lnot \forall$ is the same as $\exists \lnot$ and, in turn, that $\lnot \exists$ is the same as $\forall \lnot$.

Thus, the negation of (i) will be : $\lnot [∀x ∈ D \ ∃y ∈ E \ (x + y = 0)]$, i.e.

$∃x ∈ D \ ∀y ∈ E \ (x + y \ne 0)$.

Final check; the new formula expresses the fact that :

there is an $x$ in $D$ such that, for every $y$ in $E$ it is not true that $(x+y=0)$,

and this is exactly what we have found above with $7$.

Answer 2

Negation of (i):
exists x in D such that for all y in E, x + y /= 0.