Negation problem

Forum for the GRE subject test in mathematics.
Post Reply
Hom
Posts: 39
Joined: Sat Oct 01, 2011 3:22 am

Negation problem

Post by Hom » Mon Oct 10, 2011 9:59 pm

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)

blitzer6266
Posts: 61
Joined: Sun Apr 04, 2010 1:08 pm

Re: Negation problem

Post by blitzer6266 » Tue Oct 11, 2011 12:02 am

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.

sogdlk
Posts: 1
Joined: Thu Sep 22, 2011 10:43 pm

Re: Negation problem

Post by sogdlk » Tue Oct 11, 2011 12:31 am

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.

blitzer6266
Posts: 61
Joined: Sun Apr 04, 2010 1:08 pm

Re: Negation problem

Post by blitzer6266 » Tue Oct 11, 2011 2:44 am

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

Hom
Posts: 39
Joined: Sat Oct 01, 2011 3:22 am

Re: Negation problem

Post by Hom » Tue Oct 11, 2011 8:01 am

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



Post Reply