Definition:Mapping

From ProofWiki
Jump to: navigation, search

Definition

Let $S$ and $T$ be sets.

Let $S\times T$ be their cartesian product.


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 = \left({S, T, R}\right)$, where $R \subseteq S \times T$, such that:

$\forall \left({x_1, y_1}\right), \left({x_2, y_2}\right) \in f: y_1 \ne y_2 \implies x_1 \ne x_2$

and

$\forall x \in S: \exists y \in T: \left({x, y}\right) \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$.


General Definition

Let $\displaystyle \prod_{i \mathop = 1}^n S_i$ be the cartesian product of sets $S_1$ to $S_n$.

Let $\displaystyle \mathcal R \subseteq \prod_{i \mathop = 1}^n S_i$ be an $n$-ary relation on $\displaystyle \prod_{i \mathop = 1}^n S_i$.


Then $\mathcal R$ is a mapping if and only if:

$\displaystyle \forall x := \left({x_1, x_2, \ldots, x_{n-1}}\right) \in \prod_{i \mathop = 1}^{n-1} S_i: \forall y_1, y_2 \in S_n: \left({x, y_1}\right) \in \mathcal R \land \left({x, y_2}\right) \in \mathcal R \implies y_1 = y_2$

and

$\displaystyle \forall x := \left({x_1, x_2, \ldots, x_{n-1}}\right) \in \prod_{i \mathop = 1}^{n-1} S_i: \exists y \in S_n: \left({x, y}\right) \in \mathcal R$


Thus, a mapping is an $n$-ary relation which is:

Many-to-one
Left-total, that is, defined for all elements in the domain.


Self-Map

Let $S$ be a set.

A self-map on $S$ is a mapping from $S$ to itself:

$f: S \to S$


Defined

A mapping $f \subseteq S \times T$ is defined at $x \in S$ if and only if:

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


If for some $x \in S$, one has:

$\forall y \in T: \tuple {x, y} \notin f$

then $f$ is not defined or (undefined) at $x$, and indeed, $f$ is not technically a mapping at all.


Domain, Codomain, Image, Preimage

As a mapping is also a relation, all the results and definitions concerning relations also apply to mappings.

In particular, the concepts of domain and codomain carry over completely, as do the concepts of image and preimage.


Domain

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

The domain of $f$ is the set $S$ and can be denoted $\Dom f$.

In the context of mappings, the domain and the preimage of a mapping are the same set.


Codomain

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

The codomain of $f$ is the set $T$.

It is denoted on $\mathsf{Pr} \infty \mathsf{fWiki}$ by $\Cdm f$.


Image

Definition 1

The image of a mapping $f: S \to T$ is the set:

$\Img f = \set {t \in T: \exists s \in S: f \paren s = t}$

That is, it is the set of values taken by $f$.


Definition 2

The image of a mapping $f: S \to T$ is the set:

$\Img f = f \sqbrk S$

where $f \sqbrk S$ is the image of $S$ under $f$.


Preimage

The preimage of $f$ is defined as:

$\Preimg f := \set {s \in S: \exists t \in T: f \paren s = t}$

That is:

$\Preimg f := f^{-1} \sqbrk T$

where $f^{-1} \sqbrk T$ is the image of $T$ under $f^{-1}$.


In this context, $f^{-1} \subseteq T \times S$ is the the inverse of $f$.

It is a relation but not necessarily itself a mapping.


Diagrammatic Presentations

Mapping on Finite Set

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, p}, \tuple {i, r}, \tuple {j, s}, \tuple {k, s} }$


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

\(\displaystyle f \paren a\) \(=\) \(\displaystyle f \paren b = f \paren c = p\) $\quad$ $\quad$
\(\displaystyle f \paren i\) \(=\) \(\displaystyle r\) $\quad$ $\quad$
\(\displaystyle f \paren j\) \(=\) \(\displaystyle f \paren k = s\) $\quad$ $\quad$
MappingFinite.png
$S$ is the domain of $f$.
$T$ is the codomain of $f$.
$\set {p, r, s}$ is the image of $f$.


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

\(\displaystyle f^{-1} \paren p\) \(=\) \(\displaystyle \set {a, b, c}\) $\quad$ $\quad$
\(\displaystyle f^{-1} \paren q\) \(=\) \(\displaystyle \O\) $\quad$ $\quad$
\(\displaystyle f^{-1} \paren r\) \(=\) \(\displaystyle \set i\) $\quad$ $\quad$
\(\displaystyle f^{-1} \paren s\) \(=\) \(\displaystyle \set {j, k}\) $\quad$ $\quad$


