Mapping/Injective/Surjective/Composition/Introduction/Section

Definition

Let ${}L$ and ${}M$ denote sets, and let

$F\colon L\longrightarrow M,x\longmapsto F(x),$

be a mapping. Then ${}F$ is called injective, if for two different elements ${}x,x'\in L$, also ${}F(x)$ and ${}F(x')$

are different.

If we want to show that a certain mapping is injective then we may show the following: For any two elements ${}x$ and ${}x'$ fulfilling the condition ${}F(x)=F(x')$, we can deduce that ${}x=x'$. This is often easier to show than the statement that ${}x\neq x'$ implies ${}F(x)\neq F(x')$.

Definition

Let ${}L$ and ${}M$ denote sets, and let

$F\colon L\longrightarrow M,x\longmapsto F(x),$

be a mapping. Then ${}F$ is called surjective, if for every ${}y\in M$, there exists at least one element ${}x\in L$, such that

${}F(x)=y\,.$

Example

We consider a football game as the mapping which assigns, to every goal of team ${}A$, the corresponding goal scorer. Suppose that there are no own goals and no changes. The goals of ${}A$ are numbered by ${}1,2,\ldots ,n$. Then we have a mapping

$\psi \colon \{1,\ldots ,n\}\longrightarrow A=\{{\text{player }}1,\,{\text{player }}2,\ldots ,{\text{player }}11\},$

given by

${}\psi (i)={\text{ the player who has scored the }}i{\text{-th goal}}\,.$

The injectivity of ${}\psi$ means that every player has scored at most one goal, the surjectivity means that every player has scored at least one goal.

Example

Let ${}H$ denote the set of all (living or dead) people. We study the mapping

$\varphi \colon H\longrightarrow H,$

which assigns to every person his or her (biological) mother. This is well-defined, as every person has a uniquely determined mother. This mapping is not injective, since there exists different people (brothers and sisters) with the same mother. It is also not surjective, since not every person is a mother of somebody.

Example

The mapping

$\mathbb {R} \longrightarrow \mathbb {R} ,x\longmapsto x^{2},$

is neither injective nor surjective. It is not injective, because the different numbers ${}2$ and ${}-2$ are both sent to ${}4$. It is not surjective, because only nonnegative elements are in the image (a negative number does not have a real square root). The mapping

$\mathbb {R} _{\geq 0}\longrightarrow \mathbb {R} ,x\longmapsto x^{2},$

is injective, but not surjective. The injectivity can be seen as follows: If ${}x\neq y$, then one number is larger, say

${}x>y\geq 0\,.$

But then also ${}x^{2}>y^{2}$, and in particular ${}x^{2}\neq y^{2}$. The mapping

$\mathbb {R} \longrightarrow \mathbb {R} _{\geq 0},x\longmapsto x^{2},$

is not injective, but surjective, since every nonnegative real number has a square root. The mapping

$\mathbb {R} _{\geq 0}\longrightarrow \mathbb {R} _{\geq 0},x\longmapsto x^{2},$

is injective and surjective.

Definition

Let ${}M$ and ${}L$ denote sets and suppose that

$F\colon M\longrightarrow L,x\longmapsto F(x),$

is a mapping. Then ${}F$ is called bijective if ${}F$ is injective as well as

surjective.

Remark

The question, whether a mapping ${}F\colon L\rightarrow M$ has the properties of being injective or surjective, can be understood looking at the equation

${}F(x)=y\,$

(in the two variables ${}x$ and ${}y$). The surjectivity means that for every ${}y\in M$ there exists at least one solution

${}x\in L\,$

for this equation, the injectivity means that for every ${}y\in M$ there exist at most one solution ${}x\in L$ for this equation, and the bijectivity means that for every ${}y\in M$ there exists exactly one solution ${}x\in L$ for this equation. Hence surjectivity means the existence of solutions, injectivity means the uniqueness of solutions. Both questions are everywhere in mathematics and they also can be interpreted as surjectivity or injectivity of suitable mappings.

Definition

Let ${}F\colon L\rightarrow M$ denote a bijective mapping. Then the mapping

$G\colon M\longrightarrow L$

which sends every element ${}y\in M$ to the uniquely determined element ${}x\in L$ with ${}F(x)=y$,

is called the inverse mapping of ${}F$.

Definition

Let ${}L,\,M$ and ${}N$ denote sets, let

$F\colon L\longrightarrow M,x\longmapsto F(x),$

and

$G\colon M\longrightarrow N,y\longmapsto G(y),$

be mappings. Then the mapping

$G\circ F\colon L\longrightarrow N,x\longmapsto G(F(x)),$

is called the composition of the mappings

${}F$ and ${}G$.

So we have

${}(G\circ F)(x):=G(F(x))\,$

where the left hand side is defined by the right hand side. If both mappings are given by functional expressions, then the composition is realized by plugging in the first term into the variable of the second term (and to simplify the expression if possible).

Lemma

Let ${}L,M,N$ and ${}P$ be sets and let

$F\colon L\longrightarrow M,x\longmapsto F(x),$

$G\colon M\longrightarrow N,y\longmapsto G(y),$

and

$H\colon N\longrightarrow P,z\longmapsto H(z),$

be mappings. Then

${}H\circ (G\circ F)=(H\circ G)\circ F\,$

holds.

Proof

See exercise.

$\Box$