# Definition:Surjection

## Contents

## Definition

Let $S$ and $T$ be sets.

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

### Definition 1

$f: S \to T$ is a **surjection** if and only if:

- $\forall y \in T: \exists x \in \Dom f: \map f x = y$

That is, if and only if $f$ is right-total.

### Definition 2

$f: S \to T$ is a **surjection** if and only if:

- $f \sqbrk S = T$

## Graphical Depiction

The following diagram illustrates the mapping:

- $f: S \to T$

where $S$ and $T$ are the finite sets:

\(\displaystyle S\) | \(=\) | \(\displaystyle \set {a, b, c, i, j, k}\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle T\) | \(=\) | \(\displaystyle \set {p, q, r, s}\) | $\quad$ | $\quad$ |

and $f$ is defined as:

- $f = \set {\tuple {a, p}, \tuple {b, p}, \tuple {c, q}, \tuple {i, r}, \tuple {j, s}, \tuple {k, s} }$

Thus the images of each of the elements of $S$ under $f$ are:

\(\displaystyle \map f a\) | \(=\) | \(\displaystyle \map f b = p\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \map f c\) | \(=\) | \(\displaystyle q\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \map f i\) | \(=\) | \(\displaystyle r\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \map f j\) | \(=\) | \(\displaystyle \map f k = s\) | $\quad$ | $\quad$ |

The preimages of each of the elements of $T$ under $f$ are:

\(\displaystyle \map {f^{-1} } p\) | \(=\) | \(\displaystyle \set {a, b}\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \map {f^{-1} } q\) | \(=\) | \(\displaystyle \set c\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \map {f^{-1} } r\) | \(=\) | \(\displaystyle \set i\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \map {f^{-1} } s\) | \(=\) | \(\displaystyle \set {j, k}\) | $\quad$ | $\quad$ |

## Also known as

The phrase **$f$ is surjective** is often used for **$f$ is a surjection**.

Authors who prefer to limit the jargon of mathematics tend to use the term **an onto mapping** for **a surjection**, and **onto** for **surjective**.

A mapping which is **not surjective** is thence described as **into**.

A surjection $f$ from $S$ to $T$ is sometimes denoted:

- $f: S \twoheadrightarrow T$

to emphasize surjectivity.

The $\LaTeX$ code for \(f: S \twoheadrightarrow T\) is `f: S \twoheadrightarrow T`

.

## Examples

### Negative Function on Integers

Let $f: \Z \to \Z$ be the mapping defined on the set of integers as:

- $\forall x \in \Z: \map f x = -x$

Then $f$ is a surjection.

### Floor Function of $\dfrac {x + 1} 2$ on $\Z$

Let $f: \Z \to \Z$ be the mapping defined on the set of integers as:

- $\forall x \in \Z: \map f x = \floor {\dfrac {x + 1} 2}$

where $\floor {\, \cdot \,}$ denotes the floor function.

Then $f$ is a surjection, but not an injection.

### $\map f x = \dfrac x 2$ for $x$ Even, $0$ for $x$ Odd

Let $f: \Z \to \Z$ be the mapping defined on the set of integers as:

- $\forall x \in \Z: \map f x = \begin{cases} \dfrac x 2 & : x \text { even} \\ 0 & : x \text { odd} \end{cases}$

Then $f$ is a surjection.

## Also see

- In Surjection iff Image equals Codomain, it is shown that a mapping $f$ is a surjection if and only if its image equals its codomain.

- In Surjection iff Right Cancellable it is shown that a mapping $f$ is a surjection if and only if it is right cancellable.

- In Surjection iff Right Inverse it is shown that a mapping $f$ is a surjection if and only if it has a right inverse.

- In Preimages All Exist iff Surjection, it is shown that a mapping $f$ is a surjection if and only if the preimage of every element is guaranteed not to be empty.

- In Subset equals Image of Preimage iff Mapping is Surjection, it is shown that a mapping $f$ is a surjection if and only if the image of the preimage of every subset of its codomain equals that subset.

- Results about
**surjections**can be found here.

## Sources

- For a video presentation of the contents of this page, visit the Khan Academy.