# Equivalence of Definitions of Mapping

## Theorem

The following definitions of the concept of **Mapping** are equivalent:

### Definition 1

A **mapping** from $S$ to $T$ is a binary relation on $S \times T$ which associates each element of $S$ with exactly one element of $T$.

### Definition 2

A **mapping $f$ from $S$ to $T$**, denoted $f: S \to T$, is a relation $f = \struct {S, T, G}$, where $G \subseteq S \times T$, such that:

- $\forall x \in S: \forall y_1, y_2 \in T: \tuple {x, y_1} \in G \land \tuple {x, y_2} \in G \implies y_1 = y_2$

and

- $\forall x \in S: \exists y \in T: \tuple {x, y} \in G$

### Definition 3

A **mapping $f$ from $S$ to $T$**, denoted $f: S \to T$, is a relation $f = \struct {S, T, R}$, where $R \subseteq S \times T$, such that:

- $\forall \tuple {x_1, y_1}, \tuple {x_2, y_2} \in f: y_1 \ne y_2 \implies x_1 \ne x_2$

and

- $\forall x \in S: \exists y \in T: \tuple {x, y} \in f$

### Definition 4

A **mapping from $S$ to $T$** is a relation on $S \times T$ which is:

- $(1): \quad$ Many-to-one
- $(2): \quad$ Left-total, that is, defined for all elements in $S$.

## Proof

In the following, let $f \subseteq S \times T$ be a relation on $S \times T$.

### $(1)$ if and only if $(4)$

$f$ is by definition left-total if and only if:

- $\forall s \in S: \exists t \in T: \tuple {s, t} \in f$

which means exactly the same thing as:

$f$ is by definition many-to-one if and only if:

- $\forall x \in \Dom f: \tuple {x, y_1} \in f \land \tuple {x, y_2} \in f \implies y_1 = y_2$

which means exactly the same thing as:

Thus:

- $f$ is left-total and many-to-one

That is:

- $f$ is a mapping by definition 1

- $f$ is a mapping by definition 4.

$\Box$

### $(2)$ if and only if $(4)$

$f$ is by definition left-total if and only if:

- $\forall s \in S: \exists t \in T: \tuple {s, t} \in G$

and:

$f$ is by definition many-to-one if and only if:

- $\forall x \in \Dom f: \forall y_1, y_2 \in \Cdm f: \tuple {x, y_1} \in f \land \tuple {x, y_2} \in f \implies y_1 = y_2$

which means exactly the same thing as:

- $\forall x \in S: \forall y_1, y_2 \in T: \tuple {x, y_1} \in f \land \tuple {x, y_2} \in f \implies y_1 = y_2$

That is:

- $f$ is a mapping by definition 2

- $f$ is a mapping by definition 4.

$\Box$

### $(2)$ if and only if $(3)$

Both definition 2 and definition 3 carry the stipulation that:

- $\forall x \in S: \exists y \in T: \tuple {x, y} \in f$

Then we have that definition 2 carries the stipulation that

- $\forall x \in S: \forall y_1, y_2 \in T: \tuple {x, y_1} \in f \land \tuple {x, y_2} \in f \implies y_1 = y_2$

By the Rule of Transposition, that means the same as:

- $\forall x \in S: \forall y_1, y_2 \in T: \neg \paren {y_1 = y_2} \implies \neg \paren {\tuple {x, y_1} \in f \land \tuple {x, y_2} \in f}$

which in turn is the same as:

- $\forall \tuple {x_1, y_1}, \tuple {x_2, y_2} \in f: y_1 \ne y_2 \implies x_1 \ne x_2$

which is the other stipulation of definition 3.

That is:

- $f$ is a mapping by definition 2

- $f$ is a mapping by definition 3.

$\blacksquare$