Injection

Definition

A map $f:X\to Y$ between sets $X$ and $Y$ is an injection (or one-to-one map) iff it maps distinct points to distinct points: $\forall x,x^{\prime }\in X.f(x)=f(x^{\prime })\Rightarrow x=x^{\prime }.$ Equivalently, $f(x)\ne f(y)$ whenever $x\ne y$.

Properties

• Left inverse: $f:X\to Y$ is injective iff there exists $g:Y\to X$ such that $g\circ f={\mathrm{id}}_X$. Such a $g$ is called a left inverse or retraction of $f$. (For $X$ non-empty, constructing $g$ requires the Axiom of Choice.)
• Composition: if $f:X\to Y$ and $g:Y\to Z$ are both injective, then $g\circ f:X\to Z$ is injective.
• Cancellation: $f$ is injective iff it is left-cancellable, i.e. $f\circ g=f\circ h\Rightarrow g=h$ for all $g,h$.
• Categorical: injections between sets are precisely the monomorphisms in Set.

Relationship to Cardinality

An injection $f:X\to Y$ witnesses that $X$ is no larger than $Y$ in the sense of cardinality: $|X|\le |Y|$. By the Schröder-Bernstein theorem, if injections $f:X\to Y$ and $g:Y\to X$ both exist, then there is a bijection between $X$ and $Y$, so $|X|=|Y|$.

Related Concepts

• Surjection
• Bijection
• Monomorphism
• Cardinality
• Schröder-Bernstein theorem
• Axiom of Choice