8  Background: Functions

A function from a set $A$ to a set $B$ is a way of associating elements of $A$ with unique elements of $B$. Formally, a function is a special type of relation:

Definition 8.1 (Function) A function $f$ from $A$ to $B$ is a binary relation on $A$ and $B$ (i.e., $f\subseteq A\times B$) such that for all $a\in A$, there exists a unique $b\in B$ such that $(a,b)\in f$. We write $f:A\to B$ when $f$ is a function, and if $(a,b)\in f$, then write $f(a)=b$.

Suppose that $A=\{1,2,3\}$ and $B=\{a,b\}$. Examples of relations that are functions include:

• $f_1=\{(1,a),(2,a),(3,b)\}$. We write $f_1(1)=a,f_1(2)=a$, and $f_1(3)=b$
• $f_2=\{(1,a),(2,a),(3,a)\}$. We write $f_2(1)=a,f_2(2)=a$, and $f_2(3)=a$
• $f_3=\{(1,a),(3,b)\}$. We write $f_3(1)=a$ and $f_3(3)=b$

An example of a relation that is not a function is $R=\{(1,a),(1,b),(3,b)\}$.

When using functions, we often employ the following terminology and notation:

Definition 8.2 (Domain and Codomain) Suppose $f:A\to B$ is a function. The set $A$ is called the domain of $f$, and $B$ is called the codomain of $f$.

Definition 8.3 (Image and Range) Suppose $f:A\to B$ is a function. The image of a set $X\subseteq A$ is the set: $$f(X)=\{b|b=f(a)\text{ for some }a\in X\}.$$ The range of $f$ is the image of its domain.

For example, suppose that $A=\{a,b,c,d\}$ and $f:A\to \mathbb{N}$ is the function where $f(a)=1$, $f(b)=1$, $f(c)=2$ and $f(d)=4$. Then, we have the following:

• The domain of $f$ is $A$
• The codomain of $f$ is $\mathbb{N}$
• The range of $f$ is $\{1,2\}$
• The image of $\{a,b\}$ is $f(\{a,b\})=\{1\}$

In many situations, we need to apply one function to the output of another function. More formally, when the codomain of one function is the same as the domain of another function, we can compose these functions to create a new function:

Definition 8.4 (Composition of functions) Suppose that $f:A\to B$ and $g:B\to C$. The composition of $f$ with $g$ is the function $(g\circ f):A\to C$ defined as follows: for all $a\in A$, $g\circ f(a)=g(f(a))$

For example, suppose $A=\{a,b,c,d\}$ and $f:A\to \mathbb{N}$ is the function where $f(a)=1$, $f(b)=1$, $f(c)=2$, and $f(d)=4$. Let $g$ be the function $g:\mathbb{N}\to \mathbb{N}$ defined by $g(n)=2n+1$ for all $n\in \mathbb{N}$. Then the composition $(g\circ f):A\to \mathbb{N}$ is the function where:

• $(g\circ f)(a)=g(f(a))=g(1)=3$,
• $(g\circ f)(b)=g(f(b))=g(1)=3$,
• $(g\circ f)(c)=g(f(c))=g(2)=5$,
• $(g\circ f)(d)=g(f(d))=g(4)=7$,

8.1 Exercises

1. Suppose that $X=\{a,b,c\}$ and $u:X\to \mathbb{R}$ with $u(a)=0.5$, $u(b)=1.0$, $u(c)=2.0$.

   1. Consider the function $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=2x+5$. What is $f\circ u$?
   2. Consider the function $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=x^2$. What is $f\circ u$?
   3. Consider the function $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=-10x$. What is $f\circ u$?

2. In rational choice theory, we will often consider functions with domain and/or codomains that are powersets of a set. For example, suppose that $X=\{a,b,c\}$. A function from non-empty subsets of $X$ to non-empty subsets of $X$ is denoted $f:(\mathrm{\wp }(X)\setminus \mathrm{\varnothing })\to (\mathrm{\wp }(X)\setminus \mathrm{\varnothing })$. An example of such a function is: $$\begin{array}{rl}f(\{a\})& =\{b\}\\ f(\{b\})& =\{b\}\\ f(\{c\})& =\{c\}\\ f(\{a,b\})& =\{a\}\\ f(\{a,c\})& =\{b\}\\ f(\{b,c\})& =\{b\}\\ f(\{a,b,c\})& =\{b,c\}\end{array}$$ Does this function satisfy the following constraint: for all $Y\in \mathrm{\wp }(X)-\mathrm{\varnothing }$, $f(Y)\subseteq Y$? If so, explain why. If not, explain why it fails the constraint and find a function that satisfies the constraint.

Solutions

1. Suppose that $X=\{a,b,c\}$ and $u:X\to \mathbb{R}$ with $u(a)=0.5$, $u(b)=1.0$, $u(c)=2.0$.

   1. Consider the function $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=2x+5$. What is $f\circ u$?

      • $f\circ u(a)=f(u(a))=f(0.5)=2\ast 0.5+5=6.0$
      • $f\circ u(b)=f(u(b))=f(1.0)=2\ast 1.0+5=7.0$
      • $f\circ u(c)=f(u(c))=f(2.0)=2\ast 2.0+5=9.0$

   2. Consider the function $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=x^2$. What is $f\circ u$?

      • $f\circ u(a)=f(u(a))=f(0.5)={0.5}^2=0.25$
      • $f\circ u(b)=f(u(b))=f(1.0)={1.0}^2=1.0$
      • $f\circ u(c)=f(u(c))=f(2.0)={2.0}^2=4.0$

   3. Consider the function $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=-10x$. What is $f\circ u$?

2. In rational choice theory, we will often consider functions with domain and/or codomains that are powersets of a set. For example, suppose that $X=\{a,b,c\}$. A function from non-empty subsets of $X$ to non-empty subsets of $X$ is denoted $f:(\mathrm{\wp }(X)\setminus \mathrm{\varnothing })\to (\mathrm{\wp }(X)\setminus \mathrm{\varnothing })$. An example of such a function is: $$\begin{array}{rl}f(\{a\})& =\{b\}\\ f(\{b\})& =\{b\}\\ f(\{c\})& =\{c\}\\ f(\{a,b\})& =\{a\}\\ f(\{a,c\})& =\{b\}\\ f(\{b,c\})& =\{b\}\\ f(\{a,b,c\})& =\{b,c\}\end{array}$$ Does this function satisfy the following constraint: for all $Y\in \mathrm{\wp }(X)-\mathrm{\varnothing }$, $f(Y)\subseteq Y$? If so, explain why. If not, explain why it fails the constraint and find a function that satisfies the constraint.

   The above function does not satisfy this constraint since, for instance, $f(\{a\})=\{b\}⊈\{a\}$ (we also have that $f(\{a,c\})=\{b\}⊈\{a,c\}$). An example of a function that satisfies the above constraint is:

$$\begin{array}{rl}f(\{a\})& =\{a\}\\ f(\{b\})& =\{b\}\\ f(\{c\})& =\{c\}\\ f(\{a,b\})& =\{a\}\\ f(\{a,c\})& =\{c\}\\ f(\{b,c\})& =\{b\}\\ f(\{a,b,c\})& =\{b,c\}\end{array}$$