Definition:Surjection

From ProofWiki
Jump to navigation Jump to search

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\)
Surjection.png
$S$ is the domain of $f$.
$T$ is the codomain of $f$.
$\set {p, q, r, s}$ is the image of $f$.


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 Finite Set

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.


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



  • Results about surjections can be found here.


Technical Note

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


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Surjection&oldid=680789"