Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

~(∃ 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.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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$.)

Your (incorrectly) negated statement is read:

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.