Injection

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

Definition

For a 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 of the above)

Notes

Terminology

• An injective function is sometimes called an embedding
• Just as surjections are called 'onto' an injection may be called 'into'
  • This is French, from "throwing into" referring to the domain, not elements themselves (as any function takes an element into the codomain, it need not be one-to-one)
  • I do not like using the word into but do like onto - I say:

    "But [ilmath]f[/ilmath] maps [ilmath]A[/ilmath] onto [ilmath]B[/ilmath] so...."

    "But [ilmath]f[/ilmath] is an injection so...."

    "As [ilmath]f[/ilmath] is a bijection..."

  • I see into used rarely to mean injection.

---

TODO: Investigate page 6 in Probability and Stochastics, it uses into and see if injectivity matters

---

Properties

• The cardinality of the inverse of an element [math]y\in Y[/math] may be no more than 1
  • Note this means 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, writing [ilmath]f^{-1}(y)=x[/ilmath])

See also

• Bijection
• Surjection
• Function