One-to-One Functions and Onto Functions

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

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.