It always puzzles me.
For example, given R: There exist x1,x2 ∈X such that x1 ≠x2 and f(x1)=f(x2).
What is not R?
For every x1,x2 ∈X such that x1 ≠x2 and f(x1)≠f(x2) ?
or
For every x1,x2 ∈X such that x1 =x2 and f(x1)≠f(x2) ?
Any suggestion for such kind of problem? (like which part needs to change and which part doesn't)
Negation problem

 Posts: 61
 Joined: Sun Apr 04, 2010 1:08 pm
Re: Negation problem
Maybe think of it this way... Not R would be
There does not exist an x1, x2 in X such that x1=/=x2 and f(x1) = f(x2)
This is the same as saying
For every x1, x2 in X such that x1=/=x2, f(x1) =/= f(x2)
There are probably other ways to translate it, but your 2 options don't make sense, at least how they are written in English.
There does not exist an x1, x2 in X such that x1=/=x2 and f(x1) = f(x2)
This is the same as saying
For every x1, x2 in X such that x1=/=x2, f(x1) =/= f(x2)
There are probably other ways to translate it, but your 2 options don't make sense, at least how they are written in English.
Re: Negation problem
Could it be:
For every x1 and x2 that belongs to X, x1 = x2 or f(x1) is not equal to f(x2)
I believe AND becomes OR when negating a statement.
For every x1 and x2 that belongs to X, x1 = x2 or f(x1) is not equal to f(x2)
I believe AND becomes OR when negating a statement.

 Posts: 61
 Joined: Sun Apr 04, 2010 1:08 pm
Re: Negation problem
That's right...
If you want to be formal, R can be written as
$$\exists x_1 \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
The main trick is that $$\lnot \exists \lnot$$ equals $$\forall$$ and vice versa
so not R is
$$\lnot \exists x_1 \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
$$\forall x_1 \lnot \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
$$\forall x_1 \forall x_2 \lnot (\lnot(x_1=x_2)\wedge (f(x_1) =f(x_2)))$$
$$\forall x_1 \forall x_2 (x_1=x_2)\lor \lnot (f(x_1) =f(x_2))$$
where each of the lines is equivalent to the one above it and the last step is the de morgan rule mentioned above
If you want to be formal, R can be written as
$$\exists x_1 \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
The main trick is that $$\lnot \exists \lnot$$ equals $$\forall$$ and vice versa
so not R is
$$\lnot \exists x_1 \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
$$\forall x_1 \lnot \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
$$\forall x_1 \forall x_2 \lnot (\lnot(x_1=x_2)\wedge (f(x_1) =f(x_2)))$$
$$\forall x_1 \forall x_2 (x_1=x_2)\lor \lnot (f(x_1) =f(x_2))$$
where each of the lines is equivalent to the one above it and the last step is the de morgan rule mentioned above
Re: Negation problem
blitzer6266 wrote:That's right...
If you want to be formal, R can be written as
$$\exists x_1 \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
The main trick is that $$\lnot \exists \lnot$$ equals $$\forall$$ and vice versa
so not R is
$$\lnot \exists x_1 \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
$$\forall x_1 \lnot \exists x_2 \lnot(x_1=x_2)\wedge (f(x_1) =f(x_2))$$
$$\forall x_1 \forall x_2 \lnot (\lnot(x_1=x_2)\wedge (f(x_1) =f(x_2)))$$
$$\forall x_1 \forall x_2 (x_1=x_2)\lor \lnot (f(x_1) =f(x_2))$$
where each of the lines is equivalent to the one above it and the last step is the de morgan rule mentioned above
wow. Thank you very much for the detailed explanation. That's quite helpful.
I added another step below to convert ~pVq to p>q so that it matches the statement perfectly.
$$\forall x_1 \forall x_2 \lnot (x_1=x_2) \to \lnot (f(x_1) =f(x_2))$$