# Negating injection function

• October 30th 2010, 01: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???
• October 30th 2010, 02:02 PM
Plato
The negation of $f$ being injective is $\left( {\exists x} \right)\left( {\exists y} \right)\left[ {f(x) = f(y) \wedge \left( {x \ne y} \right)} \right]$.
• October 30th 2010, 03:01 PM
chr91
Quote:

Originally Posted by Plato
The negation of $f$ being injective is $\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
• October 30th 2010, 03:11 PM
Plato
Actually it more general. The negation:
$\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]$