next up previous contents
Next: Surjections Up: Mappings Previous: Mappings   Contents

Injections

Definition 5.2.1   Let $ A$ and $ B$ be two sets and $ f$ be a mapping from $ A$ to $ B$. The mapping $ f$ is injective (or is one-to-one, or is an injection) if every element of the range $ B$ has at most one pre-image in $ A$ by $ f$.

This means that the following holds:

$\displaystyle \forall x_1 \in A, \;\forall x_2 \in A, \;
 x_1 \neq x_2 \Longrightarrow f(x_1) \neq f(x_2).$    

The contrapositive statement is as follows:

$\displaystyle \forall x_1 \in A, \;\forall x_2 \in A, \;
 f(x_1) = f(x_2) \Longrightarrow x_1 = x_2.$    

The diagram in Figure 3(a) determines an injection and the diagram in Figure 3(b) determines a non injective mapping.

Figure 3: Injection or not.
\begin{figure}
\centering
\mbox{\subfigure[an injection]{\epsfig{file=Injecti...
...ot an injection]{\epsfig{file=NotInjection.eps, height=4cm}}
}
\end{figure}

Example 5.2.2   Let $ f$ be a mapping from $ \mathbb{R}$ to $ \mathbb{R}$ such that for any real $ x$ we have $ f(x)=4x+5$. Take $ x_1 \in \mathbb{R}$ and $ x_2 \in \mathbb{R}$; then we have:

$\displaystyle f(x_1)$ $\displaystyle = f(x_2)$    
$\displaystyle 4x_1+5$ $\displaystyle = 4x_2+5$    
$\displaystyle 4x_1$ $\displaystyle = 4x_2$    
$\displaystyle x_1$ $\displaystyle = x_2.$    

Therefore $ f$ is an injection.

Example 5.2.3   The mapping $ f: \; \mathbb{R}\longrightarrow \mathbb{R}$ such that $ f(x)=x^2$ is not injective, as there exists pairs of distinct reals which have the same square. For instance, $ f(2)=f(-2)$.

Proposition 5.2.4   Let $ A$,$ B$,$ C$ be three sets and let $ f:A \rightarrow B$ and $ g: A \rightarrow C$ be two mappings. If $ f$ and $ g$ are injective, then $ gof$ is an injection.

Proof. Let $ x_1 \in A$ and $ x_2 \in A$ be two elements such that $ gof(x_1)=gof)(x_2)$, i.e. $ g(f(x_1))=g(f(x_2))$. As $ g$ is injective, we have: $ f(x_1)=f(x_2)$, and as $ f$ is injective it follows that $ x_1=x_2$. This proves that $ gof$ is injective. $ \qedsymbol$

Proposition 5.2.5   Let $ A$,$ B$,$ C$ be three sets and let $ f:A \rightarrow B$ and $ g: A \rightarrow C$ be two mappings. If $ gof$ is an injection, then $ f$ is an injection.

Proof. We use a contrapositive argument. Assume that $ f$ is not an injection, i.e. that there exists two different elements $ x_1$ and $ x_2$ in $ A$ such that $ f(x_1)=f(x_2)$. Then $ g(f(x_1))=g(f(x_2))$, i.e. $ g(f(x_1))=g(f(x_2))$. This proves that $ gof$ is not an injection. $ \qedsymbol$


next up previous contents
Next: Surjections Up: Mappings Previous: Mappings   Contents
root 2002-06-10