1.4 Mappings

Editorial note

In Example 1.8 the fibre-to-class map is defined on the image $\phi (X)$; fibres of points outside the image are empty. Injectivity means at most one preimage, not existence of a preimage for every codomain point.

Let X and Y be any two sets. A mapping $\phi$ from X to $Y,$ , often written $\phi :X\to Y,$ , is a subset of $X\times Y$ such that for every $x\in X$ there is a unique $y\in Y$ for which $(x,y)\in \phi$ By unique we mean

$$(x,y)\in \phi \text{ and }(x,y^{\prime })\in \phi ⟹y=y^{\prime }.$$

Mappings are also called functions or maps. It is most common to write $y=\phi (x)$ for $(x,y)\in \phi$ . Whenever $y=\phi (x)$ it is said that x is mapped to $y,$ , written $\phi :x\mapsto y$

In elementary mathematics it is common to refer to the subset $\phi \subseteq X\times Y$ as representing the graph of the function $\phi .$ . Our definition essentially identifies a function with its graph. The set X is called the domain of the mapping $\phi ,$ and the subset $\phi (X)\subseteq Y$ defined by

$$\phi (X)=\{y\in Y\mid y=\phi (x),x\in X\}$$

is called its range.

Let $U$ be any subset of Y. The inverse image of $U$ is defined to be the set of all points of $X$ that are mapped by $\phi$ into $U$ , denoted

$${\phi }^{-1}(U)=\{x\in X|\phi (x)\in U\}.$$

This concept makes sense even when the inverse map ${\phi }^{-1}$ does not exist. The notation ${\phi }^{-1}(U)$ is to be regarded as one entire symbol for the inverse image set, and should not be broken into component parts.

Example 1.6

Let sin: $\mathbb{R}\to \mathbb{R}$ be the standard sine function on the real numbers R. The inverse image of 0 is ${\sin }^{-1}(0)=\{0,\pm \pi ,\pm 2\pi ,\pm 3\pi ,...\}$ , while the inverse image of 2 is the empty set, ${\sin }^{-1}(2)=\varnothing$

Multi-argument functions and projections

An n-ary function from X to Y is a function $\phi :X^n\to Y$ . In this case we write $y=$ $\phi (x_1,x_2,\dots ,x_n)\mathrm{for}\left((x_1,x_2,\dots ,x_n),y\right)\in \phi$ and say that ϕ has n arguments in the set S, although strictly speaking it has just one argument from the product set $X^n=X\times \cdots \times X.$

It is possible to generalize this concept even further and consider maps whose domain is a product of n possibly different sets,

$$\phi :X_1\times X_2\times \cdots \times X_n\to Y.$$

Important maps of this type are the projection maps

$${\mathrm{pr}}_i:X_1\times X_2\times \dots X_n\to X_i$$

defined by

$${\mathrm{pr}}_i:(x_1,x_2,\dots ,x_n)\mapsto x_i.$$

Composition

If $\phi :X\to Y$ and $\psi :Y\to Z$ , the composition map $\psi \circ \phi :X\to Z$ is defined by

$$\psi \circ \phi (x)=\psi (\phi (x)).$$

Composition of maps satisfies the associative law

$$\alpha \circ (\psi \circ \phi )=(\alpha \circ \psi )\circ \phi$$

where $\alpha :Z\to W$ ,

Proof

For any $x\in X$

$$\alpha \circ (\psi \circ \phi )(x)=\alpha (\psi (\phi (x)))=(\alpha \circ \psi )(\phi (x))=(\alpha \circ \psi )\circ \phi (x).$$

Hence, there is no ambiguity in writing $\alpha \circ \psi \circ \phi$ for the composition of three maps.

Surjective, injective and bijective maps

A mapping $\phi :X\to Y$ is said to be surjective or a surjection if its range is all of Y. More simply, we say $\phi$ is a mapping of X onto Y if $\phi (\mathbf{X})=\mathbf{Y}$ . It is said to be one-to-one or injective, or an injection, if for every $y\in Y$ there is at most one $x\in X$ such that $y=\phi (x)$ ; that is,

$$\phi (x)=\phi (x^{\prime })⟹x=x^{\prime }.$$

A map $\phi$ that is injective and surjective, or equivalently one-to-one and onto, is called bijective or a bijection. In this and only this case can one define the inverse map ${\phi }^{-1}$ $Y\to X$ having the property

$${\phi }^{-1}(\phi (x))=x,\forall x\in X.$$

