# Mapping is Injection and Surjection iff Inverse is Mapping/Proof 1

## Theorem

Let $S$ and $T$ be sets.

Let $f: S \to T$ be a mapping.

Then:

- $f: S \to T$ can be defined as a bijection in the sense that:
- $(1): \quad f$ is an injection
- $(2): \quad f$ is a surjection.

iff:

- the inverse $f^{-1}$ of $f$ is such that:
- for each $y \in T$, the preimage $f^{-1} \left({y}\right)$ has exactly one element.

- That is, such that $f^{-1} \subseteq T \times S$ is itself a mapping.

## Proof

Recall the definition of the inverse of $f$:

$f^{-1} \subseteq T \times S$ is the relation defined as:

- $f^{-1} = \left\{{\left({t, s}\right): t = f \left({s}\right)}\right\}$

### Necessary Condition

Let $f: S \to T$ be a bijection in the sense that:

- $(1): \quad f$ is an injection
- $(2): \quad f$ is a surjection.

By Inverse of Injection is Functional Relation, $f^{-1}$ is functional.

That is:

- $\forall y_1, y_2 \in T: f^{-1} \left({y_1}\right) \ne f^{-1} \left({y_2}\right) \implies y_1 = y_2$

Hence the preimage $f^{-1} \left({y}\right)$ has **at most** one element.

By Surjection iff Image equals Codomain:

- $\operatorname{Im} \left({f}\right) = T$

That is:

- $\forall y \in T: \exists x \in S: f^{-1} \left({y}\right) = x$

Hence the preimage $f^{-1} \left({y}\right)$ has **at least** one element.

Thus the preimage $f^{-1} \left({y}\right)$ has exactly one element.

Hence, by definition, $f^{-1}$ is a mapping.

$\Box$

### Sufficient Condition

Let $f^{-1}: T \to S$ be a mapping.

It is necessary to show that $f$ is both an injection and a surjection.

Let $f \left({x_a}\right) = y$ and $f \left({x_b}\right) = y$.

Then:

\(\displaystyle \left({x_a, y}\right)\) | \(\in\) | \(\displaystyle f\) | |||||||||||

\(\, \displaystyle \land \, \) | \(\displaystyle \left({x_b, y}\right)\) | \(\in\) | \(\displaystyle f\) | by definition of mapping as a relation | |||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle \left({y, x_a}\right)\) | \(\in\) | \(\displaystyle f^{-1}\) | ||||||||||

\(\, \displaystyle \land \, \) | \(\displaystyle \left({y, x_b}\right)\) | \(\in\) | \(\displaystyle f^{-1}\) | by definition of inverse of mapping | |||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle x_a\) | \(=\) | \(\displaystyle x_b\) | as $f^{-1}$ is a mapping |

Thus, by definition, $f$ is an injection.

$\Box$

Aiming for a contradiction, suppose that $f$ is not a surjection.

That is:

- $\exists y \in T: \neg \exists x \in S: \left({x, y}\right) \in f$

By definition of inverse of mapping:

- $\exists y \in T: \neg \exists x \in S: \left({y, x}\right) \in f^{-1}$

which would mean that $f^{-1}$ is not a mapping.

From this contradiction it follows that $f$ is a surjection.

$\Box$

So, being both an injection and a surjection, it follows by definition that $f$ is a bijection.

$\blacksquare$