Page 1 of 1

Negation problem

Posted: Mon Oct 10, 2011 9:59 pm
by Hom
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)

Re: Negation problem

Posted: Tue Oct 11, 2011 12:02 am
by blitzer6266
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.

Re: Negation problem

Posted: Tue Oct 11, 2011 12:31 am
by sogdlk
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.

Re: Negation problem

Posted: Tue Oct 11, 2011 2:44 am
by blitzer6266
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

Re: Negation problem

Posted: Tue Oct 11, 2011 8:01 am
by Hom
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))$$