---
jupytext:
formats: md:myst
text_representation:
extension: .md
format_name: myst
kernelspec:
display_name: Python 3
language: python
name: python3
---
# 📖 Mappings and cardinality
⏱ | words
```{admonition} Definition
:class: caution
A generic mapping $f$ from $A$ to $B$ is a rule that assigns elements $x$ of a set $A$ to elements of a set $B$. We write
:::{math}
f: A \to B \qquad\text{ or }\qquad f: A \ni x \mapsto f(x) \in B
:::
```
There are four basic **types of mappings**:
1. A one-to-one mapping:
- $\forall x \in X$ there is at most one $f(x) \in Y$; and
- $\forall y \in Y$ there is at most one $x \in X$ such that $f(x)=y$.
- example: $f(x) = x$
2. A many-to-one mapping:
- $\forall x \in X$ there is at most one $f(x) \in Y$; but
- $\exists y \in Y$ for which $\exists x_1 \ne x_2 \in X$ such that $f(x_1)=f(x_2)=y$.
- example: $f(x) = x^2$
3. A one-to-many mapping:
- $\exists x \in X$ for which $\exists y_1 \ne y_2 \in f(x) \subset Y$; but
- $\forall y \in Y$ there is at most one $x \in X$ such that $f(x)=y$.
- example: $f(x) = \{e^x,-e^x\}$
4. A many-to-many mapping:
- $\exists x \in X$ for which $\exists y_1 \ne y_2 \in f(x) \subset Y$; but
- $\exists y \in Y$ for which $\exists x_1 \ne x_2 \in X$ such that $f(x_1)=f(x_2)=y$.
- example: $f(x) = \{x,x+1,x+2,\dots\}$
Mappings of the first two types are referred to as **functions**. Mappings of the last two types are referred to as **set-valued functions** or **correspondences**.
(ref-functions)=
## Functions
```{admonition} Definition
:class: caution
A **function** $f: A \rightarrow B$ from set $A$ to set $B$ is a mapping that
associates to *each element* of $A$ a *uniquely determined* element of $B$.
```
- typically functions map $A$ to a (Cartesian product of) set(s) of real numbers $\mathbb{R}^n$
```{admonition} Example
:class: tip
- `Each student gets a set of textbooks` is a mapping
- `Each student gets a grade between 0 and 100` is a function
```
```{figure} _static/plots/function.png
:name: function
```
```{admonition} Definition
:class: caution
$A$ is called the **domain** of $f$ and $B$ is called the **co-domain**
```
```{figure} _static/plots/allfunctions.png
:name: function_non_function
:scale: 50%
```
- lower panel: functions have to map *all* elements in domain to a *uniquely determined* element in co-domain
```{admonition} Example
:class: tip
:::{math}
f(x) = \exp(-x^2)
:::
is a function from $\mathbb{R}$ to $\mathbb{R}$.
We may also write
:::{math}
f: \mathbb{R} \to \mathbb{R} \\
x \mapsto \exp(-x^2), \text{ or}\\
f: \mathbb{R} \ni x \mapsto \exp(-x^2) \in \mathbb{R}
:::
```
```{admonition} Definition
:class: caution
Functions can be:
- *scalar-valued* when $n=1$, so $f: A \to \mathbb{R}$
- *vector-valued* when $n>1$, so $f: A \to \mathbb{R}^n$
- *univariate* when $A = \mathbb{R}$, so $f: \mathbb{R} \to \mathbb{R}^n$
- *multivariate* when $A = \mathbb{R}^m$, so $f: \mathbb{R}^m \to \mathbb{R}^n$
```
````{admonition} Example: not a function
:class: tip
```{figure} _static/plots/xy_not_function.png
:name: xy_non_func
:scale: 60%
```
````
```{admonition} Definition
:class: caution
For each $a \in A$, $f(a) \in B$ is called the **image of $a$** under $f$
```
```{admonition} Definition
:class: caution
If $f(a) = b$ then $a$ is called a **pre-image of $b$** under $f$
```
```{admonition} Definition
:class: caution
The definitions of image and pre-image naturally generalize to subsets of the domain.
- For each $X \subset A$, $f(X) = \{f(x): x \in X\} \in B$ is called the **image of $X$** under $f$
- For each $Y \subset B$, $\{x: f(x) \in Y\} \in A$ is called the **pre-image of $Y$** under $f$
```
```{figure} _static/plots/image_and_preimage.png
:name: pre-image
:scale: 100%
```
Each point in $B$ can have one, many or zero pre-images
The co-domain of a function is not uniquely pinned down
```{admonition} Example
:class: tip
Consider the mapping defined by
$f(x) = \exp(-x^2)$
All of these statements are valid:
- $f$ a function from $\mathbb{R}$ to $\mathbb{R}$
- $f$ a function from $\mathbb{R}$ to $(0, \infty)$
- $f$ a function from $\mathbb{R}$ to $(0, 1]$
```
```{admonition} Definition
:class: caution
The smallest possible co-domain is called the **range** of $f: A \to B$:
```
$$
\mathrm{rng}(f) := \{ b \in B : f(a) = b \text{ for some } a \in A \}
$$
```{figure} _static/plots/range.png
:name: range
:scale: 50%
```
```{admonition} Example
:class: tip
Let $f: [-1, 1] \to \mathbb{R}$ be defined by
%
$$
f(x) = 0.6 \cos(4 x) + 1.4
$$
Then $\mathrm{rng}(f) = [0.8, 2.0]$
```
```{figure} _static/plots/range2.png
:name: range2
```
```{admonition} Example
:class: tip
If $ f: [0, 1] \to \mathbb{R}$ is defined by
%
$$
f(x) = 2x
$$
then $\mathrm{rng}(f) = [0, 2]$
```
```{admonition} Example
:class: tip
If $f: \mathbb{R} \to \mathbb{R}$ is defined by
%
$$
f(x) = \exp(x)
$$
then $\mathrm{rng}(f) = (0, \infty)$
```
## Compositions
```{admonition} Definition
:class: caution
The **composition** of $f: A \to B$ and $g: B \to C$ is the
function $g \circ f$ from $A$ to $C$ defined by
%
$$
(g \circ f)(a) = g(f(a)) \quad (a \in A)
$$
```
```{figure} _static/plots/composition.png
:name: composition
```
```{admonition} Example
:class: tip
Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x^2$ and $g: \mathbb{R} \to \mathbb{R}$ be defined by $g(x) = x + 1$
Then $(g \circ f)(x) = g(f(x)) = g(x^2) = x^2 + 1$
Note that $(f \circ g)(x) = f(g(x)) = f(x+1) = (x+1)^2 \ne (g \circ f)(x)$
```
- Order of components in a composite function matters
- The domain of the outer function in a composition must contain the range of the inner function
## Onto (Surjections)
```{admonition} Definition
:class: caution
A function $f: A \to B$ is called **onto** (or surjection) if every element of $B$
is the image under $f$ of at least one point in $A$.
```
Equivalently, $\mathrm{rng}(f) = B$
```{figure} _static/plots/function1.png
:name: function1
:scale: 50%
```
```{admonition} Fact
:class: important
$f: A \to B$ is onto if and only if each element of $B$
has at least one pre-image under $f$
```
```{figure} _static/plots/bijection3.png
:name: bijection3
:scale: 50%
Onto (surjection)
```
```{figure} _static/plots/function3.png
:name: function3
:scale: 50%
Not *onto*!
```
```{figure} _static/plots/bijection2.png
:name: bijection22
:scale: 50%
Not *onto*!
```
```{admonition} Example
:class: tip
The function $f: \mathbb{R} \to \mathbb{R}$ defined by
%
$$
f(x) = ax^3 + b x^2 + cx + d
$$
%
is onto whenever $a \ne 0$
```
To see this pick any $y \in \mathbb{R}$
We claim $\exists \; x \in \mathbb{R}$ such that $f(x) = y$
Equivalent:
%
$$
\exists \; x \in \mathbb{R} \; \mathrm{s.t.} \;
ax^3 + b x^2 + cx + d - y = 0
$$
```{admonition} Fact
:class: important
Every cubic equation with $a \ne 0$ has at least one real root
```
```{figure} _static/plots/cubic.png
:name: cubic
Cubic functions from $\mathbb{R}$ to $\mathbb{R}$ are always onto
```
## One-to-One (Injections)
```{admonition} Definition
:class: caution
A function $f: A \to B$ is called **one-to-one** (or injection) if distinct
elements of $A$ are always mapped into distinct elements of $B$.
```
That is, $f$ is one-to-one if
$$
a \in A, \; a' \in A \text{ and } a \ne a'
\implies f(a) \ne f(a')
$$
Equivalently,
$$
f(a) = f(a') \implies a = a'
$$
```{admonition} Fact
:class: important
$f: A \to B$ is one-to-one if and only if each element of $B$
has at most one pre-image under $f$
```
```{figure} _static/plots/bijection2.png
:name: bijection2
:scale: 50%
One-to-one
```
```{figure} _static/plots/bijection3.png
:name: bijection3b
:scale: 50%
One-to-one
```
```{figure} _static/plots/bijection1.png
:name: bijection1
:scale: 50%
Not one-to-one
```
## Bijections
```{admonition} Definition
:class: caution
A function that is
%
1. one-to-one (injection) and
9. onto (surjection)
%
is called a **bijection** or **one-to-one correspondence**
```
```{figure} _static/plots/bijection3.png
:name: bijection3a
:scale: 50%
```
```{admonition} Fact
:class: important
$f: A \to B$ is a bijection if and only if each $b \in B$ has one and only one pre-image in $A$
```
```{admonition} Example
:class: tip
$x \mapsto 2x$ is a bijection from $\mathbb{R}$ to $\mathbb{R}$
```
```{figure} _static/plots/x_to_2x.png
:name: x_to_2x
```
```{admonition} Example
:class: tip
$k \mapsto -k$ is a bijection from $\mathbb{Z}$ to $\mathbb{Z}$
```
```{figure} _static/plots/k_to_minus_k.png
:name: k_to_minus_k
```
```{admonition} Example
:class: tip
$x \mapsto x^2$ is **not** a bijection from $\mathbb{R}$ to $\mathbb{R}
$
```
```{figure} _static/plots/x_squared.png
:name: x_squared
```
## Inverse functions
```{admonition} Fact
:class: important
If $f: A \to B$ a bijection, then there exists a unique
function $\phi: B \to A$ such that
%
$$
\phi(f(a)) = a, \quad \forall \; a \in A
$$
That function $\phi$ is called the **inverse** of $f$ and written $f^{-1}$
```
```{figure} _static/plots/bijec.png
:name: bijec
```
```{admonition} Example
:class: tip
Let
%
- $f: \mathbb{R} \to (0, \infty)$ be defined by $f(x) = \exp(x) :=
e^x$
- $\phi: (0, \infty) \to \mathbb{R}$ be defined by $\phi(x) = \log(x)$
Then $\phi = f^{-1}$ because, for any $a \in \mathbb{R}$,
%
$$
\phi(f(a)) = \log(\exp(a)) = a
$$
```
```{admonition} Fact
:class: important
If $f: A \to B$ is one-to-one, then $f: A \to \mathrm{rng}(f)$ is a bijection
```
```{admonition} Fact
:class: important
Let $f: A \to B$ and $g: B \to C$ be bijections
%
1. $f^{-1}$ is a bijection and its inverse is $f$
- $f^{-1}(f(a)) = a$ for all $a \in A$
- $f(f^{-1}(b)) = b$ for all $b \in B$
- $g \circ f$ is a bijection from $A$ to $C$ and $(g \circ f)^{-1}
= f^{-1} \circ g^{-1}$
%
```
```{figure} _static/plots/bij_inv.png
:name: bij_inv
Illustration of $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$
```
(ref-cardinality)=
## Cardinality
If a bijection exists between sets $A$ and $B$ they are said to have the **same cardinality**, and we write $|A| = |B|$
```{admonition} Fact
:class: important
If $|A| = |B|$ and $A$ and $B$ are finite then $A$ and $B$ have the same number of elements (same cardinality).
```
**Exercise:** Convince yourself this is true
Hence "same cardinality" is analogous to "same size"
- But cardinality applies to infinite sets as well!
```{admonition} Fact
:class: important
If $|A| = |B|$ and $|B| = |C|$ then $|A| = |C|$
```
````{admonition} Proof
:class: dropdown
- Since $|A| = |B|$, there exists a bijection $f: A \to B$
- Since $|B| = |C|$, there exists a bijection $g: B \to C$
Let $h := g \circ f$
Then $h$ is a bijection from $A$ to $C$
Hence $|A| = |C|$
````
```{admonition} Definition
:class: caution
A nonempty set $A$ is called **finite** if
%
$$
|A| = |\{1, 2, \ldots, n\}|
\quad \text{ for some } \quad
n \in \mathbb{N}
$$
Otherwise called **infinite**
```
```{admonition} Definition
:class: caution
Sets that either are finite, or have the same cardinality as $\mathbb{N}$, denoted $|A| = \aleph_0$, are called **countable**
```
```{admonition} Fact
:class: important
A set $X$ **countable** if and only if there exists a bijection $f: X \rightarrow \mathbb{N}$.
```
```{admonition} Example
:class: tip
$-\mathbb{N} := \{\ldots, -4, -3, -2, -1\}$ is countable
:::{math}
\begin{array}{ccc}
-1 & \leftrightarrow & 1 \\
-2 & \leftrightarrow & 2 \\
-3 & \leftrightarrow & 3 \\
& \vdots & \\
-n & \leftrightarrow & n \\
& \vdots &
\end{array}
:::
```
Formally: $f(k) = -k$ is a bijection from $-\mathbb{N}$ to $\mathbb{N}$
```{admonition} Example
:class: tip
$E := \{2,4,6, \ldots\}$ is countable
$$
\begin{array}{ccc}
2 & \leftrightarrow & 1 \\
4 & \leftrightarrow & 2 \\
6 & \leftrightarrow & 3 \\
& \vdots & \\
2n & \leftrightarrow & n \\
& \vdots &
\end{array}
$$
Formally: $f(k) = k/2$ is a bijection from $E$ to $\mathbb{N}$
```
```{admonition} Fact
:class: important
Nonempty subsets of countable sets are countable
```
```{admonition} Fact
:class: important
Finite unions of countable sets are countable
```
````{admonition} Proof
:class: dropdown
Sketch of proof for $A$ and $B$ countable $\implies A \cup B$ countable.
Consider $A$ and $B$ are disjoint and infinite (the most complicated case)
By assumption, can write $A = \{a_1, a_2, \ldots\}$ and $B = \{b_1, b_2,
\ldots\}$
Now count it like so:
%
$$
\begin{matrix}
a_1 & & a_2 & & a_3 & & a_4 & \cdots\\
\downarrow & \nearrow & \downarrow & \nearrow & \downarrow & \nearrow & \downarrow & \nearrow \\
b_1 & & b_2 & & b_3 & & b_4 & \cdots
\end{matrix}
$$
````
```{admonition} Example
:class: tip
$\mathbb{Z} = \{\ldots, -2, -1\} \cup \{ 0 \} \cup \{1, 2, \ldots\}$ is countable
```
```{admonition} Fact
:class: important
Finite Cartesian products of countable sets is countable
```
````{admonition} Proof
:class: dropdown
Sketch of proof for $A$ and $B$ countable $\implies A \times B$ countable.
Consider $A$ and $B$ are disjoint and infinite (the most complicated case).
Now count like so:
%
$$
\begin{matrix}
(a_{1},b_{1})&\to &(a_{1},b_{2})& & (a_{1},b_{3})&\to\cdots\\
&\swarrow& &\nearrow & & \\
(a_{2},b_{1})& &(a_{2},b_{2})& &\cdots & \\
\downarrow &\nearrow& & & & \\
(a_{3},b_{1})& &\vdots & & & \\
\vdots & & & & &
\end{matrix}
$$
%
````
````{admonition} Example
:class: tip
$\mathbb{Z} \times \mathbb{Z} = \{ (p,q) : p \in \mathbb{Z}, q \in \mathbb{Z} \}$ is countable
```{figure} _static/plots/lattice.png
:name: lattice
```
````
```{admonition} Fact
:class: important
$\mathbb{Q}$ is countable
```
````{admonition} Proof
:class: dropdown
By definition
%
$$
\mathbb{Q}:=
\left\{ \,
\text{all } \frac{p}{q}
\text{ where } p \in \mathbb{Z} \text{ and } q \in \mathbb{N} \,
\right\}
$$
Consider the function $\phi$ defined by $\phi(p/q) = (p, q)$
- A one-to-one function from $\mathbb{Q}$ to $\mathbb{Z} \times \mathbb{N}$
- A bijection from $\mathbb{Q}$ to $\mathrm{rng}(\phi)$
Since $\mathbb{Z} \times \mathbb{N}$ is countable, so is $\mathrm{rng}(\phi) \subset \mathbb{Z} \times \mathbb{N}$
Hence $\mathbb{Q}$ is also countable
````
```{admonition} Example
:class: tip
An example of an **uncountable** set is all binary sequences
%
$$
\{0,1\}^{\mathbb{N}} := \big\{ (b_1,b_2,\ldots) : \, b_n \in \{0,1\ \} \text{
for each } n \big\}
$$
```
````{admonition} Proof
:class: dropdown
Sketch of proof: If this set were countable then it could be listed as follows:
$$
\begin{matrix}
1 & \leftrightarrow & {\bf a_1}, \; a_2, \; a_3, \; a_4, \ldots \\
2 & \leftrightarrow & b_1, \;{\bf b_2}, \; b_3, \; b_4, \ldots \\
3 & \leftrightarrow & c_1, \; c_2, \;{\bf c_3}, \; c_4, \ldots \\
4 & \leftrightarrow & d_1, \; d_2, \; d_3, \;{\bf d_4}, \ldots \\
\vdots & & \vdots
\end{matrix}
$$
Such a list is never complete: Cantor's diagonalization argument
````
Cardinality of $\{0,1\}^{\mathbb{N}}$ called the **power of the continuum**
Other sets with the power of the continuum
- $\mathbb{R}$
- $(a, b)$ for any $a < b$
- $[a, b]$ for any $a < b$
- $\mathbb{R}^N$ for any finite $N \in \mathbb{N}$
```{admonition} Continuum hypothesis
:class: important
Every nonempty subset of $\mathbb{R}$ is either
countable or has the power of the continuum
```
- [Not a homework exercise](https://en.wikipedia.org/wiki/Continuum_hypothesis)!
```{admonition} Example
:class: tip
$\mathbb{R}$ and $(-1, 1)$ have the same cardinality because $x \mapsto 2\arctan(x)/\pi$ is a bijection from $\mathbb{R}$ to $(-1, 1)$
```
```{figure} _static/plots/arctan.png
:name: arctan
Same cardinality
```
## References and further reading
```{dropdown} References
- {cite:ps}`simon1994`: 2.1, 2.2, 5.1
```
---
[Mentimeter reflection](https://www.menti.com/alcit49zwrq6)