One-to-One Functions and Onto Functions

One-to-One Functions and Onto Functions


Master of Science in Mathematics
Lecture Notes. Accessed on: 2019-10-21 18:06:30

One-to-one and Onto 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.

5/5 (1 Review)

Leave a Comment

Scroll to Top