One-to-One Functions and Onto Functions

In this article, I cover one-to-one functions and onto functions. One-to-one functions are often called injective, and onto functions are called surjective. I worked through the proofs (in detail) of several basic properties for these special types of functions.

Injective Functions

Definition. Let $X$ and $Y$ be sets. A function $f:X\to Y$ is called injective if  $$ \forall x_1,x_2\in X, f(x_1)=f(x_2)\implies x_1=x_2. $$

Theorem. Let $f:X\to Y$ be a function.  If $f$ is injective and $A\subseteq X$, then $f|_A$ is injective.

Proof. Let $x_1, x_2\in A$.  Then  $$ f|_A(x_1)=f|_A(x_2)  \Longrightarrow f(x_1)=f(x_2) \Longrightarrow x_1=x_2 $$ shows that $f|_A$ is injective. 

Theorem. Let $f:X\to Y$ be a function.  Then $f$ is injective if and only if $$f(A_1\cap A_2) = f(A_1)\cap f(A_2)$$ for all $A_1, A_2\subseteq X$.

Proof. Assume $f$ is injective.  It suffices to show $f(A_1)\cap f(A_2)\subseteq f(A_1\cap A_2)$ for all $A_1, A_2\subseteq X$.  Let $A_1, A_2\subseteq X$.  Then \begin{align*} & y\in f(A_1)\cap f(A_2)  \Longleftrightarrow y\in f(A_1)\land y\in f(A_2)  \\& \qquad \Longleftrightarrow [\exists x\in A_1, y=f(x)] \land [\exists z\in A_2, y=f(z)] \\& \qquad \Longrightarrow \exists x\in A_1, \exists z\in A_2, f(x)=y=f(z) \\& \qquad \Longrightarrow \exists x\in A_1, \exists z\in A_2, x=z, y=f(x)  \\& \qquad \Longrightarrow \exists x\in A_1\cap A_2, y=f(x) \Longrightarrow  y\in f(A_1\cap A_2)  \end{align*} Conversely, assume $f(A_1\cap A_2)=f(A_1)\cap f(A_2)$, for all $A_1, A_2\subseteq X$.  Let $x_1, x_2\in X$ and assume $x_1\neq x_2$.  Then   $\{x_1\}\cap \{x_2\}=\emptyset$.  Then  $$ f(\{x_1\}\cap \{x_2\})=\emptyset=f(\{x_1\})\cap f(\{x_2\}).$$ If $f(x_1)=f(x_2)$, then $f(x_2)\in f(\{x_1\})$ and $f(x_1)\in f(\{x_2\})$, and so $f(\{x_1\})\cap f(\{x_2\}) \neq \emptyset$.  Thus, $f(x_1)\neq f(x_2)$ and so $f$ is injective.

Theorem. Let $f:X\to Y$ be a function.  Then $f$ is injective if and only if $f(A_2\setminus A_1)=f(A_2)\setminus f(A_1)$ for all $A_1, A_2\subseteq X$.

Proof. Assume $f$ is injective.  Let $A_1, A_2\subseteq X$.  It suffices to show $f(A_2\setminus A_1)\subseteq f(A_2)\setminus f(A_1)$.  Assume $y\in f(A_2\setminus A_1)$.  Then $y=f(x)$ for some $x\in A_2\setminus A_1$.  Thus, $x\in A_2$ and so $y\in f(A_2)$.  We claim $y\not\in f(A_1)$.  Suppose $y\in f(A_1)$.  Then, there exists $z\in A_1$ such that $f(z)=y$. Since $f$ is injective, $x=z$. However, $x\not\in A_1$, and so the claim follows. Thus, $y\in f(A_2)\setminus f(A_1)$ as desired.  Conversely, assume $f(A_2\setminus A_1)=f(A_2)\setminus f(A_1)$ holds for all $A_1, A_2\in X$. Let $x_1, x_2\in X$ and assume $x_1\neq x_2$.  Then $\{x_2\}\setminus \{x_1\}=\{x_2\}$ and so  $$f(\{x_2\}\setminus \{x_1\})=f(\{x_2\})=f(\{x_2\})\setminus f(\{x_1\}).  $$ If $f(x_1)=f(x_2)$, then $f(\{x_2\})\setminus f(\{x_1\})=\emptyset$, contrary to $f(\{x_2\})\setminus f(\{x_1\})=f(\{x_2\})$.  Thus $f(x_1)\neq f(x_2)$ and so $f$ is injective.

