2
$\begingroup$

$\forall x \in U,$ $\exists r\gt0$ such that $\forall y \in \Bbb R, |y-x|\lt r\Rightarrow y \in U$

Negation:

$\exists x \in U,$ $\forall r\gt0$ such that $\forall y \in \Bbb R, |y-x|\lt r\land y \notin U$

So it is that right?

$\endgroup$
  • $\begingroup$ No it isn't — almost, but one flub. Why do you properly switch the $x$ and $r$ quantifiers but not the $y$ quantifier? Here, "such that" is just noise, and in fact you shouldn't even write it, although you pronounce "$\exists r>0$" as "there is $r>0$ such that". You got everything else right though; in particular, you negated the inner, quantifier-free formula correctly. $\endgroup$ – BrianO Feb 24 '16 at 3:43
1
$\begingroup$

The correct one should be

$\exists x \in U,$ such that $\forall r\gt 0$, there exists $ y \in \Bbb R, |y-x|\lt r$ but $y \not\in U$.

$\endgroup$
1
$\begingroup$

I'm going to rewrite your formula as:

$$ \forall x \exists r \forall y : x \in U \to \bigg[ r > 0 \land \big[r \in \Bbb R \to (|y-x|\lt r \to y \in U) \big] \bigg] $$

to better isolate the quantifiers (this follows from the rules around bounded quantifiers). Now, the negation is just:

$$ \neg \Bigg[ \forall x \exists r \forall y : x \in U \to \bigg[ r > 0 \land \big[r \in \Bbb R \to (|y-x|\lt r \to y \in U) \big] \bigg] \Bigg] $$

Using $\forall x \phi \equiv \neg \exists x \neg \phi$ we can "move" the negation past the quantifiers:

$$ \begin{align} \neg \forall x \exists r \forall y & \equiv \\ \exists x \neg \exists r \forall y & \equiv \\ \exists x \forall r \neg \forall y & \equiv \\ \exists x \forall r \exists y \neg \end{align} $$

Now the fun part. Using De Morgan's law and the fact that $\neg (p \to q) \equiv p \land \neg q$:

$$ x \in U \land \neg \bigg[ r > 0 \land \big[r \in \Bbb R \to (|y-x|\lt r \to y \in U) \big] \bigg] $$ $$ x \in U \land \bigg[ \neg (r > 0) \lor \neg \big[r \in \Bbb R \to (|y-x|\lt r \to y \in U) \big] \bigg] $$

$$ x \in U \land \bigg[ \neg (r > 0) \lor \big[r \in \Bbb R \land \neg (|y-x|\lt r \to y \in U) \big] \bigg] $$

$$ x \in U \land \bigg[ \neg (r > 0) \lor \big[r \in \Bbb R \land (|y-x|\lt r \land y \notin U) \big] \bigg] $$

$$ x \in U \land \bigg[ (r > 0) \to \big[r \in \Bbb R \land (|y-x|\lt r \land y \notin U) \big] \bigg] $$

And finally, if we re-bound the quantifiers, we get

$$ \exists x \in U \forall r > 0 \exists y \in \Bbb{R} : |y-x|\lt r \land y \notin U $$

So your solution is almost correct, you just got a quantifier wrong.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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