Mapping on Infinite Set

The following diagram illustrates the mapping:

$f: S \to T$

where $S$ and $T$ are areas of the the plane, each containing an infinite number of points.


Mapping.png


$\Dom f$ is the domain of $f$.
$\Cdm f$ is the codomain of $f$.
$\Img f$ is the image of $f$.


Note that by Image is Subset of Codomain:

$\Img f \subseteq \Cdm f$

There are no other such constraints upon the domain, image and codomain.


Mapping as Unary Operation

It can be noted that a mapping can be considered as a unary operation.


Notation

Let $f = \tuple {S, T, R}$, where $R \subseteq S \times T$, be a mapping.

This is usually denoted $f: S \to T$, which is interpreted to mean:

$f$ is a mapping with domain $S$ and codomain $T$
$f$ is a mapping of (or from) $S$ to (or into) $T$
$f$ maps $S$ to (or into) $T$.

The notation $S \stackrel f {\longrightarrow} T$ is also seen.


For $x \in S, y \in T$, the usual notation is:

$f: S \to T: f \paren x = y$

where $f \paren x = y$ is interpreted to mean $\tuple {x, y} \in f$.

It is read $f$ of $x$ equals $y$.

This is the preferred notation on $\mathsf{Pr} \infty \mathsf{fWiki}$.


Sometimes the brackets are omitted: $f x = y$, as seen in 1971: Allan Clark: Elements of Abstract Algebra, for example.


The notation $f: x \mapsto y$ is often seen, read $f$ maps, or sends, $x$ to $y$.


Less common notational forms of $f \paren x = y$ are:

$x f = y$, as seen in 1951: Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts and 1968: Ian D. Macdonald: The Theory of Groups, for example
$x^f = y$, as seen in 1951: Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts, for example
$f_x = y$, as remarked on in 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.), for example.

1955: John L. Kelley: General Topology provides a list of several different styles: $\tuple {f, x}$, $\tuple {x, f}$, $f x$, $x f$ and $\cdot f x$, and discusses the advantages and disadvantages of each.

The notation $\cdot f x$ is attributed to Anthony Perry Morse, and can be used to express complicated expressions without the need of parenthesis to avoid ambiguity. However, it appears not to have caught on.


Also known as

Words which are often used to mean the same thing as mapping include:

transformation (particularly in the context of self-maps)
operator
function (usually in the context of numbers)
map (but this term is discouraged, as the term is also used by some writers for planar graph).

Some sources introduce the concept with informal words such as rule or idea or mathematical notion.

Sources defining a mapping (function) to be only a many-to-one relation refer to a mapping (function) as a total mapping (total function).


The wording can vary.

A mapping $f$ from $S$ to $T$ is also described as a mapping on $S$ into $T$.


Also defined as

Some approaches, for example 1999: András Hajnal and Peter Hamburger: Set Theory, define a mapping as a many-to-one relation from $S$ to $T$, and then separately specify its requisite left-total nature by restricting $S$ to the domain. However, this approach is sufficiently different from the mainstream approach that it will not be used on $\mathsf{Pr} \infty \mathsf{fWiki}$ and limited to this mention.


Examples

Rotation of Cartesian Plane Anticlockwise through $30 \degrees$

Let $\Gamma$ be the Cartesian plane.

The rotation $R_{30 \degrees}$ of $\Gamma$ anticlockwise through an angle of $30 \degrees$ about the origin $O$ is a mapping from $\Gamma$ to $\Gamma$.


Mistakes

Here are some supposed definitions of mappings which contain mistakes.

Image Elements not in Codomain

$f: \N \to \N$ defined as: $\forall x \in \N: x \mapsto x - 7$


Image Element Undefined

$g: \R \to \R$ defined as: $\forall x \in \R: x \mapsto \dfrac 1 x$


Image Element Multiply Defined

$h: \R \to \R$ defined as: $\forall x \in \R: x \mapsto \begin{cases} x + 1 & : x \ge 0 \\ 0 & : x \le 0 \end{cases}$


Mapping not Well-Defined

$\theta: \Q \to \Z$ defined as: $\forall m, n \in \Z, n \ne 0: \dfrac m n \mapsto m + n$


Also see

  • Results about mappings can be found here.


Sources