**Thm.** $g:X \rightarrow Y$ is invertible iff $g$ is bijective.

**Pf.** Two implications need to be proven:

- $g$ is invertible $\rightarrow$ $g$ is bijective.
- $g$ is bijective $\rightarrow$ $g$ is invertible.

ad (1): The proposition has it that $g$ is invertible $\leftrightarrow (\exists h:Y\rightarrow X) \: g \circ h = \text{id}_{Y} \wedge h \circ g = \text{id}_{X}$. Or, equivalently,
$$
(\exists h)(\underbrace{(\forall y \in Y) \: g(h(y)) = y}_{(i)}
\: \wedge \:
\underbrace{(\forall x \in X) \: h(g(x)) = x)}_{(ii)}.
$$
I.e. assume, according to (i), there is a function $h$ such that for every element in $Y$ there is an element $h(y) = x \in X$ such that $g(x) = y$. This is the definition for $g$ to be onto/surjective. Now assume that $g$ is not 1-1:
$$ (\exists x,x' \in X) \: x \neq x' \wedge g(x) = g(x'). $$
Since $h$ is a function this means that
$$ (\forall g(x),g(x') \in Y) \: g(x) = g(x') \rightarrow h(g(x)) = h(g(x')). $$
So we can deduce
$$ g \text{ is not onto } \rightarrow (\exists x,x' \in X) \: ( h(g(x')) = h(g(x)) = x' \neq x ) \leftrightarrow (\forall h)(\exists x \in X) \: h(g(x)) \neq x,$$
where the contrapositive states that
$$ (\exists h)(\forall x \in X) \: h(g(x)) = x \rightarrow g \text{ is onto}. $$
Hence, (ii) implies $g$ to be an injection.

2015 MAR 19 (v1.0)