Functions and Sets
[callout headingicon=”noicon” textalign=”textleft” type=”basic”]All in all, those who were chained would consider nothing besides the shadows of the artifacts.
Plato, The Allegory of the Cave
[/callout]
Pushforwards and Pullbacks
A function $f:X\rightarrow Y$ gives us a way of taking elements in $X$ and pushing them over to $Y$. We call $f(x)$ the image of $x$ under $f$. In fact, we can also think of $f$ as giving a way to push a set of elements of $X$ over to $Y$.
Definition. Given $f:X\rightarrow Y$ and $A\subseteq X$, we define $f_*A=\left\{f(x)\middle\vert x\in A\right\}$. We call $f_*A$ the image of $A$ under $f$ or the pushforward of $A$ by $f$.
Notice that by definition, $f_*A$ is a subset of the target $Y$.
E.g. If $f:t\mapsto t^2$, and $A=[-2,3]$, then $f_*A=[0,9]$.
Proof. ($\Rightarrow$) Let $y\in f_*A$. Then $\exists x\in A: f(x)=y$. So $-2\leq x\leq 3$.
If $-2\leq x\leq 0$, then $y=x^2$ is between $0$ and $4$. So $y\in[0,9]$.
If $0\leq x\leq 3$, then $y=x^2$ is between $0$ and $9$. So $y\in[0,9]$.
($\Leftarrow$) Let $y\in[0,9]$. Then $0\leq y\leq 9$. Let $x=\sqrt{y}$. So $0\leq x\leq 3$. Then $f(x)=\left(\sqrt{y}\right)^2=y$. Since $0\leq x\leq 3$, $x\in[-2,3]$.
Notation. Most sources write $f(A)$ for the image of $A$ under $f$. This is not an entirely unreasonable choice, but it means that the symbol $f(A)$ has two interpretations — if $A$ is an element of $X$, then $f(A)$ is an element of $Y$; if $A$ is a subset of $X$, then $f(A)$ is a subset of $Y$. Our notation $f_*A$ is always going to be a set. But you should know, for your future mathematics courses, that $f(A)$ is a standard notation.
Theorem/Realization. If $f:X\rightarrow Y$, then $f_*:2^X\rightarrow 2^Y$.
That is, $f_*$ takes subsets of $X$ and yields subsets of $Y$.
Definition. Given $f:X\rightarrow Y$ and $B\subseteq Y$, we define $f^*B=\left\{x\middle\vert f(x)\in B\right\}$. We call $f^*B$ the preimage of $B$ under $f$ or the pullback of $B$ by $f$.
Note that $f^*B$ is a subset of the domain $X$.
E.g. If $f:\mathbb{R}\rightarrow\mathbb{R}$ is given by $t\mapsto t^2$, then $f^*((-2,-1))=\varnothing$ and $f^*([-4,4))=[0,2)$.
Theorem/Realization. If $f:X\rightarrow Y$, then $f^*:2^Y\rightarrow 2^X$.
Notation. Just like with the image, there is a standard-but-terrible notation for the preimage. Most sources write $f^{-1}(B)$ for the preimage of $B$ under $f$. This is just nutty, because the object in question doesn’t have anything to do with inverses. Nevertheless, you should expect at least once in your mathematical life to have to deal with the string of symbols $f^{-1}(B)$, where $B$ is some set. We live in a fallen world.
Theorem. Let $f:X\rightarrow Y$, $A\subseteq X$, $B\subseteq X$, $C\subseteq Y$, $D\subseteq Y$. Then
- $f_*(A\cup B)=f_*(A)\cup f_*(B)$
- $f_*(A\cap B)\subseteq f_*(A)\cap f_*(B)$
- $f^*(C\cup D)=f^*(C)\cup f^*(D)$
- $f^*(C\cap D)=f^*(C)\cap f^*(D)$
- $f^*(C^c)=\left(f^*(C)\right)^c$
Proof. This is an exercise, but it’s just an exercise in proving set equalities.
Characteristic Functions
Recall that for $S$ to be a set means that “$x\in S$” is an open sentence. We can view this in terms of functions.
Definition. Given a set $A$, the characteristic function of $A$ is the function \begin{equation*} \chi_A(x)=\begin{cases}1 &\text{ if } x\in A\\0&\text{ otherwise}\end{cases} \end{equation*}
Technically in order to define this function, we need to specify a universe for $x$ — but notice that it really doesn’t much matter, because as long as $x\notin A$, $\chi_A(x)=0$.
Exercise. If $A$ and $B$ are subsets of some common universe $U$, then for any $x\in U$, we have:
- $\chi_{A\cap B}(x)=\chi_A(x)\chi_B(x)$,
- $\chi_{A\cup B}(x)=\max\{\chi_A(x),\chi_B(x)\}$
- $\chi_{A^c}(x)=1-\chi_{A}(x)$.
Theorem. $\chi_A^*(\{1\})=A$.
This says that $A$ determines its characteristic function, and $\chi_A$ determines $A$ as well.