Injection

Grade: A*

This page requires some work to be carried out

Some aspect of this page is incomplete and work is required to finish it
The message provided is:

This needs to be modified (in tandem with Surjection) to:

1. allow surjection/injection/bijection to be seen through the lens of Category Theory. Alec (talk) 21:50, 8 May 2018 (UTC)
2. be linked to cardinality of sets and that Cantor theorem. Alec (talk) 21:50, 8 May 2018 (UTC)

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)\ne f(x_2)]$$ (the contrapositive of the above)

Sometimes an injection is denoted $\rightarrowtail$ (and a surjection $\twoheadrightarrow$ and a bijection is both of these combined (as if super-imposed on top of each other) - there is no LaTeX arrow for this however) - we do not use this convention.

Statements

• Every injection yields a bijection onto its image

Notes

Terminology

• An injective function is sometimes called an embedding
• Just as surjections are called 'onto' an injection may be called 'into' however this is rare and something I frown upon.
  • 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 $f$ maps $A$ onto $B$ so...."

    "But $f$ is an injection so...."

    "As $f$ is a bijection..."

  • I see into used rarely to mean injection, and in fact any function $f:X\rightarrow Y$ being read as $f$ takes $X$ into $Y$ without meaning injection

Properties

• The cardinality of the inverse of an element $$y\in Y$$ 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 $$f^{-1}(y)=\{x\}$$ as the value it contains, writing $f^{-1}(y)=x$)

See also

• Bijection
• Surjection
• Function