The Analysis of Data, volume 1

Set Theory: Functions

A.2. Functions

Definition A.2.1. Let $A,B$ be two sets. A function $f:A\to B$ assigns one element $b\in B$ for every element $a\in A$, denoted by $b=f(a)$.
Definition A.2.2. For a function $f:A\to B$, we define \begin{align} \label{ap:sets:func} \text{range}\, f &= \{f(a):a\in A\}\\ f^{-1}(b) &= \{a\in A: f(a)=b\}\\ f^{-1}(H) &= \{a\in A: f(a)\in H\}. \end{align} If $\text{range}\, f=B$, we say that $f$ is onto. If for all $b\in B$, $|f^{-1}(b)|\leq 1$ we say that $f$ is 1-1 or one-to-one. A function that is both onto and 1-1 is called a bijection.

If $f:A\to B$ is one-to-one, $f^{-1}$ is also a function $f^{-1}:B'\to A$ where $B'=\text{range}\, f\subset B$. If $f:A\to B$ is a bijection then $f^{-1}:B\to A$ is also a bijection.

Definition A.2.3. Let $f:A\to B$ and $f:B\to C$ be two functions. Their function composition is a function $f\circ g:A\to C$ defined as $(f\circ g)(x)=f(g(x))$.
Proposition A.2.1. For any function $f$ and any indexed collection of sets $U_{\alpha}, \alpha\in A$, \begin{align*} f^{-1} \left(\bigcap_{\alpha\in A} U_{\alpha}\right) &= \bigcap_{\alpha\in A} f^{-1}(U_{\alpha}) \\ f^{-1} \left(\bigcup_{\alpha\in A} U_{\alpha}\right) &= \bigcup_{\alpha\in A} f^{-1}(U_{\alpha}) \\ f \left(\bigcup_{\alpha\in A} U_{\alpha}\right) &= \bigcup_{\alpha\in A} f(U_{\alpha}). \end{align*}
Proof. We prove the result above for a union and intersection of two sets. The proof of the general case of a collection of sets is similar.

If $x\in f^{-1} (U\cap V)$ then $f(x)$ is in both $U$ and $V$ and therefore $x\in f^{-1}(U) \cap f^{-1}(V)$. If $x\in f^{-1}(U) \cap f^{-1}(V)$ then $f(x)\in U$ and $f(x)\in V$ and therefore $f(x)\in U\cap V$, implying that $x\in f^{-1} (U\cap V)$.

If $x\in f^{-1} (U\cup V)$ then $f(x)\in U\cup V$, which implies $f(x)\in U$ or $f(x)\in V$ and therefore $x\in f^{-1}(U) \cup f^{-1}(V)$. On the other hand, if $x\in f^{-1}(U) \cup f^{-1}(V)$ then $f(x) \in U$ or $f(x)\in V$ implying $f(x)\in U\cup V$ and $x\in f^{-1} (U\cup V)$.

If $y\in f(U\cup V)$ then $y=f(x)$ for some $x$ in either $U$ or $V$ and $y=f(x)\in f(U)\cup f(V)$. On the other hand, if $y\in f(U)\cup f(V)$ then $y=f(x)$ for some $x$ that belongs to either $U$ or $V$, implying $y=f(x)\in f(U\cup V)$.

Interestingly, the statement $f(U\cap V) = f(U)\cap f(V)$ is not true in general.

Example A.2.1. For $f:\R\to\R$, $f(x)=x^2$, we have $f^{-1}(x)=\{\sqrt{x},-\sqrt{x}\}$ implying that $f$ is not one-to-one. We also have $f^{-1}([1,2])=[-\sqrt{2},1]\cup [1,\sqrt{2}]$.
Definition A.2.4. Given two functions $f,g:A\to\R$ we denote $f\leq g$ if $f(x)\leq g(x)$ for all $x\in A$, $f < g$ if $f(x) < g(x)$ for all $x\in A$, and $f\equiv g$ if $f(x)=g(x)$ for all $x\in A$.
Definition A.2.5. We denote a sequence of functions $f_n:A\to\R$, $n\in\mathbb{N}$ satisfying $f_1\leq f_2\leq f_3\leq \cdots$ as $f_n\nearrow$.
Definition A.2.6. Given a set $A\subset\Omega$ we define the indicator function $I_A:\Omega\to\R$ as \[I_A(\omega)=\begin{cases} 1 & \omega\in A \\ 0 & \text{otherwise}\end{cases}, \qquad \omega\in\Omega.\]
Example A.2.2. For any set $A$, we have $I_A=1-I_{A^c}$.
Example A.2.3. If $A\subset B$, we have $I_A\leq I_B$.