Definition:Surjection
Definition
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$
or, in the language and notation of direct image mappings:
- $\map {f^\to} S = T$
That is, $f$ is a surjection if and only if its image equals its codomain:
- $\Img f = \Cdm f$
Class-Theoretical Definition
Let $A$ and $B$ be classes.
Let $f: A \to B$ be a mapping from $A$ to $B$.
Then $f$ is a surjection if and only if:
- $\Img f = B$
where $\Img f$ denotes the image of $f$.
That is, if and only if:
- $\forall y \in B: \exists x \in A: \map f x = y$
Graphical Depiction
The following diagram illustrates the mapping:
- $f: S \to T$
where $S$ and $T$ are the finite sets:
| \(\ds S\) | \(=\) | \(\ds \set {a, b, c, i, j, k}\) | ||||||||||||
| \(\ds T\) | \(=\) | \(\ds \set {p, q, r, s}\) |
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:
| \(\ds \map f a\) | \(=\) | \(\ds \map f b = p\) | ||||||||||||
| \(\ds \map f c\) | \(=\) | \(\ds q\) | ||||||||||||
| \(\ds \map f i\) | \(=\) | \(\ds r\) | ||||||||||||
| \(\ds \map f j\) | \(=\) | \(\ds \map f k = s\) |
The preimages of each of the elements of $T$ under $f$ are:
| \(\ds \map {f^{-1} } p\) | \(=\) | \(\ds \set {a, b}\) | ||||||||||||
| \(\ds \map {f^{-1} } q\) | \(=\) | \(\ds \set c\) | ||||||||||||
| \(\ds \map {f^{-1} } r\) | \(=\) | \(\ds \set i\) | ||||||||||||
| \(\ds \map {f^{-1} } s\) | \(=\) | \(\ds \set {j, k}\) |
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.
In the context of class theory, a surjection is often seen referred to as a class surjection.
Examples
Arbitrary Example $1$
Let $S$ and $T$ be sets such that:
| \(\ds S\) | \(=\) | \(\ds \set {a, b, c}\) | ||||||||||||
| \(\ds T\) | \(=\) | \(\ds \set {x, y}\) |
Let $f: S \to T$ be the mapping defined as:
| \(\ds \map f a\) | \(=\) | \(\ds x\) | ||||||||||||
| \(\ds \map f b\) | \(=\) | \(\ds x\) | ||||||||||||
| \(\ds \map f c\) | \(=\) | \(\ds y\) |
Then $f$ is a surjection.
Arbitrary Example $2$
Let $S$ and $T$ be sets such that:
| \(\ds S\) | \(=\) | \(\ds \set {2, -2, 3}\) | ||||||||||||
| \(\ds T\) | \(=\) | \(\ds \set {4, 9}\) |
Let $f: S \to T$ be the mapping defined as:
- $f: x \mapsto x^2$
Then $f$ is a surjection.
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.
Doubling Function on Reals
Let $f: \R \to \R$ be the real function defined as:
- $\forall x \in \R: \map f x = 2 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 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.
Technical Note
The $\LaTeX$ code for \(f: S \twoheadrightarrow T\) is f: S \twoheadrightarrow T .
Sources
- 2002: Thomas Jech: Set Theory (3rd ed.) ... (previous) ... (next): Chapter $1$: Power Set
- For a video presentation of the contents of this page, visit the Khan Academy.