properties of injective functions

Theorem 1.

Suppose $A\mathrm{,}B\mathrm{,}C$ are sets and $f\mathrm{:}A\mathrm{\to }B$, $g\mathrm{:}B\mathrm{\to }C$ are injective functions. Then the composition $g\mathrm{\circ }f$ is an injection.

Proof.

Suppose that $(g\circ f)(x)=(g\circ f)(y)$ for some $x,y\in A$. By definition of composition, $g(f(x))=g(f(y))$. Since $g$, is assumed injective, $f(x)=f(y)$. Since $f$ is also assumed injective, $x=y$. Therefore, $(g\circ f)(x)=(g\circ f)(y)$ implies $x=y$, so $g\circ f$ is injective. ∎

Theorem 2.

Suppose $f\mathrm{:}A\mathrm{\to }B$ is an injection, and $C\mathrm{\subseteq }A$. Then the restriction ${f\mathrm{|}}_C\mathrm{:}C\mathrm{\to }B$ is an injection.

Proof.

Suppose $({f|}_C)(x)=({f|}_C)(y)$ for some $x,y\in C$. By definition of restriction, $f(x)=f(y)$. Since $f$ is assumed injective this, in turn, implies that $x=y$. Thus, ${f|}_C$ is also injective. ∎

Theorem 3.

Suppose $A\mathrm{,}B\mathrm{,}C$ are sets and that the functions $f\mathrm{:}A\mathrm{\to }B$ and $g\mathrm{:}B\mathrm{\to }C$ are such that $g\mathrm{\circ }f$ is injective. Then $f$ is injective.

Proof.

(direct proof) Let $x,y\in A$ be such that $f(x)=f(y)$. Then $g(f(x))=g(f(y))$. But as $g\circ f$ is injective, this implies that $x=y$, hence $f$ is also injective. ∎

Proof.

(proof by contradiction) Suppose that $f$ were not injective. Then there would exist $x,y\in A$ such that $f(x)=f(y)$ but $x\ne y$. Composing with $g$, we would then have $g(f(x))=g(f(y))$. However, since $g\circ f$ is assumed injective, this would imply that $x=y$, which contradicts a previous statement. Hence $f$ must be injective. ∎

Theorem 4.

Suppose $f\mathrm{:}A\mathrm{\to }B$ is an injection. Then, for all $C\mathrm{\subseteq }A$, it is the case that $f^{\mathrm{-}\mathrm{1}}\mathit{}\mathrm{(}f\mathit{}\mathrm{(}C\mathrm{)}\mathrm{)}\mathrm{=}C$.

Proof.

It follows from the definition of $f^{-1}$ that $C\subseteq f^{-1}(f(C))$, whether or not $f$ happens to be injective. Hence, all that need to be shown is that $f^{-1}(f(C))\subseteq C$. Assume the contrary. Then there would exist $x\in f^{-1}(f(C))$ such that $x\notin C$. By defintion, $x\in f^{-1}(f(C))$ means $f(x)\in f(C)$, so there exists $y\in A$ such that $f(x)=f(y)$. Since $f$ is injective, one would have $x=y$, which is impossible because $y$ is supposed to belong to $C$ but $x$ is not supposed to belong to $C$. ∎

Theorem 5.

Suppose $f\mathrm{:}A\mathrm{\to }B$ is an injection. Then, for all $C\mathrm{,}D\mathrm{\subseteq }A$, it is the case that $f\mathit{}\mathrm{(}C\mathrm{\cap }D\mathrm{)}\mathrm{=}f\mathit{}\mathrm{(}C\mathrm{)}\mathrm{\cap }f\mathit{}\mathrm{(}D\mathrm{)}$.

Proof.

Whether or not $f$ is injective, one has $f(C\cap D)\subseteq f(C)\cap f(D)$; if $x$ belongs to both $C$ and $D$, then $f(x)$ will clearly belong to both $f(C)$ and $f(D)$. Hence, all that needs to be shown is that $f(C)\cap f(D)\subseteq f(C\cap D)$. Let $x$ be an element of $B$ which belongs to both $f(C)$ and $f(D)$. Then, there exists $y\in C$ such that $f(y)=x$ and $z\in D$ such that $f(z)=x$. Since $f(y)=f(z)$ and $f$ is injective, $y=z$, so $y\in C\cap D$, hence $x\in f(C\cap D)$. ∎

Title	properties of injective functions
Canonical name	PropertiesOfInjectiveFunctions
Date of creation	2013-03-22 16:40:20
Last modified on	2013-03-22 16:40:20
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	22
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 03E20
Classification	msc 03E99