2

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

abuchay
  • 602
  • 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. – BrianO Feb 24 '16 at 03:43

2 Answers2

1

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

John
  • 13,204
1

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.

Dan Simon
  • 894