Functions

The type of function we will run across here most frequently is a ``permutation'', defined precisely later, which is roughly speaking a rule which mixes up and swaps around the elements of a finite set.

Let $S$ and $T$ be sets.

Definition 4.1.1   : A function $f$ from $S$ to $T$ is a rule which associates to each element $s\in S$ exactly one element $t \in T$ . We will use the following notation and terminology for this:

$$\begin{array}{c} f : S \rightarrow T \ {\rm (\lq\lq f... ... {\rm (\lq\lq t is the image of s under f'').} \end{array}$$

A function is also called a map, mapping, or transformation. We call $S$ the domain of $f$ , $T$ the codomain (or range) of $f$ , and the set

$$f(S) = \{f(s) \in T \vert s \in S\}$$

the image of f.

A wonderful tool for learning about permutations is the Rubik's cube. Erno Rubik was born during World War II in Budapest, Hungary. Far from being a mathematician, Rubik was a Professor at the Academy of Applied Arts and Design, teaching interior design. In the mid 1970's, he patented a cube-shaped mechanical puzzle that has since captured the imagination of millions of people worldwide, the Rubik's Cube. Those of you who have a Rubik's cube or similar puzzle have met permutations before. The moves are permutations!

Example 4.1.2  

• One typical example for us will be when $S$ is the set of all 54 facets of the Rubik's cube and $f$ is a rule for associating to each facet some other facet determined by a Rubik's cube move. This example will be discussed in more detail later (see §4.8.2 below).
• If $n>0$ is any natural number, recall from §1.4.5 that we let $\phi(n)$ denote the number of natural numbers less than or equal to $n$ which have no prime factor in common with $n$ . The function $\phi:{\mathbb{N}}\rightarrow {\mathbb{N}}$ is Euler's phi function. We have $\phi(1)=1$ , $\phi(2)=1$ , $\phi(3)=2$ , ... .

• If $n$ is any natural number, let $\pi(n)$ denote the number of prime numbers less than or equal to $n$ . The function $\pi:{\mathbb{N}}\rightarrow {\mathbb{N}}$ is simply called the $\pi$ function. We have $\pi(1)=0$ , $\pi(2)=1$ , $\pi(3)=2$ , ... . Though the rough asymptotic behaviour of $\pi(n)$ is known, there are still many unsolved problems regarding $\pi(n)$ . For example, the following problem is still unsolved.

  Question: Is there $n>1$ such that $\pi(n^2+2n+1)=\pi(n^2)$ (i.e., ii there always a prime between any two consecutive squares)?

• Let $f:\mathbb{Z}\rightarrow \mathbb{Z}/m\mathbb{Z}$ denote the map which sends an integer $n$ to its residue $\overline{n}=n ({\rm mod} m)$ . This ``mod $m$ function'' maps an infinite set to a finite set.

• Let $a_1,a_2,...$ denote any sequence of complex numbers. We may regard this sequence as a function $f:{\mathbb{N}}\rightarrow {\mathbb{C}}$ by $f(n)=a_n$ , $n>0$ .

The Cartesian product of two sets $S$ , $T$ is the set of pairs of elements taken from these sets:

$$S\times T=\{(s,t) \vert s\in S, t\in T\}.$$

An element of $S\times T$ is simply a list of two things, the first one from $S$ and the second one from $T$ . This construction of a new set from two given sets is named for the French philosopher René Descartes (March 1596-February 1650) whose work, La géométrie, includes his application of algebra to geometry.

Example 4.1.3   If $\mathbb{R}$ denotes the set of all real numbers then the Cartesian product $\mathbb{R}\times \mathbb{R}$ is simply the set of all pairs or real numbers. In other words, this is the Cartesian plane we are all familiar with from high school.

More generally, we may repeat this process and take the Cartesian product of the set of real numbers with itself $n$ times (where $n>1$ is any integer) to get $\mathbb{R}\times ... \times \mathbb{R}$ ($n$ times). This $n$ -fold Cartesian product is denoted more conveniently by $\mathbb{R}^n$ . An element of the set $\mathbb{R}^n$ is simply a list of $n$ real numbers. Such a list will be called a vector or an $n$ -vector to be specific.

Sometimes it is convenient to ``picture'' a function as the set of its values inside the Cartesian product $S\times T$ . The graph of a function $f : S\rightarrow T$ is the subset

$$\{ (s,f(s)) \vert s \in S\} \subset S\times T .$$

Not every subset of $S\times T$ is the graph of some function from $S$ to $T$ .

Definition 4.1.4   Let $f : S\rightarrow T$ and $g : T \rightarrow U$ be two functions. We can compose them to get another function, the composition, denoted $fg:S\rightarrow U$ :

$$\begin{array}{ccccc} x& \longmapsto& f(x)& \longmapsto& g(f(x))\\ S&\rightarrow &T&\rightarrow &U \end{array}$$

If this definition seems ``backwards'' to you, note we are not writing $f\circ g(x)$ but $f(g(x))$ .

Definition 4.1.5   If the image of the function $f : S\rightarrow T$ is all of $T$ , i.e., if $f(S) = T$ , then we call $f$ surjective (or ``onto", or say ``$f$ is a surjection"). Equivalently, a function $f$ from $S$ to $T$ is surjective if every $t \in T$ is the image of some $s\in S$ under $f$ .

For example, the map $f:\mathbb{R}\rightarrow \mathbb{R}$ defined by $f(x)=2x$ , for any real number $x$ , is surjective. Another example, let $S$ be the set of all 54 facets of the Rubik's cube. Let $f:S\rightarrow S$ be the map which sends a facet to the facet which is diametrically opposite (for instance, the upward center facet would be mapped to the downward center facet). This function is also surjective.

Definition 4.1.6   : A function $f : S\rightarrow T$ is called injective (or ``one-to-one" or say ``$f$ is an injection") if each element $t$ belonging to the image $f(S)$ is the image of exactly one $s$ in $S$ .

In other words, $f$ is an injection if the condition $f(s_1)=f(s_2)$ (for some $s_1, s_2 \in S$ ) always forces $s_1=s_2$ .

Question: Suppose that $\vert S\vert > \vert T\vert$ . Is there an injective function $f : S\rightarrow T$ ? Explain.

Definition 4.1.7   A function $f : S\rightarrow T$ is called a bijection if it is both injective and surjective.

Equivalently, a bijection from $S$ to $T$ is a function $f : S\rightarrow T$ for which each $t \in T$ is the image of exactly one $s\in S$ .

Definition 4.1.8   A set $S$ is called countable if there exists a bijection $f:S\rightarrow \mathbb{Z}$ to the set of integers $\mathbb{Z}$ .

Example 4.1.9 (a)   The set of all odd integers $S=\{...,-3,-1,1,3,...\}$ is countable since the map $f:S\rightarrow \mathbb{Z}$ defined by $f(x)=(x+1)/2$ is a bijection.

(b) Recall the set of all rational numbers is denoted by ${\mathbb{Q}}$ . The set $S$ of all rational numbers within the unit interval $0<r<1$ is countable since you can define $f:S\rightarrow \mathbb{Z}$ as follows: $f(1)=1/2$ , $f(2)=1/3$ , $f(3)=2/3$ , $f(4)=1/4$ , $f(5)=3/4$ , $f(6)=1/5$ , $f(7)=2/5$ , $f(8)=3/5$ , and so on. (There are $\phi(n)$ terms of the form $m/n$ , where $m$ is relatively prime to $n$ and $\phi(n)$ denotes the Euler $\phi$ -function.).

Example 4.1.10   Let C be the cube in 3-space having vertices at the points $O=(0,0,0), P_1=(1,0,0), P_2=(0,1,0), P_3=(0,0,1), P_4=(1,1,0), P_5=(1,0,1), P_6=(0,1,1), P_7=(1,1,1)$ . We shall also (to use a notation which will be used more later) denote these by dbl, dfl, dbr, ubl, dfr, ufl, ubr, ufr, resp. Let $C_0 = \{O,P_1,...,P_7\}$ be the set of the 8 vertices of $C$ , let $C_1=\{uf, ur,ub,ul,fr,br,bl,fl,df,dr,db,dl\}$ be the set of the $12$ edges of $C$ , and let $C_2=\{F,B,U,D,L,R\}$ be the set of the $6$ faces of $C$ . Let $r$ be the rotation of a point $(x,y,z)$ by $180$ degrees about the line passing through the points $(1/2,1/2,0)$ , $(1/2,1/2,1)$ . Note that $r:\mathbb{R}^3 \rightarrow \mathbb{R}^3$ is a function which sends the cube $C$ onto itself.

This function $r$ induces three functions

$$f_0 : C_0 \rightarrow C_0, \ f_1 : C_1 \rightarrow C_1, \ f_2 : C_2 \rightarrow C_2.$$

where $f_i$ is the function which sends $x\in C_i$ to its image $r(x)$ under $r$ (which is again in $C_i$ ), for $i=0,1,2$ . Each $f_i$ is a bijection. For example, $f_1(ub)=uf$ and $f_2(B)=B$ .

Suppose $f : S\rightarrow T$ is a bijection. Define $f^{-1}$ to be the rule which associates to $t \in T$ the element $s\in S$ ,

$$f^{-1}(t)=s \ {\rm if and only if}\ f(s)=t.$$

This rule defines a function $f^{-1} : T \rightarrow S$ . This function satisfies $f(f^{-1}(t))=t$ , for all $t \in T$ , and $f^{-1}(f(s)))=s$ , for all $s\in S$ . In other words, the composition $f\circ f^{-1}:T\rightarrow T$ sends each element of $T$ to itself, and $f^{-1}\circ f:S\rightarrow S$ sends each element of $S$ to itself.

Definition 4.1.11   The function $f^{-1}$ constructed above is called the inverse function of $f$ .

Exercise 4.1.12   Label the vertices and the facets as in Example 4.1.10 and describe $f_1$ and $f_2$ explicitly by filling out the tables

$v$	$f_0(v)$	$e$	$f_1(e)$	$f$	$f_2(f)$

Exercise 4.1.13   Suppose that $\vert S\vert < \vert T\vert$ . Is there a surjective function $f : S\rightarrow T$ ? Explain.

Exercise 4.1.14   Suppose that $\vert S\vert = \vert T\vert$ . Show that a function $f : S\rightarrow T$ is surjective if and only if it is injective.

Exercise 4.1.15   If $f:W\rightarrow X$ , $g:V\rightarrow W$ , $h:U\rightarrow V$ are functions, is $(fg)h=f(gh)$ ? In other words, if $f(w)=x$ , $g(v)=w$ , $h(u)=v$ , is the value of $(fg)h$ at $u$ equal to the value of $f(gh)$ at $u$ ?