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*}

*References*.

[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