# Could someone verify that I got this negation correctly in Discrete Mathematics?

~(∃ x ∈ Z | ∀ y ∈ Z, y/x ∈ Z)

= ∀ x ∈ Z | ∀ y ∈ Z, y/x ∈ Z

I'm just not 100% sure. I'm under the impression that if expressions following "such that" are not included in the quantifier they do not get negated. Is that correct?

And if that is true, how does one read the bottom expression? It seems bizarre to me.

-

Hint:

Assuming Z refers to the integers, your original un-negated statement reads:

There exists an integer $x$ so that for any integer $y$, the value of $\frac{y}{x}$ is an integer.

(It's referring to the integers $1$ and $−1$.)

For any integers $x$ and $y$, the value of $\frac{y}{x}$ is an integer.

Correctly negated, it should read:

For any integer $x$, there is an integer $y$ so that $\frac{y}{x}$ is not an integer.

-
Thanks for the beautiful explanation. I understand it conceptually (like an "English" translation of negation, if you will) but mathematically converting is where I'm having trouble. Could you see the comment on the other answer? –  Doug Smith Sep 25 '12 at 21:37

The negation is

$$\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z} \,\,\,\,\,\, \frac{y}{x} \notin \mathbb{Z}$$

When you have a statement of the form

$$\forall \exists \exists \forall \exists \cdots P$$

that is, a bunch of quantifiers before a quantifier-free formula, you negate by turning $\forall$ into $\exists$ and vice versa, and then negating $P$ to get

$$\neg (\forall \exists \exists \forall \exists \cdots P) = \exists \forall \forall \exists \forall \cdots \neg P$$

-
Okay, but how does the such that (|) come into play? In the original equation there is one expression before the | and in the negation there is two. What's the conversion rule for that? –  Doug Smith Sep 25 '12 at 21:36
@DougSmith: The "such that" is just there to make it read nicely in English. Most people leave it out, I believe. For example, I would have written $\exists x \in \mathbb{Z} \; \forall y \in \mathbb{Z} \; \frac{y}{x} \in \mathbb{Z}$ for the original expression. –  Snowball Sep 25 '12 at 21:41