Theorem. Let $f:X\to Y$ be a function. Then  $f$ is injective if and only if  $f(A_1)\cap f(A_2)=\emptyset $ for all $A_1, A_2\subseteq X$ such that $A_1\cap A_2=\emptyset$. 

Proof. Assume $f$ is injective.  Let $A_1, A_2\in X$ with $A_1\cap A_2=\emptyset$. Assume $y\in f(A_1)\cap f(A_2)$.  Then there exists $x_1\in A_1$ and $x_2\in A_2$ such that $y=f(x_1)$ and $y=f(x_2)$. Since $f$ is injective, $x_1=x_2$.  Thus, $A_1\cap A_2\neq \emptyset$ contrary to hypothesis. Thus, $f(A_1)\cap f(A_2)$ is empty.  Conversely, assume $f(A_1)\cap f(A_2)=\emptyset$ for all $A_1, A_2\subseteq X$ with $A_1\cap A_2=\emptyset$.  Let $x_1, x_2\in X$ and assume $x_1\neq x_2$.  Then $\{x_1\}\cap \{x_2\}=\emptyset$.  By hypothesis, $f(\{x_1\})\cap f(\{x_2\})=\emptyset$. Thus $f(x_1)\neq f(x_2)$ and so $f$ is injective. 

Theorem. Let $f:X\to Y$ be a function.  Then $f$ is injective if and only if $A=f^{-1}(f(A))$ for all $A\subseteq X$.

Proof. Assume $f$ is injective.  Let $A\subseteq X$.  It suffices to show $f^{-1}(f(A))$.  Let $x\in f^{-1}(f(A))$. Then $f(x)\in f(A)$.  Then there exists $x_1\in A$ such that $f(x_1)=f(x)$.  Since $f$ is injective, $x_1=x$ and so $x\in A$. Conversely, assume $A=f^{-1}(f(A))$ for all $A\subseteq X$. Let $x_1, x_2\in X$.  Assume $f(x)1=f(x_2)$.  Then  $$ \{x_1\}=f^{-1}(f(\{x_1\}))=f^{-1}(f(\{x_2\}))=\{x_2\} $$ implies $x_1=x_2$ and so $f$ is injective.

Surjective Functions

Definition. Let $X$ and $Y$ be sets. A function $f:X\to Y$ is called surjective if  $$ \forall y\in Y, \exists x\in X, y=f(x). $$

Theorem. Let $f:X\to Y$ be a function.  If $f$ is surjective and $A\supseteq X$, then $f|^A$ is surjective.

Proof. Let $t\in Y$. Since $f$ is surjective there exists $x\in X$ such that $f(x)=y$. Since $X\subseteq A$, $x\in A$ and so $f(x)=y$ with $x\in A$ implies $f|^A$ is surjective.

Theorem. Let $f:X\to Y$ be a function.  Then $f$ is surjective if and only if $B=f(f^{-1}(B))$ for all $B\subseteq Y$.

Proof. Assume $f$ is surjective. It suffices to show $B\subseteq f(f^{-1}(B))$.  Let $y\in B$.  Since $f$ is surjective. there exists $x\in X$ such that $y=f(x)$. Since $f(x)\in B$ we have $x\in f^{-1}(B)$. It follows $y=f(x)\in f(f^{-1}(B))$.  Conversely, assume $B=f(f^{-1}(B))$ for all $B\subseteq Y$.  Since $\{y\}=f(f^{-1}(\{y\}))$, it follows $y=f(x)$ for some $x\in f^{-1}(\{y\})$.  Let $y\in Y$. Thus, $f$ is surjective. 

Theorem. If $f:X\rightarrow P(X)$ is a function, then $f$ is not surjective.

Proof. Let $A=\{x\in X : x\notin f(x)\}$. Assume for a contradiction that $f$ is onto. Then there exists $x\in X$ such that $f(x)=A$.  Consider both cases $x\in f(x)$ and $x\not\in f(x)$: \begin{align*} & x\in f(x) \implies x\in A \implies x\not\in f(x)  \implies\Longleftarrow \\ & x\notin f(x) \implies x\in A=f(x) \implies x\not\in f(x)  \implies\Longleftarrow \end{align*} Thus, $x$ can not exist with $f(x)=A$. Therefore, no $f:X\rightarrow P(X)$ is onto.

David A. Smith at Dave4Math

David Smith (Dave) has a B.S. and M.S. in Mathematics and has enjoyed teaching precalculus, calculus, linear algebra, and number theory at both the junior college and university levels for over 20 years. David is the founder and CEO of Dave4Math.