# Negation of injectivity

I'm having some problems understanding the negation of injectivity.

Take the function $f: \mathbb{R} \rightarrow \mathbb{R}$ given by $f(x) = x^2$. The formal definition of injectivity is $f(a)=f(b) \implies a = b$. Therefore the function $f(x)$ is not injective because $-1 \neq 1$ while $f(-1)=f(1)=1$.

But when I try to specify the negation of the statement "f is injective", I run into problems. I know that the negation of "P implies Q" is "P but not Q" so the formal definition of non-injectivity should be $f(a)=f(b) \implies a\neq b$, right? The problem is this statement doesn't hold for the function $f(x)=x^2$, because $f(1) = f(1)$ while it's not true that $1 \neq 1$.

What am I doing wrong?

-
The logical equivalence is $$P\implies Q \iff \neg Q \implies \neg P$$ You are doing the following: $$f(a)=f(b) \implies a\neq b$$ which is wrong, because first it should be that $a\neq b$ implies something and secondly because you did not negate $f(a) = f(b)$. – Ale Jan 12 at 12:50
I wasn't looking for the logical equivalence, but for the logical negation. – Jim Daniël Teunis Jan 12 at 12:51
You're missing a quantifier: implication ($P\implies Q$) holds for all $a$ and $b$, so the negation is 'there exists (at least one) pair $(a,b)$ such that $(P\land\lnot Q)$'. – CiaPan Jan 12 at 12:52
There is no "but" in logic, the negation of "P implies Q" is "P and not Q". – fkraiem Jan 12 at 13:27
Your problem is that you have translated "but" as $\implies$ when it should be $\land\lnot$. – MJD Jan 12 at 13:32

By definition, $f$ is injective if and only if

$$\forall(a,b) \in \mathbb{R}^2: f(a)=f(b) \implies a=b.$$

The negation of this statement is

$$\exists (a,b) \in \mathbb{R}^2: f(a)=f(b) \quad \text{and} \quad a \neq b.$$

$f(x)=x^2$ is not injective because there exists the pair $(-1,1)$ such that $(-1)^2 = 1^2$ but $-1 \neq 1.$

-
Thanks, I forgot about the quantifiers.. :) – Jim Daniël Teunis Jan 12 at 12:50
I think you miss where are $a,b$ taken from. E.g. if $f: A \to B$, then you should say $a,b\in A$. In this case, $a, b \in \mathbb R$. – JnxF Jan 12 at 13:17
@JnxF Edited, though the context was not ambiguous – Paolo Franchi Jan 12 at 13:21
@JimDaniëlTeunis I think your actual mistake was not the quantifiers, but rather your translation of the English description "$f(a) = f(b)$ but not $a = b$" into the logical statement $f(a) = f(b) \implies a \ne b$ instead of $f(a) = f(b) \land a \ne b$. – Daniel Wagner Jan 12 at 20:15
You are right, but it was the quantifiers that caused the confusion for me. I got stuck because I thought the statement would have to be true for all a,b which (in retrospect) doesn't make sense. Thanks for explaining it so clearly though :) – Jim Daniël Teunis Jan 13 at 15:27

There exists $a,b \in \mathbb{R}$ such that $f(a) = f(b)$ but $a\neq b$, is a negation of injectivity.

-

"P but not Q" so the formal definition of non-injectivity should be $f(a)=f(b) \implies a\neq b$, right?

Wrong, but close. You said "P but not Q" (which really means "P and not Q") and then you wrote the equivalent of "P implies not Q". These are different.

You also have to be careful how to take negation inside a quantifier. The definition of injectivity really is "for all $x,y$ something", which is negated as "there exists $x,y$ for which NOT something". Substituting "P implies Q" for "something", and using the rule for negating an implication, we get that the negation of "for $x,y$ P implies Q" is "there exists $x,y$ such that P and not Q".

-
Great answer, thank you :) – Jim Daniël Teunis Jan 13 at 15:28

As you notice the negation of $P$ implies $Q$ is $P$ but not $Q$. However this made formal for injectivety should be stated $f(a)=f(b) \wedge a\neq b$ i.e. both statement $f(a)=f(b)$ and $a\neq b$ hold, for some numbers $a$ and $b$.

-