Graphs and Functions

A graph $G$ from a set $A$ to another set $B$ is a subset $R\subseteq A\times B$. If $A=B$ then $G$ is called a relation in $A$. The inverse of a graph $G\subseteq A\times B$ is defined by $G^{-1}=\{(y,x):(x,y)\in G\}\subseteq B\times A$.

A function $f$ from $A$ to $B$ is a graph $f\subseteq A\times B$ such that

F1. For any $x\in A$ there exists $y\in B$ such that $(x,y)\in f$.

F2. $(x,y_1)\in f$ and $(x,y_2)\in f$ $\Longrightarrow$ $y_1=y_2$.

If $(x,y)\in f$ then we write $y=f(x)$. If $f\subseteq A\times B$ is a function, we write $f: A\longrightarrow B$. We call $A$ and $B$ the domain and the codomain of $f$, respectively. The set \begin{align*}f(A)&=\{y\in B: (x,y)\in f\ \mbox{for some}\ x\in A\}\\&=\{f(x):x\in A\}\end{align*} is called the range of $f$. A function $f: A\longrightarrow B$ is onto or surjective if $f(A)=B$. A function $f: A\longrightarrow B$ is one-to-one or injective if $(x_1,y)\in f$ and $(x_2,y)\in f$ $\Longrightarrow$ $x_1=x_2$. A function $f: A\longrightarrow B$ is bijective if it is both injective and surjective. A bijective function is also called a one-to-one correspondence.

Theorem. An inverse graph $f^{-1}\subseteq B\times A$ of a function $f\subseteq A\times B$ is a function if and only if $f$ is bijective.

Proof. ($\Longrightarrow$) Suppose that $f^{-1}\subseteq A\times B$ is a function. $\forall y\in B$, $\exists x\in A$ such that $(y,x)\in f^{-1}\Longrightarrow (x,y)\in f$. Thus $f$ is surjective. $(x_1,y)\in f$ and $(x_2,y)\in f$ $\Longrightarrow$ $(y,x_1)\in f^{-1}$ and $(y,x_2)\in f^{-1}$ $\Longrightarrow$ $x_1=x_2$. Thus $f$ is injective. Therefore, $f$ is bijective.

($\Longleftarrow$) Suppose that $f: A\longrightarrow B$ is bijective.

F1. Let $y\in B$. Then $\exists x\in A$ such that $(x,y)\in f\Longrightarrow (y,x)\in f^{-1}$.

F2. $(y,x_1)\in f^{-1}$ and $(y,x_2)\in f^{-1}$ $\Longrightarrow$ $(x_1,y)\in f$ and $(x_2,y)\in f$ $\Longrightarrow$ $x_1=x_2$.

Theorem. If $f: A\longrightarrow B$ and $g: B\longrightarrow C$ are bijective then the composition $g\circ f: A\longrightarrow C$ is also bijective.

Proof. F1. Let $x\in A$. Then $\exists y\in B$ such that $y=f(x)$. Also $\exists z\in C$ such that $g(y)=z$. Hence, $$g\circ f(x)=g(f(x))=f(y)=z$$

F2. $$x_1=x_2\Longrightarrow f(x_1)=f(x_2)\Longrightarrow g\circ f(x_1)=g\circ f(x_2)$$

Surjective: Let $z\in C$. Then $\exists y\in B$ such that $g(y)=z$. Also $\exists x\in A$ such that $f(x)=y$. Thus, $g\circ f(x)=z$.

Injective: \begin{align*}g\circ f(x_1)=g\circ f(x_2)&\Longrightarrow g(f(x_1))=g(f(x_2))\\&\Longrightarrow f(x_1)=f(x_2)\\&\Longrightarrow x_1=x_2\end{align*}


[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

[2] Set Theory, Charles C. Pinter, Addison Wesley Publishing Company, 1971

Leave a Reply

Your email address will not be published. Required fields are marked *