109 lines
5.8 KiB
Markdown
109 lines
5.8 KiB
Markdown
# Maps
|
|
|
|
## Definition
|
|
|
|
> *Definition*: a relation $f$ from a set $A$ to a set $B$ is called a map or function from $A$ to $B$ if for each $a \in A$ there is one and only one $b \in B$ with $afb$.
|
|
>
|
|
> * To indicate that $f$ is a map from $A$ to $B$ we may write $f:A \to B$.
|
|
> * If $a \in A$ and $b \in B$ is the unique element with $afb$ then we may write $b=f(a)$.
|
|
> * The set of all maps from $A$ to $B$ is denoted by $B^A$.
|
|
> * A partial map $f$ from a $A$ to $B$ with the property that for each $a \in A$ there is at most one $b \in B$ with $afb$.
|
|
|
|
For example, let $f: \mathbb{R} \to \mathbb{R}$ with $f(x) = \sqrt{x}$ for all $x \in \mathbb{R}$ is a partial map, since not all of $\mathbb{R}$ is mapped.
|
|
|
|
<br>
|
|
|
|
> *Proposition*: let $f: A \to B$ and $g: B \to C$ be maps, then the composition $g$ after $f$: $g \circ f = f;g$ is a map from $A$ to $C$.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
Let $a \in A$ then $g(f(a))$ is an element in $C$ in relation $f;g$ with $a$. If $c \in C$ is an element in $C$ that is in relation $f;g$ with $a$, then there is a $b \in B$ with $afb$ and $bgc$. But then, as $f$ is a map, $b=f(a)$ and as $g$ is a map $c=g(b)$. Hence $c=g(b)=g(f(a))$ is the unique element in $C$ which is in relation $g \circ f$ with $a$.
|
|
|
|
<br>
|
|
|
|
> *Definition*: Let $f: A \to B$ be a map.
|
|
>
|
|
> * The set $A$ is called the *domain* of $f$ and the set $B$ the *codomain*.
|
|
> * If $a \in A$ then the element $b=f(a)$ is called the image of $a$ under $f$.
|
|
> * The subset of $B$ consisting of the images of the elements of $A$ under $f$ is called the image or range of $f$ and is denoted by $\text{Im}(f)$.
|
|
> * If $a \in A$ amd $b=f(a)$ then the element $a$ is called a pre-image of $b$. The set of all pre-images of $b$ is denoted by $f^{-1}(b)$.
|
|
|
|
Notice that $b$ can have more than one pre-image. Indeed if $f: \mathbb{R} \to \mathbb{R}$ is given by $f(x) = x^2$ for all $x \in \mathbb{R}$, then both $-2$ and $2$ are pre-images of $4$.
|
|
|
|
If $A'$ is a subset of $A$ then the image of $A'$ under $f$ is the set $f(A') = \{f(a) \;|\; a \in A'\}$, so $\text{Im}(f) = f(A)$.
|
|
|
|
If $B'$ is a subet of $B$ then the pre-image of $B'$, denoted by $f^{-1}(B')$ is the set of elements $a$ from $A$ that are mapped to an element $b$ of $B'$.
|
|
|
|
<br>
|
|
|
|
> *Theorem*: let $f: A \to B$ be a map.
|
|
>
|
|
> * If $A' \subseteq A$, then $f^{-1}(f(A')) \supseteq A'$.
|
|
> * If $B' \subseteq B$, then $f(f^{-1}(B')) \subseteq B'$.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
Let $a' \in A'$, then $f(a') \in f(A')$ and hence $a' \in f^{-1}(f(A'))$. Thus $A' \subseteq f^{-1}(f(A'))$.
|
|
|
|
Let $a \in f^{-1}(B')$, then $f(a) \in B'$. Thus $f(f^{-1}(B')) \subseteq B'$.
|
|
|
|
## Special maps
|
|
|
|
> *Definition*: let $f: A \to B$ be a map.
|
|
>
|
|
> * $f$ is called **surjective**, if for each $b \in B$ there is at least one $a \in A$ with $b = f(a)$. Thus $\text{Im}(f) = B$.
|
|
> * $f$ is called **injective** if for each $b \in B$, there is at most one $a$ with $f(a) = b$.
|
|
> * $f$ is called **bijective** if it is both surjective and injective. So, if for each $b \in B$ there is a unique $a \in A$ with $f(a) = b$.
|
|
|
|
For example the map $\sin: \mathbb{R} \to \mathbb{R}$ is not surjective nor injective. The map $\sin: [-\frac{\pi}{2},\frac{\pi}{2}] \to \mathbb{R}$ is injective but not surjective and the map $\sin: \mathbb{R} \to [-1,1]$ is surjective but not injective. To conclude the map $\sin: [-\frac{\pi}{2},\frac{\pi}{2}] \to [-1,1]$ is a bijective map.
|
|
|
|
<br>
|
|
|
|
> *Theorem*: let $A$ be a set of size $n$ and $B$ a set of size $m$. Let $f: A \to B$ be a map between the sets $A$ and $B$.
|
|
>
|
|
> * If $n < m$ then $f$ can not be surjective.
|
|
> * If $n > m$ then $f$ can not be injective.
|
|
> * If $n = m$ then $f$ is injective if and only if it is surjective.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
Think of pigeonholes. (Not really a proof).
|
|
|
|
<br>
|
|
|
|
> *Proposition*: let $f: A \to B$ be a bijection. Then for all $a \in A$ and $b \in B$ we have $f^{-1}(f(a)) = a$ and $f(f^{-1}(b)) = b$. In particular, $f^{-1}$ is the inverse of $f$.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
Let $a \in A$. Then $f^{-1}(f(a)) = a$ by definition of $f^{-1}$. If $b \in B$ then by surjectivity of $f$ there is an $a \in A$ with $b = f(a)$. So, by the above $f(f^{-1}(b)) = f(f^{-1}(f(a))) = f(a) = b$.
|
|
|
|
<br>
|
|
|
|
> *Theorem*: let $f: A \to B$ and $g: B \to C$ be two maps.
|
|
>
|
|
> 1. If $f$ and $g$ are surjective then so is $g \circ f$.
|
|
> 2. If $f$ and $g$ are injective then so is $g \circ f$.
|
|
> 3. If $f$ and $g$ are bijective then so is $g \circ f$.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
1. Suppose $f$ and $g$ are surjective, let $c \in C$. By surjectivity of $g$ there is a $b \in B$ with $g(b) = c$. Since $f$ is surjective there is also an $a \in A$ with $f(a) = b$. Therefore $g \circ f(a) = g(f(a)) = g(b) = c$.
|
|
2. Suppose $f$ and $g$ are injective, let $a,a' \in A$ with $g \circ f(a) = g \circ f(a')$. Then $g(f(a)) = g(f(a'))$ and by injectivity of $g$ we find $f(a) = f(a')$. Injectivity of $f$ implies $a = a'$.
|
|
3. Proofs 1. and 2. imply 3. by definition of bijectivity.
|
|
|
|
<br>
|
|
|
|
> *Proposition*: if $f: A \to B$ and $g: B \to A$ are maps with $f \circ g = I_B$ and $g \circ f = I_A$, where $I_A$ and $I_B$ denote the identity maps on $A$ and $B$, respectively. Then $f$ and $g$ are bijections and $f^{-1} = g$ and $g^{-1} = f$.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
Suppose $f A \to B$ and $g: B \to A$ are maps with $f \circ g = I_B$ and $g \circ f = I_A$. Let $b \in B$ then $f(g(b)) = b$, thus $f$ is surjective. If $a,a' \in A4 with $f(a) = f(a')$, then $a = g(f(a)) = g(f(a')) = a' and hence $f$ is injective. Therefore $f$ is bijective and by symmetry $g$ is also bijective.
|
|
|
|
<br>
|
|
|
|
> *Proposition*: suppose $f: A \to B$ and $g: B \to C$ are bijective maps. Then the inverse of the map $g \circ f$ equals $f^{-1} \circ g^{-1}$.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
Suppose $f: A \to B$ and $g: B \to C$ are bijective maps. Then for all $a \in A$ we have $(f^{-1} \circ g^{-1}) (g \circ f)(a) = f^{-1}(g^{-1}(g(f(a)))) = f^{-1}(f(a)) = a$.
|
|
|