Negation problem

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

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

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

[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

[Hom]

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