Two sets X and Y are said to be in one-to-one correspondence with each other if there exists a bijection $\phi :X\to Y$

Exercise

Show that if $\phi :X\to Y$ is a bijection, then so is ${\phi }^{-1}$ , and that $\phi ({\phi }^{-1}(y))=y,\forall y\in Y.$

A bijective map $\phi :X\to X$ from X onto itself is called a transformation of X. The most trivial transformation of all is the identity map id defined by

$${\mathrm{id}}_X(x)=x,\forall x\in X.$$

Note that this map can also be described as having a ‘diagonal graph’,

$${\mathrm{id}}_X=\{(x,x)|x\in X\}\subseteq X\times X.$$

Exercise

Show that for any map $\phi :X\to Y,{\mathrm{id}}_Y\circ \phi =\phi \circ {\mathrm{id}}_X=\phi$

When $\phi :X\to Y$ is a bijection with inverse ${\phi }^{-1}$ , then we can write

$${\phi }^{-1}\circ \phi ={\mathrm{id}}_X,\phi \circ {\phi }^{-1}={\mathrm{id}}_Y.$$

If both $\phi$ and $\psi$ are bijections then so is $\psi \circ \phi$ , and its inverse is given by

$$(\psi \circ \phi {)}^{-1}={\phi }^{-1}\circ {\psi }^{-1}$$

Proof

By associativity,

$${\phi }^{-1}\circ {\psi }^{-1}\circ \psi \circ \phi ={\phi }^{-1}\circ {\mathrm{id}}_Y\circ \phi ={\phi }^{-1}\circ \phi ={\mathrm{id}}_X.$$

Restrictions and inclusions

If $U$ is any subset of X and $\phi :X\to Y$ is any map having domain X, then we define the restriction of $\phi$ to $U$ as the map $\phi {|}_U:U\to Y$ by $\phi {|}_U(x)=\phi (x)$ for all $x\in U$ . The restriction of the identity map

$$i_U={\mathrm{id}}_X{|}_U:U\to X$$

is referred to as the inclusion map for the subset U. The restriction of an arbitrary map $\phi$ to $U$ is then its composition with the inclusion map,

$$\phi {|}_U=\phi \circ i_U.$$

Example 1.7

If $U$ is a subset of $X,$ , define a function ${\chi }_U:X\to \{0,1\}$ , called the characteristic function of $U$ , by

$${\chi }_U(x)=\{\begin{array}{ll}0& \text{ if }x\notin U,\\ 1& \text{ if }x\in U.\end{array}$$

Any function $\phi :X\to \{0,1\}$ is evidently the characteristic function of the subset $U\subseteq X$ consisting of those points that are mapped to the value 1,

$$\phi ={\chi }_U\text{ where }U={\phi }^{-1}(\{1\}).$$

Thus the power set $2^X$ and the set of all maps $\phi :X\to \{0,1\}$ are in one-to-one correspondence.

Referenced 3 times

• 1.5 Infinite setsFor any two sets S and T the set of all maps … will be denoted by … . Justification for this notatio…
• 1.5 Infinite setsThe sequence x is essentially the characteristic function of the subset … , discussed in Example 1.7…
• 1.6 StructuresDiscrete dynamical structures are often described on the set of states on a given set … where a stat…

Example 1.8

Let R be an equivalence relation on a set X. Define the canonical map $\phi :X\to X/R$ from X onto the factor space by

$$\phi (x)=[x{]}_R,\forall x\in X.$$

It is easy to verify that this map is onto.

More generally, any map $\phi :X\to Y$ defines an equivalence relation R on X by aRb iff $\phi (a)=\phi (b)$ . The equivalence classes defined by R are precisely the inverse images of the singleton subsets of $Y$ ,

$$X/R=\{{\phi }^{-1}(\{y\})\mid y\in \phi (X)\},$$

and the map $\psi :\phi (X)\to X/R$ defined by $\psi (y)={\phi }^{-1}(\{y\})$ is one-to-one, for if $\psi (y)=\psi (y^{\prime })$ then $y=y^{\prime }-\mathsf{pick}$ any element $x\in \psi (y)=\psi (y^{\prime })$ and we must have $\phi (x)=y=y^{\prime }$

Referenced 1 time

• 1.4 MappingsIn Example 1.8 the fibre-to-class map is defined on the image …; fibres of points outside the image …

Referenced 1 time

• 1.7 Category theoryThe simplest example of a category is the category of sets, in which the objects are all possible se…