properties of injective functions

Theorem 1.

Suppose $A,B,C$ are sets and $f\colon A\to B$, $g\colon B\to C$ are injective functions. Then the composition $g\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\colon A\to B$ is an injection, and $C\subseteq A$. Then the restriction $f|_{C}\colon C\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,B,C$ are sets and that the functions $f\colon A\to B$ and $g\colon B\to C$ are such that $g\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.

() Suppose that $f$ were not injective. Then there would exist $x,y\in A$ such that $f(x)=f(y)$ but $x\neq 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\colon A\to B$ is an injection. Then, for all $C\subseteq A$, it is the case that $f^{-1}(f(C))=C$.11In this equation, the symbols “$f$” and “$f^{-1}$” as applied to sets denote the direct image and the inverse image, respectively

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\colon A\to B$ is an injection. Then, for all $C,D\subseteq A$, it is the case that $f(C\cap D)=f(C)\cap f(D)$.

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 PropertiesOfInjectiveFunctions 2013-03-22 16:40:20 2013-03-22 16:40:20 rspuzio (6075) rspuzio (6075) 22 rspuzio (6075) Theorem msc 03E20 msc 03E99