\(\newcommand{\versionNum}{$3.2$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section6.5Special functions

There are a great many functions that fail the horizontal line test which we nevertheless seem to have inverse functions for. For example, \(x^2\) fails HLT but \(\sqrt{x}\) is a pretty reasonable inverse for it — one just needs to be careful about the “plus or minus” issue. Also, \(\sin{x}\) fails HLT pretty badly; any horizontal line \(y=c\) with \(-1 \leq c \leq 1\) will hit \(\sin{x}\) infinitely many times. But look! Right here on my calculator is a button labeled “\(\sin^{-1}\).” 1  This apparent contradiction can be resolved using the notion of restriction.

Definition6.5.1

Given a function \(f\) and a subset \(D\) of its domain, the restriction of \(f\) to \(D\) is denoted \(\restrict{f}{D}\) and \begin{equation*} \restrict{f}{D} = \{ (x,y) \suchthat \; x \in D \, \land \, (x,y) \in f \}. \end{equation*}

The way we typically use restriction is to eliminate any regions in \(\Dom{f}\) that cause \(f\) to fail to be one-to-one. That is, we choose a subset \(D \subseteq \Dom{f}\) so that \(\restrict{f}{D}\) is an injection. This allows us to invert the restricted version of \(f\). There can be problems in doing this, but if we are careful about how we choose \(D\), these problems are usually resolvable.

Exercise 6.5.2

Suppose \(f\) is a function that is not one-to-one, and \(D\) is a subset of \(\Dom{f}\) such that \(\restrict{f}{D}\) is one-to-one. The restricted function \(\restrict{f}{D}\) has an inverse which we will denote by \(g\). Note that \(g\) is a function from \(\Rng{\restrict{f}{D}}\) to \(D\). Which of the following is always true: \begin{equation*} f(g(x)) = x \mbox{or} g(f(x)) = x ? \end{equation*}

Technically, when we do the process outlined above (choose a domain \(D\) so that the restriction \(\restrict{f}{D}\) is invertible, and find that inverse) the function we get is a right inverse for \(f\).

Let's take a closer look at the inverse sine function. This should help us to really understand the “right inverse” concept.

A glance at the graph of \(y = \sin{x}\) will certainly convince us that this function is not injective, but the portion of the graph shown in bold below passes the horizontal line test.

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

If we restrict the domain of the sine function to the closed interval \([-\pi/2, \pi/2]\), we have an invertible function. The inverse of this restricted function is the function we know as \(\sin^{-1}(x)\) or \(\mbox{arcsin} (x)\). The domain and range of \(\sin^{-1}(x)\) are (respectively) the intervals \([-1,1]\) and \([-\pi/2, \pi/2]\).

Notice that if we choose a number \(x\) in the range \(-1 \leq x \leq 1\) and apply the inverse sine function to it, we will get a number between \(-\pi/2\) and \(\pi/2\) — i.e. a number we can interpret as an angle in radian measure. If we then proceed to calculate the sine of this angle, we will get back our original number \(x\).

On the other hand, if we choose an angle first, then take the sine of it to get a number in \([-1,1]\) and then take the inverse sine of that, we will only end up with the same angle we started with if we chose the original angle so that it lay in the interval \([-\pi/2, \pi/2]\).

Exercise 6.5.3

We get a right inverse for the cosine function by restricting it to the interval \([0,\pi]\). What are the domain and range of \(\cos^{-1}\)?

The winding map is a function that goes from \(\Reals\) to the unit circle in the \(x\)–\(y\) plane, defined by \begin{equation*} W(t) = (\cos{t}, \sin{t}). \end{equation*}

One can think of this map as literally winding the infinitely long real line around and around the circle. Obviously, this is not an injection — there are an infinite number of values of \(t\) that get mapped to (for instance) the point \((1,0)\), \(t\) can be any integer multiple of \(2\pi\).

Exercise 6.5.4

What is the set \(W^{-1}(\{(0,1)\})\) ?

If we restrict \(W\) to the half-open interval \([0, 2\pi)\) the restricted function \(\restrict{W}{[0, 2\pi)}\) is an injection. The inverse function is not easy to write down, but it is possible to express (in terms of the inverse functions of sine and cosine) if we consider the four cases determined by what quadrant a point on the unit circle may lie in.

Exercise 6.5.5

Suppose \((x,y)\) represents a point on the unit circle. If \((x,y)\) happens to lie on one of the coordinate axes we have \begin{gather*} W^{-1}((1,0)) = 0\\ W^{-1}((0,1)) = \pi/2\\ W^{-1}((-1,0)) = \pi\\ W^{-1}((0,-1)) = 3\pi/2. \end{gather*}

If neither \(x\) nor \(y\) is zero, there are four cases to consider. Write an expression for \(W^{-1}((x,y))\) using the cases (i) \(x>0 \, \land \, y>0\), (ii) \(x\lt 0 \, \land \, y>0\), (iii) \(x\lt 0 \, \land \, y\lt 0\) and (iv) \(x>0 \, \land \, y\lt 0\).

This last example that we have done (the winding map) was unusual in that the outputs were ordered pairs. In thinking of this map as a relation (that is, as a set of ordered pairs) we have an ordered pair in which the second element is an ordered pair! Just for fun, here is another way of expressing the winding map: \begin{equation*} W = \{ (t, (\cos{t}, \sin{t})) \suchthat \, t \in \Reals \} \end{equation*}

When dealing with very complicated expressions involving ordered pairs, or more generally, ordered \(n\)-tuples, it is useful to have a way to refer succinctly to the pieces of a tuple.

Let's start by considering the set \(P = \Reals \times \Reals\) — i.e. \(P\) is the \(x\)–\(y\) plane. There are two functions, whose domain is \(P\) that “pick out” the \(x\), and/or \(y\) coordinate. These functions are called \(\pi_1\) and \(\pi_2\), \(\pi_1\) is the projection onto the first coordinate and \(\pi_2\) is the projection onto the second coordinate. 2 

Definition6.5.6

The function \(\pi_1: \Reals \times \Reals \longrightarrow \Reals\) known as projection onto the first coordinate is defined by \begin{equation*} \pi_1((x,y)) = x. \end{equation*}

The definition of \(\pi_2\) is entirely analogous.

You should note that these projection functions are very bad as far as being one-to-one is concerned. For instance, the preimage of \(1\) under the map \(\pi_1\) consists of all the points on the vertical line \(x=1\). That's a lot of preimages! These guys are so far from being one-to-one that it seems impossible to think of an appropriate restriction that would become invertible. Nevertheless, there is a function that provides a right inverse for both \(\pi_1\) and \(\pi_2\). Now, these projection maps go from \(\Reals \times \Reals\) to \(\Reals\) so an inverse needs to be a map from \(\Reals\) to \(\Reals \times \Reals\). What is a reasonable way to produce a pair of real numbers if we have a single real number in hand? There are actually many ways one could proceed, but one reasonable choice is to create a pair where the input number appears in both coordinates. This is the so-called diagonal map, \(d:\Reals \times \Reals \longrightarrow \Reals\), defined by \(d(a) = (a,a)\).

Exercise 6.5.7

Which of the following is always true, \begin{equation*} d(\pi_1((x,y)) = (x,y) \mbox{or} \pi_1(d(x)) = x? \end{equation*}

There are a few other functions that it will be convenient to introduce at this stage. All of them are aspects of the characteristic function of a subset, so we'll start with that.

Whenever we have a subset/superset relationship, \(S \subseteq D\), it is possible to define a function whose codomain is \(\{0,1\}\) which performs a very useful task — if an input \(x\) is in the set \(S\) the function will indicate this by returning 1, otherwise it will return 0. The function which has this behavior is known as \(1_S\), and is called the characteristic function of the subset \(S\) (There are those who use the term indicator function of \(S\) for \(1_S\).) By definition, \(D\) is the domain of this function. \begin{align*} 1_S: D \longrightarrow \{0,1\}\\ 1_S(x) = \left\{ \begin{array}{cl} 1 \amp \mbox{if} \, x \in S \\ 0 \amp \mbox{otherwise} \end{array} \right. \end{align*}

Exercise 6.5.8

If you have the characteristic function of a subset \(S\), how can you create the characteristic function of its complement, \(\overline{S}\).

A characteristic function may be thought of as an embodiment of a membership criterion. The logical open sentence “\(x \in S\)” being true is the same thing as the equation “\(1_S(x) = 1\).” There is a notation, growing in popularity, that does the same thing for an arbitrary open sentence. The Iverson bracket notation uses the shorthand \([ P(x) ]\) to represent a function that sends any \(x\) that makes \(P(x)\) true to 1, and any inputs that make \(P(x)\) false will get sent to 0. \begin{equation*} [ P(x) ] = \left\{ \begin{array}{cl} 1 \amp \mbox{if} \, P(x) \\ 0 \amp \mbox{otherwise} \end{array} \right. \end{equation*}

The Iverson brackets can be particularly useful in expressing and simplifying sums. For example, we can write \(\sum_{i=1}^{24} [2 \divides i]\) to find the number of even natural numbers less than 25. Similarly, we can write \(\sum_{i=1}^{24} [3 \divides i]\) to find the number of natural numbers less than 25 that are divisible by 3.

Exercise 6.5.9

What does the following formula count? \begin{equation*} \sum_{i=1}^{24} [2 \divides i] + [3 \divides i] - [6 \divides i] \end{equation*}

There is a much more venerable notation known as the Kronecker delta that can be thought of as a special case of the idea inherent in Iverson brackets. We write \(\delta_{ij}\) as a shorthand for a function that takes two inputs, \(\delta(i,j)\) is 1 if and only if \(i\) and \(j\) are equal. \begin{equation*} \delta_{ij} = \left\{ \begin{array}{cl} 1 \amp \mbox{if} \; i=j \\ 0 \amp \mbox{otherwise} \end{array} \right. \end{equation*}

The corresponding Iverson bracket would simply be \([i=j]\).

We'll end this section with a function that will be especially important in Chapter 8. If we have an arbitrary subset of the natural numbers, we can associate it with an infinite string of 0's and 1's. By sticking a decimal point in front of such a thing, we get binary notation for a real number in the interval \([0,1]\). There is a subtle problem that we'll deal with when we study this function in more detail in Chapter 8 — some real numbers can be expressed in two different ways in base 2. For example, \(1/2\) can either be written as \(.1\) or as \(.0\overline{1}\) (where, as usual, the overline indicates a pattern that repeats forever). For the moment, we are talking about defining a function \(\phi\) whose domain is \({\mathcal P}(\Naturals)\) and whose codomain is the set of all infinite binary strings. Let us denote these binary expansions by \(.b_1b_2b_3b_4\ldots\). Suppose \(A\) is a subset of \(\Naturals\), then the binary expansion associated with \(A\) will be determined by \(b_i = 1_A(i)\). (Alternatively, we can use the Iverson bracket notation: \(b_i = [i \in A]\).)

The function \(\phi\) defined in the last paragraph turns out to be a bijection — given a subset we get a unique binary expansion, and given binary expansion we get (using \(\phi^{-1}\)) a unique subset of \(\Naturals\).

A few examples will probably help to clarify this function's workings. Consider the set \(\{1,2,3\} \subseteq \Naturals\), the binary expansion that this corresponds to will have 1's in the first three positions after the decimal — \(\phi(\{1,2,3\}) = .111\) this is the number written .875 in decimal. The infinite repeating binary number \(.\overline{01}\) is the base-2 representation of \(1/3\), it is easy to see that \(.\overline{01}\) is the image of the set of odd naturals, \(\{1,3,5,\ldots\}\).

Exercise 6.5.10

Find the binary representation for the real number which is the image of the set of even numbers under \(\phi\).

Exercise 6.5.11

Find the binary representation for the real number which is the image of the set of triangular numbers under \(\phi\). (Recall that the triangular numbers are \(T = \{1,3,6,10,15, \ldots \}\).)

Subsection6.5.1Exercises

  1. The \(n\)-th triangular number, denoted \(T(n)\), is given by the formula \(T(n) = (n^2 + n)/2\). If we regard this formula as a function from \(\Reals\) to \(\Reals\), it fails the horizontal line test and so it is not invertible. Find a suitable restriction so that T is invertible.

  2. The usual algebraic procedure for inverting \(T(x) = (x^2+x)/2\) fails. Use your knowledge of the geometry of functions and their inverses to find a formula for the inverse. (Hint: it may be instructive to first invert the simpler formula \(S(x) = x^2/2\) — this will get you the right vertical scaling factor.)

  3. What is \(\pi_2(W(t))\)?

  4. Find a right inverse for \(f(x) = |x|\).

  5. In three-dimensional space we have projection functions that go onto the three coordinate axes (\(\pi_1\), \(\pi_2\) and \(\pi_3\)) and we also have projections onto coordinate planes. For example, \(\pi_{12}: \Reals \times \Reals \times \Reals \longrightarrow \Reals \times \Reals\), defined by \begin{equation*} \pi_{12}((x,y,z)) = (x,y) \end{equation*} is the projection onto the \(x\)–\(y\) coordinate plane. The triple of functions \((\cos{t}, \sin{t}, t)\) is a parametric expression for a helix. Let \(H = \{ (\cos{t}, \sin{t}, t) \suchthat t \in \Reals \}\) be the set of all points on the helix. What is the set \(\pi_{12}(H)\) ? What are the sets \(\pi_{13}(H)\) and \(\pi_{23}(H)\)?

  6. Consider the set \(\{1, 2, 3, \ldots, 10\}\). Express the characteristic function of the subset \(S = \{1, 2, 3 \}\) as a set of ordered pairs.

  7. If \(S\) and \(T\) are subsets of a set \(D\), what is the product of their characteristic functions \(1_S \cdot 1_T\) ?

  8. Evaluate the sum \begin{equation*} \sum_{i=1}^{10} \frac{1}{i} \cdot [ i \; \mbox{is prime} ]. \end{equation*}