Difference between revisions of "Injection"

Revision as of 18:55, 12 February 2015 (view source) Alec (Talk | contribs) (Created page with "An injective function is 1:1, but not nessasarally onto. For <math>f:X\rightarrow Y</math> every element of <math>X</math> is mapped to an element of <math>Y</...")		Revision as of 12:58, 16 June 2015 (view source) Alec (Talk | contribs) m Newer edit →
Line 1:		Line 1:
	An injective function is 1:1, but not nessasarally [[Surjection|onto]].		An injective function is 1:1, but not nessasarally [[Surjection|onto]].
		+	==Definition==
		+	For a [[Function|function]] <math>f:X\rightarrow Y</math> every element of <math>X</math> is mapped to an element of <math>Y</math> and no two distinct things in <math>X</math> are mapped to the same thing in <math>Y</math>. That is:
		+	* <math>\forall x_1,x_2\in X[f(x_1)=f(x_2)\implies x_1=x_2]</math>
		+	Or equivalently:
		+	* <math>\forall x_1,x_2\in X[x_1\ne x_2\implies f(x_1)=f(x_2)]</math> (the [[Contrapositive|contrapositive]] of the above)
−	For <math>f:X\rightarrow Y</math> every element of <math>X</math> is mapped to an element of <math>Y</math> and no two distinct things in <math>X</math> are mapped to the same thing in <math>Y</math>.	+	==Notes==
		+	The cardinality of the inverse of an element <math>y\in Y</math> may be no more than 1; that is it may be zero, in contrast to a bijection where the cardinality is always 1 (and thus we take the singleton set <math>f^{-1}(y)=\{x\}</math> as the value it contains)
−	For this reason injectivity is often stated as <math>\forall x_1,x_2\in X:f(x_1)=f(x_2)\implies x_1=x_2</math>	+	{{Todo|Find reference - should be easy!}}
−	The cardinality of the inverse of an element <math>y\in Y</math> may be no more than 1; that is it may be zero, in contrast to a bijection where the cardinality is always 1 (and thus we take the singleton set <math>f^{-1}(y)=\{x\}</math> as the value it contains)	+	==See also==
		+	* [[Bijection]]
		+	* [[Surjection]]
		+	* [[Function]]
		+
		+	==References==
		+	<references/>
−	{{Definition}}	+	{{Definition|Set Theory}}

---

Revision as of 12:58, 16 June 2015

An injective function is 1:1, but not nessasarally onto.

Definition

For a function

$$f:X\rightarrow Y$$ every element of $$X$$ is mapped to an element of $$Y$$ and no two distinct things in $$X$$ are mapped to the same thing in $$Y$$ . That is:

• $$\forall x_1,x_2\in X[f(x_1)=f(x_2)\implies x_1=x_2]$$

Or equivalently:

• $$\forall x_1,x_2\in X[x_1\ne x_2\implies f(x_1)=f(x_2)]$$ (the contrapositive of the above)

Notes

The cardinality of the inverse of an element

$$y\in Y$$ may be no more than 1; that is it may be zero, in contrast to a bijection where the cardinality is always 1 (and thus we take the singleton set $$f^{-1}(y)=\{x\}$$ as the value it contains)

---

TODO: Find reference - should be easy!

---

See also

• Bijection
• Surjection
• Function

References