Operations on Functions – Foundations of Mathematics

Set Operations on Functions

Functions are sets, so we can try to combine them like we combine sets. That is, we can ask the following questions:

Is the complement of a function necessarily a function?
Is the intersection of two functions necessarily a function?
Is the union of two functions necessarily a function?
Is the set product of two functions necessarily a function?

Let's investigate the first three; the last one I'll leave for homework.

To start with, let's pick two functions and run with them. How about: $f:x\mapsto x+1$ and $g:t\mapsto t^2$ .

The complement of $g$ is $g^c=\left\{(x,y)\middle\vert y\neq x^2\right\}$ , shown here in hatching:That's definitely not a function: it badly fails the vertical line test.

What about intersection?

The intersection is just two points; so $f\cap g$ is not a function from $\mathbb{R}$ to $\mathbb{R}$ . But $f\cap g$ is a function from a smaller set.

Let's look at $f\cup g$ :

It also fails the vertical line test. But:

The Pasting Lemma (in the category of sets). Let $f:X\rightarrow Y$ and $g:A\rightarrow B$ be two functions. Then $f\cup g:X\cup A\rightarrow Y\cup B$ if and only if $f|_{A\cap X}=g|_{A\cap X}$ .

Proof. This is a biconditional, so we have two directions:

( $\Leftarrow$ ) Assume $f|_{A\cap X}=g|_{A\cap X}$ . We need to show $f\cup g$ is a function; to do this, there are two clauses.

(clause 1: domain) Let $t\in X\cup A$ . Then either $t\in X$ or $t\in A$ .

If $t\in X$ , then because $f:X\rightarrow Y$ , $\exists y\in Y: (t,y)\in f$ . Then $(t,y)\in f\cup g$ .

If $t\in A$ , then because $g:A\rightarrow B$ , $\exists b\in Y: (t,b)\in g$ . Then $(t,b)\in f\cup g$ .

In either case, there's an element of $z\in Y\cup B$ so that $(t,z)\in f\cup g$ . That's clause 1 of the definition of function.

(clause 2: unambiguousness) Let $t\in X\cup A$ and $z_1,z_2\in Y\cup B$ be such that $(t,z_1)\in f\cup g$ and $(t,z_2)\in f\cup g$ . There are four cases:

If $(t,z_1)\in f$ and $(t,z_2)\in f$ , then the fact that $f$ is a function implies $z_1=z_2$ .

If $(t,z_1)\in g$ and $(t,z_2)\in g$ , then the fact that $g$ is a function implies $z_1=z_2$ .

If $(t,z_1)\in f$ and $(t,z_2)\in g$ , then we have $t\in \operatorname{Domain}(f)=X$ and $t\in\operatorname{Domain}(g)=A$ , so $t\in X\cap A$ . But then $z_1=f(t)=f|_{X\cap A}(t)=g|_{X\cap A}(t)$ . So $(t,z_1)\in g|_{X\cap A}\subseteq g$ . So $(t,z_2)\in g$ . Since $g$ is a function, $z_1=z_2$ .

If $(t,z_1)\in g$ and $(t,z_2)\in f$ , then we have $t\in \operatorname{Domain}(f)=X$ and $t\in\operatorname{Domain}(g)=A$ , so $t\in X\cap A$ . But then $z_2=f(t)=f|_{X\cap A}(t)=g|_{X\cap A}(t)$ . So $(t,z_2)\in g|_{X\cap A}\subseteq g$ . So $(t,z_1)\in g$ . Since $g$ is a function, $z_1=z_2$ .

In any of these four cases, $z_1=z_2$ , which is what we needed for clause 2 of the definition of function.

( $\Rightarrow$ ) In this direction, we need to show two functions are equal. So we should probably use the TAWFAE. I'll leave this direction to you.

Why does this theorem bear such a silly name? Consider this diagram, which tells you how to build a cube from a piece of paper. In order to attach the sides, you have to paste the red tab to the back of one of the appropriate square (I've indicated where the red tab gets attached by coloring it green). We won't succeed in pasting unless the red tab and the green target match up.

That's what the condition $f|_{X\cap A}=g|_{X\cap A}$ ensures: that the functions $f$ and $g$ agree on the overlap of their domains.

Again, an example from precalculus mathematics: when we define a function piecewise, like

$h(x)=\begin{cases}x^2 & \text{ if } x\leq 3\\ -x+1&\text{ if } x>3\end{cases}$

we usually want to make sure that the two pieces have nonoverlapping domains. This corresponds, in the Theorem above, to the case that $X\cap A=\varnothing$ . If we weren't so careful, we might have a situation like this:

$h(x)=\begin{cases}x^2 & \text{ if } x\leq 3\\ -x+1&\text{ if } x>1\end{cases}$

where it's ambiguous what $h(2)$ is:

Composition of Functions

Because functions are relations, we can consider their composites. We have the following nice theorem:

The Composition of Functions Is a Function. If $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ , then $g\circ f:X\rightarrow Z$ .

Proof. There are two things to show:

(clause 1: domain) Let $x\in X$ . Then, because $f$ is a function, $\exists y\in Y:(x,y)\in f$ . Since $y\in Y$ and $g$ is a function, $\exists z\in Z:(y,z)\in g$ . Then $(x,z)\in g\circ f$ . $\Box$ .

(clause 2: unambiguousness) Given $x\in X, z_1,_2\in Z$ so that $(x,z_1)\in g\circ f$ and $(x,z_2)\in g\circ f$ . We need to show $z_1=z_2$ .

Since $(x,z_1)\in g\circ f$ , there is some $y_1\in Y$ with $(x,y_1)\in f$ and $(y_1,z_1)\in g$ . We also have $y_2\in Y$ with $(x,y_2)\in f$ and $(y_2,z_2)\in g$ .

Since $f$ is a function, $y_1=y_2$ . So we have $(y_1,z_2)\in g$ . But since $g$ is a function, $(y_1,z_2)\in g$ and $(y_1,z_1)\in g$ forces $z_1=z_2$ . $\Box$ .

Important Formula. If $f$ and $g$ are functions, so that $g\circ f$ is a function, then $(g\circ f)(x)=g(f(x))$ .

Proof. What does it mean for $z=(g\circ f)(x)$ ? It means $(x,z)\in g\circ f$ . But that means $\exists y: (x,y)\in f$ and $(y,z)\in g$ . So $y=f(x)$ and $z=g(y)$ . By substituting, we obtain $z=g(f(x))$ . $\Box$

This formula explains the "backwards" looking choice of how we write compositions: even though $f$ come first, we write $g\circ f$ . The only way out of this would be to switch our function notation to something like $(x)f$ , so that the composite would be $((x)f)g$ . (Some people do this, and it has a name: reverse Polish notation. But most normal people don't do it.)