# Negating injection function

• Oct 30th 2010, 12:47 PM
chr91
Negating injection function
A function f: X to Y is injective if for all x, x' E X f(x) = f(x') implies x = x'

I attempted it and got:

There exists x, x' E X f(x) not equal to f(x') implies x not equal to x'

I'm confident I have got the quantifiers correct, but not the next part???
• Oct 30th 2010, 01:02 PM
Plato
The negation of $\displaystyle f$ being injective is $\displaystyle \left( {\exists x} \right)\left( {\exists y} \right)\left[ {f(x) = f(y) \wedge \left( {x \ne y} \right)} \right]$.
• Oct 30th 2010, 02:01 PM
chr91
Quote:

Originally Posted by Plato
The negation of $\displaystyle f$ being injective is $\displaystyle \left( {\exists x} \right)\left( {\exists y} \right)\left[ {f(x) = f(y) \wedge \left( {x \ne y} \right)} \right]$.

Oh I see

Because x implies y negated is Not (x implies y)

Using the implication rule: x and not y
• Oct 30th 2010, 02:11 PM
Plato
Actually it more general. The negation:
$\displaystyle \neg \left( {\forall x} \right)\left[ {P(x) \Rightarrow Q(x)} \right] \equiv \left( {\exists x} \right)\left[ {P(x) \wedge \neg Q(x)} \right]$