Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
2  
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
3  
I wasn't looking for the logical equivalence, but for the logical negation. – Jim Daniël Teunis Jan 12 at 12:51
5  
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
4  
There is no "but" in logic, the negation of "P implies Q" is "P and not Q". – fkraiem Jan 12 at 13:27
3  
Your problem is that you have translated "but" as $\implies$ when it should be $\land\lnot$. – MJD Jan 12 at 13:32
up vote 13 down vote accepted

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

share|cite|improve this answer
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
2  
@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.

share|cite|improve this answer

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

share|cite|improve this answer
    
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$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.