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}\).”¹It might be labeled “asin” instead. The old-style way to refer to the inverse of a trig. function was arc-whatever. So the inverse of sine was arcsine, the inverse of tangent was arctangent. This apparent contradiction can be resolved using the notion of restriction.

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.

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.

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]\).

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\).

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.

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.²Don't think of the usual \(\pi \approx 3.14159\) when looking at \(\pi_1\) and \(\pi_2\). These functions are named as they are because \(\pi\) is the Greek letter corresponding to `p' which stands for “projection.”

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)\).

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*}

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.

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\}\).