5  Functions

In this chapter we explore the concept of a mathematical function. Undoubtedly, functions have been prevalent in your previous mathematical experiences. You may have spent a lot of time working with functions given by an explicit formula, such as . In this chapter we develop a broader understanding of functions, presenting a commonly used and intuitive (but incomplete) definition in Section 5.1, followed by a variety of related terminology and concepts, and then a rigorous definition in Section 5.5.

5.1.  What is a Function?

The notion of a function is broader than numerical functions that are given by explicit formulas.

DEFINITION 5.1 (Initial Version).    Let A and B be sets. A function from A to B is a rule that assigns to each a unique associated element .

There are two standard ways to represent “f is a function from A to B.” One is to write

and the other is

Both notations are supposed to indicate that the function f takes an input element and outputs an element , and we express this by writing . In the sections that follow, you will often read statements like “Let .” This is a short but complete sentence stating that f is a function from A to B.

For example, consider the function g defined in a piecewise fashion for real numbers x:

The formulas and both give real numbers if x is a real number, so we could use the notation or because both A and B equal . As another example, you might have encountered parametric curves which trace out patterns in the plane. One of these gives a circle parametrized by

as illustrated in Figure 1. Here the input is a real number and the output is a point , so we write or .

Figure 1. The image of the function is a circle.

Exercise 5.1   Define two functions from to .

The examples in this section emphasize that functions are not restricted to inputs and outputs involving real numbers. In particular, many functions do not have natural graphical representations. As a first example, we can construct a function f from to the set . We use the rule when n is an even integer and when n is odd, so

Formal languages are collections of strings of characters from a given alphabet. A particular example is the set of binary strings, consisting of all finite strings of 0s and 1s, including the empty string, which we denote . We call the set of all finite binary strings :

The notion of length provides a function from to . Using a slightly different style of function notation than we have seen so far, we denote the length of a string by , so that we have , , and . This function counts the total number of 0s and 1s in the given string. There is also a function that counts only the 0s, where for example

Similarly there is a function that counts only the 1s, so that

Exercise 5.2   Prove the following two elementary facts about .

(a)   Let ω be formed by concatenating the two strings and , that is . Prove that .

(b)   Prove that for any string .

We can also construct a function

by defining to be the first character in the string ω, reading left-to-right; for instance, . Notice that we need to remove from consideration because has no first character.

Our next examples use the set of polynomials with integer coefficients. We denote this set by , notation that is purposely reminiscent of examples from Section 4.5. The set contains , and it also contains linear functions like and constant functions like .

We can define by

For example, . We can also define a function by

Thus .

As a final introductory example, we can define a function κ from to , where a polynomial is mapped to the shortest possible string that has a 1 in each position i where the coefficient of is non-zero; other positions are filled in with 0s. For instance,

has 1s in positions 1, 2, and 4, and

To make the definition of our function κ precise, we set when , the zero polynomial; for all other , the right-most position of is a 1.

REMARK 5.2.   Because functions are ubiquitous, there are a number of different ways to speak of them. For example, in many situations the word “map” is synonymous with “function.” If , which is sometimes written , you will hear both “f maps x to y” and “f sends x to y.”

Exercise 5.3   It is time for you to construct some functions involving the set of polynomials .

(a)   Construct a function .

(b)   Construct a more interesting function¹ from to than you did for part (a)   .

(c)   Construct an interesting function .

(d)   Construct an interesting function .

(e)   Construct an interesting function .

(f)   Construct an interesting function .

5.2.  Domain, Codomain, and Range

There are a number of words that are used quite frequently when discussing functions, and you need to absorb them.

DEFINITION 5.3.   If f is a function from X to Y, then the domain of f is X; the codomain is Y. The image of an element is the unique element where . The range of f is the subset of Y consisting of all images:

Sometimes the range of f is called the image of the function f .

EXAMPLE 5.4.   Let be the parametric curve defined in the previous section. The domain of γ is , the codomain is , and as is illustrated in Figure 1, the range of γ is the unit circle:

This highlights that the range can be significantly smaller than the specified codomain.

Exercise 5.4   Determine the ranges of the functions , ϕ, and κ defined in Section 5.1.

EXAMPLE 5.5.   Here are some additional examples of functions.

(a)   For any set A, the identity function has for every . It is denoted , which we often use, and sometimes . The domain, codomain, and range all equal A.

(b)   The floor function sends to the greatest integer less than or equal to x, and the ceiling sends x to the least integer greater than or equal to x. For example, and . These are both functions from to . In both cases the range is all of the codomain .

(c)   An infinite sequence of real numbers is just another way to describe a function , where the correspondence is . In a later chapter we will ask whether such a function can ever have its range equal to the codomain .

(d)   You can map a set to its power set by with for every . You can also use complements to construct another map from A to : let with . As an example, consider the set

Then and . The range of f is

while the range of g is

(e)   The function with is often called a projection, in this case a projection onto the first coordinate. The function is the projection onto the second coordinate;² its range is B.

(f)   The function with is often called a diagonal. To see why this name is appropriate, set and sketch the points in the subset of the plane .

Exercise 5.5   Determine which of the following are functions with the given domains and codomains.

(a)    with .

(b)    with .

(c)    with .

(d)    with .

(e)    with .

(f)    with .

(g)    with , where is the set of positive real numbers.

5.3.  Injective, Surjective, and Bijective

The core vocabulary of functions includes the adjectives injective, surjective, and bijective.

DEFINITION 5.6.   A function is injective if for all , implies .

Put another way, f is injective if no two distinct xs have the same image. An injective function is also called one-to-one. The claim that a function is injective is sometimes encoded by the symbol , as in and .

EXAMPLE 5.7.   The function given by is injective for the following reason: for any , having means that , which gives upon dividing both sides by 3.

EXAMPLE 5.8.   Let be the function that appends a 1 to the end of any given string. As examples, and . To prove that this function is injective, let and be two strings in . If , then the string and the string are identical. This means that and are identical strings as well.

Exercise 5.6   Determine whether the following functions are injective.

(a)    given by , where is the set of positive real numbers.

(b)    given by .

(c)    given by .

(d)    given by . As an example, .

DEFINITION 5.9.   A function is surjective if for each there exists an such that .

Put another way, f is surjective if each element in Y is hit by some element in X. A surjective function is also called onto. The claim that a function is surjective is sometimes encoded by the symbol , as in and .

In Figure 2 we illustrate a function going from the set {Ole, Lena, Sven} to the set {Alice, Bob, Cecelia}, where each person in the first set is sent to his or her favorite partner when playing games. This function is not injective, as Lena and Sven both like playing with Bob. It is also not surjective: Cecelia is lonely, not being the preferred partner of anyone in the first set.

Figure 2. A function between two finite sets.

EXAMPLE 5.10.   The following three examples provide some insight into how you prove that a given function is or is not surjective.

(a)   The function given by is not surjective for the following reason: 1 is an element of (the codomain) , but the equation is not satisfied by any element of (the domain) .

(b)   The function given by appending a 1 to the end of any string is also not surjective. To prove this you could first note that the process of appending a 1 increases the length of any string ω by 1. Since has length 0, is not satisfied by any .

(c)   Let be defined by . This function is surjective; we can also say that it is “onto .” To prove this, we need to show that the range of g is all of , which we do by considering three cases:

  (i)   Because , we know 0 is in the range of g.

 (ii)   If , define to be the string consisting of n 0s. Then , and thus all positive integers are in the range of g.

(iii)   If , define to be the string consisting of 1s. Then , and thus all negative integers are in the range of g.

Exercise 5.7   Prove the following claims:

(a)   The function in Example 5.5 (a)    is both surjective and injective for any set A.

(b)   The functions in Example 5.5 (b)    are surjective but not injective.

(c)   The function in Example 5.5 (f)    is injective, and it is surjective if and only if A contains at most one element.

DEFINITION 5.11.   A function is bijective if it is both injective and surjective.

There is a familiar graphical interpretation of injective, surjective, and bijective when :

(a)   f is injective if each horizontal line intersects the graph of f in at most one point.

(b)   f is surjective if each horizontal line intersects the graph of f in at least one point.

(c)   f is bijective if each horizontal line intersects the graph of f in one and only one point.

You need to be a bit careful with this graphical interpretation: it applies when the codomain is , but not necessarily in other circumstances. For example, in Section 5.1 we defined the function γ that traces out a circle in the plane. You might be tempted to say that horizontal lines can cross a circle twice, and thus γ is not injective. The x-axis, for example, intersects the circle at and . But this confuses the path traced out by γ with the graph of a function. To prove that γ is not injective, you can point out that , and thus two real numbers are mapped to the same point in . If you restrict the domain of γ to the half-open interval , then γ is indeed an injective function, even though the image of γ is still a circle.

Bijective functions, called bijections, are very important because they provide matchings between the elements in two sets A and B. They are often referred to as one-to-one correspondences, emphasizing this fact.

Exercise 5.8   Find bijections for the given open intervals of real numbers.

(a)    and

(b)    and

(c)    and

Exercise 5.9   Let be an injection. Prove that the function , defined by for all , is a bijection.

When X and Y are finite sets, we can count the number of functions of different types. For example, if and , there are nine different functions, one for each column in Table 1. As we have indicated, six of these functions are injective; none are surjective. Exercises 5.35, 5.36, and the following exercise help you further explore the number of injective, surjective, bijective, and otherwise unrestricted functions between two finite sets.

Table 1 Six of the nine possible functions from to are injective.

Exercise 5.10   Consider all of the different functions from a set A with three elements to a set B with five elements. Try to answer the following questions without creating the full table of functions as we did in the smaller case above.

(a)   How many functions are there?

(b)   How many of these functions are injections?

(c)   How many of these functions are bijections?

(d)   How do your answers change if and ?

5.4.  Composition

The function is a composition of the “outer” cosine function and the “inner” polynomial . This concept of function composition is not, however, restricted to functions that can be presented by formulas.

DEFINITION 5.12.   If and are functions, then their composition is written

and is defined by sending each to the element . That is, if and .

The notation is particularly helpful for composition, as you can visualize by

Similarly a diagram like the one shown in Figure 3 can be used to visualize function composition.³ This figure depicts two functions and , where , , and . Following the arrows shows, for example, that .

Figure 3. Two functions and .

EXAMPLE 5.13.   Let be given by and by . In this case, since , both and are legitimate functions from to . However, , while .

EXAMPLE 5.14.   Let f and g be the functions shown in Figure 3. The function f is injective but not surjective because is not in the range of f. The function g is surjective but not injective because but . The composition is neither injective nor surjective.

Exercise 5.11   Referring to the previous example, what is , if anything?

We end this section with a handful of important, foundational facts about the adjectives injective, surjective, and bijective in the context of composition of functions. But first we offer a couple of cautionary examples. You might expect that if is injective, then g and f must be injective. However, consider the example where and , both having domain and range equal to . Then the composition is injective, but the same is not true for g, as you should now verify.

Exercise 5.12    

(a)   Verify that if and , then g is not injective, but the composition is injective.

(b)   Find functions f and g where g is surjective and is surjective, but f is not surjective.

These examples should help you appreciate the following proposition.

PROPOSITION 5.15.   Let and .

(a)   If is injective, then f is injective.

(b)   If is surjective, then g is surjective.

PROOF.   To prove part (a), assume to the contrary that f is not injective. Then there must be distinct elements a and in A such that . But then it must also be the case that . This contradicts the hypothesis that is injective.

To prove part (b), note that because is surjective it must be the case that given any there is an such that . But if we let , we know that . And so given any there is a such that .

Thankfully, the properties that are held by both f and g also hold for their composition.

PROPOSITION 5.16.   Let and .

(a)   If f and g are both surjective, then so is .

(b)   If f and g are both injective, then so is .

(c)   If f and g are both bijective, then so is .

Exercise 5.13   Prove Proposition 5.16. As a hint for (a), you might start with the statement “Let c be any element of C. Since g is surjective, …” As a hint for (b), you might start with the statement “Suppose that and are any two elements of A such that , which we can also write as . Since g is injective, …” Finally, as a hint for (c), make sure you’ve done parts (a) and (b)!

REMARK 5.17.   Our definition of function composition requires that the codomain of f is the same as the domain of g. This is more restrictive than is necessary. If and , where , then you can still define the composition by . See Exercises 5.45 and 5.69 at the end of this chapter if you would like to explore this modest extension of the definition.

5.5.  What is a Function? Redux!

While Definition 5.1 likely aligns well with your prior knowledge of functions and has allowed us to first explore some of their fundamental concepts, mathematicians are often uncomfortable defining functions as “rules” taking elements from one set to another. One reason for this discomfort is because the notion of a rule is somewhat vague. A related reason is that “rule” is often misinterpreted as meaning “formula,” which is too restrictive. However, if that interpretation is too restrictive, just what is it we mean when we use “rule” in the definition?

An alternate and ultimately preferable approach is to define functions using the set theory we developed in Chapter 3. The motivation comes from our experience with polynomials, trigonometric functions, and other functions that are quite closely identified with their graphs. In the case of a function , the graph of f is the set of points , which is a subset of . We are used to this idea in the context of real numbers, but we can define the “graph” of a function regardless of whether it is feasible to visualize it in the plane .

DEFINITION 5.18.   Let f be a function from a set A to a set B, both non-empty. Then the graph of f is the subset of described by

If f is a function from A to B, then the following property holds for the graph of f : given any , there is a unique element in the graph of f. This statement is just a direct generalization of the standard vertical line test for the case when A and B are subsets of . But we can reverse our way of thinking to see that any subset that satisfies this property can be used to define a function from A to B: you simply say that the function associated to S maps to when . Put another way, the subset of becomes the “rule.”

DEFINITION 5.19 (Unambiguous Version).    Let A and B be sets. A function from A to B is a subset such that for each element there is a unique element .

Notice that we are defining a function as a set, even though we are giving the set a lower-case name, “f.”

EXAMPLE 5.20.   Let and . Then is a function from A to B, as is . On the other hand, none of the following subsets of are functions.

(a)   

(b)   

(c)   

The first does not have a unique ordered pair with leading entry equal to 2; the second has no ordered pair with leading entry 1; and the third is not contained in .

Exercise 5.14   Suppose that and the function f contains , , and . Must f contain any other elements?

We emphasize that the functions we have seen in the first sections of this chapter are indeed functions according to Definition 5.19: the “rule” mapping a to b is simply the condition that is in the set f. For example, the functions in Figure 3 are

And the function κ from Section 5.1 is an infinite subset of , two of its elements being and .

Exercise 5.15   If you define the function from Section 5.1 as a subset , what elements of have the form for some ?

We now revisit some of the terminology from the previous sections. If f is a function from A to B, then the domain of f is A; the codomain is B. The image of an element is the unique such that . By defining to be this element b, all of our previous definitions translate seamlessly. For example, the range of f is the subset of B consisting of all images:

It is important that you become comfortable with both types of function notation, as each is useful in different settings.

We can restate the definition of the composition of functions using the unambiguous definition of functions: if and are functions, then their composition is the subset of defined by

For example, the composition of f and g in Figure 3 is , with a, b, and c acting as the intermediate elements in B.

Exercise 5.16   Restate the definitions of injective and surjective in a way that utilizes the unambiguous definition of a function f as a subset of .

We finish this section with a proof of the Pigeonhole Principle, a lemma that is widely used throughout mathematics. It derives its name from a common, informal phrasing: if m pigeons fly into n coops, with , then at least one coop gets at least two pigeons. Stated in the terminology of functions, the Pigeonhole Principle is:

LEMMA 5.21 (The Pigeonhole Principle).    Let , where A and B are finite, non-empty sets. If , then f is not injective.

The proof of the Pigeonhole Principle fits well with the unambiguous definition of functions presented in this section.

PROOF.   Our proof is by induction on the size of the set B.

Base Case: If , then , so A contains at least two distinct elements, and . This means that f contains both and , where b is the only element of B, so f is not injective.

Inductive Step: Assume the lemma is true for all finite sets B whose size is less than or equal to n for some . Now consider a function where is greater than . For this argument we fix an element .

Case 1:   If A contains at least two distinct elements, and , such that f contains both and , then f is not injective.

Case 2:   If A contains no element a such that , then f is also a subset of . Since and , we know that f is not an injection, by our induction hypothesis.

Case 3:   By the previous two cases, we may now assume there is a unique such that . We can then define

We know that for every there is a unique , because f being a function implies that is also a function. Notice that

and so we may apply our our induction hypothesis to , proving that is not injective. It follows that f cannot be injective either.

Exercise 5.17   Explain two quick steps in the proof of the Pigeonhole Principle above: if f is a function, so is ; and if is not injective, neither is f.

The Pigeonhole Principle is the focus of Project 11.5. We highly recommend that you look at this project, which begins with a number of accessible results that follow from the Pigeonhole Principle.

GOING BEYOND THIS BOOK.   The definition of a function introduced in this section is the result of a long evolution in the history of mathematics; see the nice survey of this history in Israel Kleiner’s “Evolution of the function concept: A brief survey” [Kle89].

5.6.  Inverse Functions

Two functions are said to be inverses of each other if one function “undoes” the other, in a manner described more carefully near the end of this section. You have encountered the idea of inverse functions before, perhaps in the process of solving equations. For example, if you have reduced a problem to , then you would take the cube root of both sides to determine that . This works because the functions and are inverses. Similarly if you meet , you can apply the natural logarithm to both sides to determine that , and therefore . Here we used the fact that the natural logarithm function and the exponential function are inverses.

The definition of a function f as a subset of is particularly convenient for defining the inverse of f.

DEFINITION 5.22.    If is a function, define the inverse as a subset of :

Let f be a function from a subset of to . Because the inverse of f is created by simply reversing the order of elements, contains all points of the form . This is equivalent to reflecting the graph of f across the line ; the example of and is illustrated in Figure 4.

Figure 4. Plotting a function and its inverse – in this case and  – reveals symmetry about the line .

Exercise 5.18   Carefully plot and , determining all of the points where they intersect.

There are many situations where is not a function. Consider the example of , shown along with the subset of in Figure 5. Looking at the graph of f you can see that there are four values of x where , and via the quadratic formula you can determine that the four solutions of are . Because multiple values are taken to by f, you cannot determine the value of x just from knowing that .

Figure 5. The function is shown with a dotted curve. Viewing f as a subset of , you can form its formal inverse, shown as a solid curve, which is not a function.

There are many vertical lines in Figure 5, including the line , that pass through several points of . Thus does not satisfy the definition of a function. Specifically, it is not the case that for each element there is a unique element . There is another problem with thinking of as a function from to . Because there is no real-valued solution to , there is no element . So for some values of there is no element .

The same fundamental issues are illustrated by the function from to shown in Figure 6. In this case, you can visualize by reversing the arrows, producing

As the figure highlights, the number 2 is not the first element of an ordered pair in (notice that f is not surjective), and the number 3 is the first element of three ordered pairs in (notice that f is not injective).

These examples motivate the need for a characterization of what makes a function.

Figure 6. The function f is shown on the left, with illustrated on the right.

THEOREM 5.23.   Let be a function. Then defines a function from B to A if and only if f is a bijection.

PROOF.   Assume first that f is a bijection, that is, f is both injective and surjective. Since f is surjective, given any there is an such that . This means that given any there is an ordered pair . To see that this pair is unique given any , and thus that is a function, assume to the contrary that there is also a pair , with . Then and , contradicting the fact that f is injective.

If f is not a bijection, then f is either not surjective or not injective. If f is not surjective then there is a that does not appear as the second element of an ordered pair in f. Thus there is no such that , so is not a function. If f is not injective, then there are distinct elements and an element such that and are both in f. Thus and are both in , which contradicts the requirement that the ordered pair beginning with b is unique.

Exercise 5.19   Let’s examine the logical structure of the proof for Theorem 5.23. If P is the proposition “f is a bijection,” then P is stating that f is both injective and surjective. Thus P is equivalent to , where is “f is surjective” and is “f is injective.”

Let Q be the proposition “ is a function.” In our proof of Theorem 5.23 we showed:

Verify that this expression is logically equivalent to what is claimed in the theorem: .

If is a bijection, we can now say why “undoes” f, and vice versa, in the common notation of functions. Since f is a function, for every there is a unique such that , and thus . Since is also function, we can write both and , so

for all . Moreover, since f is a bijection, for every there is a unique element such that , and thus . As before, we can again write and , so

for all . Put another way, we now know that and . (Recall that the functions and are the identity functions mentioned in Example 5.5.)

Exercise 5.20   Let and . Prove that if and , then f and g are bijections, and .

5.7.  Functions and Subsets

There are many confusing things about inverses and how they are used in practice. For one, because you often want to know what elements in the domain are mapped by f to a particular element in the range, it is not uncommon to use even when is not a function. It is also not uncommon to apply a function not just to single elements but to a subset of the domain. In this section we explore these notationally challenging practices.

5.7.1 Where did this come from?   Let be a function. Given some , you might wonder what elements of A are taken to b by f. For example, the length function takes a binary string in and returns a non-negative integer: we find that , and as well. As shown in Exercise 5.15, there are eight strings of length 3:

If , then the pre-image of is defined to be

or stated in terms of ordered pairs,

Notice that the pre-image of an element b may be a single element in A or it may be a subset of elements. In particular, if b is not in the range of f, then the pre-image of b is the empty set.

In the previous section we examined . Looking at the graph in Figure 5 you see that f takes four distinct real numbers to , and with a bit of algebra you can show that

And since is not in the range of , the pre-image of is .

Exercise 5.21   Let be the function , shown in Figure 7.

(a)   What is the pre-image of 0?

(b)   What is the pre-image of 6?

(c)   Which real numbers have a pre-image consisting of exactly two numbers? (You may need a bit of calculus to help with this part.)

Figure 7. The cubic function for Exercise 5.21.

5.7.2 From Elements to Subsets.   Continuing our examination of from Exercise 5.21, it is not uncommon to want to understand where a function like f takes an entire subset of real numbers. For example, we might like to apply f to the closed interval and write

by which we mean

The lower limit, , is the minimum for f over the interval .

Any function can be used to describe an associated function from the power set of A to the power set of B. There is no commonly accepted notation for this “induced” function, and we will temporarily denote it by . The rule that defines is this:

That is, is the set of all images of elements in .

As an example, let f be the floor function, . Then

(a)   ,

(b)   ,

(c)   ,

(d)   .

Exercise 5.22   Let be the function

(a)   Verify that and .

(b)   What is ?

(c)   What is ?

(d)   What is ?

(e)   What is ?

5.7.3 Subsets of the Range.   If , then the pre-image of 0 is the set . Because f is not injective, we know that is not itself a function. However, it is tempting to write

Such a statement is in essence claiming that can be thought of as a function, but one where the image of an element might be a subset of , the domain of the function f. That is, the range of is in the power set .

We can combine the notions in the previous two sections – working with pre-images even when is not a function and the construction of from f  – to construct a function from subsets of B to subsets of A. Given a function , there is an induced function from to . It is defined for each by

In particular, if then we can write

Exercise 5.66 asks you to verify that and are indeed functions. As with , our use of the notation is temporary.

We return to the function to illustrate this construction. For this f we have

(a)   ,

(b)   ,

(c)   ,

(d)   .

As another example, consider defined by

Then each of the following statements is true:

(a)    and ,

(b)   ,

(c)   ,

(d)   .

Exercise 5.23   We can consider the trigonometric functions sine and cosine to have domain and codomain . What are and ?

Exercise 5.24   Consider the following two functions from to :

Plot enough points for each function so that you have a decent impression of its graph. Then compute the following.

(a)    and

(b)    and

(c)   

(d)   

(e)   

(f)   , where

5.7.4 Abuse of Notation.   Given we have now introduced three associated concepts:

, which may or may not be a function from B to A;

, which is a function from to ;

, which is a function from to .

We also mentioned that there is no standard notation for and . In practice, the symbols f and are used, or perhaps we should say reused or overused, in their places. The multiple meanings for the same notation is potentially confusing, but in context it is usually clear what is being described. Thus if , then you will indeed see expressions like

In each case, you can determine what is being stated without the burden of additional notation.

Using notation in an imprecise fashion, or using the same notation for two related but distinguishable constructions, is referred to as an abuse of notation. As the overuse of the symbols f and is a rather common abuse of notation, for the remainder of the book we will drop the subscript “” and follow the convention of using the symbols f and in all of the contexts we have described in this section.

5.8.  A Few Facts About Functions and Subsets

Let be a bijection and let be its inverse function. We have seen that for all and for all . When you apply functions and inverses to subsets instead of elements, similar but weaker statements hold.

It will be helpful to begin with an example. Consider the function

whose graph is plotted in Figure 8, highlighting the fact that f takes the closed interval to . You can see in the graph of f that there are additional values of x that map into the closed interval . In particular, a bit of algebra shows that , which is the key fact in determining that . Thus

The original interval is not, however, completely unrelated to : it is a subset of it.

Figure 8. The function takes the closed interval to .

PROPOSITION 5.24.   Let be a function.

(a)   If , then .

(b)   If , then .

PROOF.   We first prove part (a). For each we know that by the discussion in Section 5.7.2. By the discussion in Section 5.7.3, we know that . Hence .

To prove part (b), simply notice that

Exercise 5.25   Let . Prove or find a counterexample to each of the following claims.

(a)   If f is injective, then for all subsets , .

(b)   If f is surjective, then for all subsets , .

(c)   If f is bijective, then for all subsets , .

The behavior of functions applied to unions and intersections is similarly aligned with intuition, but it is once again weaker than what you might at first expect.

PROPOSITION 5.25.   Let be a function and . Then

(a)   ,

(b)   .

PROOF.   We first prove that . Let . Then there is a with . Since we have or . Thus or , hence .

Conversely, let . Then or , so for some or for some . Either way we conclude that . This establishes part (a).

To prove part (b) we begin with an element . Because w is in the image of , there must be some with . Since , , and similarly since , . Thus .

Exercise 5.26   Construct an example showing that doesn’t always hold.

5.9.  End-of-Chapter Exercises

Exercises you can work on after Sections 5.1 and 5.2

5.27 The following questions ask about the domain and range of some standard trigonometric functions.

(a)   What is the range of ?

(b)   What is the domain of ?

(c)   What is the range of ?

(d)   What is the domain of ?

5.28 Determine the range of the following functions.

(a)   The function defined by .

(b)   The function defined by

5.29 Determine the range of the following functions that involve , the set of all polynomials with integer coefficients.

(a)   The function defined by .

(b)   The function defined by .

5.30 Determine which of the following are functions with the given domains and codomains.

(a)    with .

(b)    with .

(c)   For any finite set A, with .

(d)    with .

(e)    with .

(f)   For any set A, with .

5.31 Define the function by

(a)   What is Range(g)?

(b)   Now consider the same definition for but as a function with a different domain. What is Range(g) in this case?

Exercises you can work on after Section 5.3

5.32 Define a function by

where is the ceiling function. Is f injective or surjective? Or neither?

5.33 Define the function by

Prove that f is injective but not surjective.

5.34 Let be the function , where a and b are elements of . For any such pair of coefficients, must f be …

(a)   …injective?

(b)   …surjective?

(c)   …bijective?

5.35 Consider the following continuation of Exercise 5.10 for finite sets A and B.

(a)   Determine the number of different bijections from A to B if .

(b)   Determine the number of different injections from A to B if .

5.36 Consider the following continuation of Exercises 5.10 and 5.35.

(a)   Determine the number of different surjections from A to B if and .

(b)   Determine the number of different surjections from A to B if and , with . As a hint, Stirling numbers of the second kind, discussed in Section 3.8, might prove helpful.

5.37 Construct an injective map . Then try your best to construct an injective map .

5.38 Let and , and define by

(a)   Prove that if f and g are injections, then so is h.

(b)   Prove that if f and g are surjections, then so is h.

5.39 Determine which of the following functions are bijections.

(a)    given by .

(b)    given by .

(c)   For a set A, given by .

5.40 Given sets A and B, recall the function that projects onto the first coordinate: . What conditions do you need to put on the sets A and B to insure that this function is …

(a)   …injective?

(b)   …surjective?

(c)   …bijective?

5.41 Determine whether there is a bijection for the following given sets A and B.

(a)    and .

(b)    and .

Don’t let the single missing point in part (b) deceive you: accommodating it might prove to be quite challenging!

5.42 Try to find bijections for the following given sets A and B. We believe the first one is not so hard, the next is harder, and so on. Some bijections might not be possible; this topic will reappear in Chapter 7.

(a)    and .

(b)    and .

(c)    and .

(d)    and .

(e)    and .

Caution: The last one is REALLY hard.

Exercises you can work on after Section 5.4

5.43 Suppose that A, B, and C are finite sets that each contain five elements. Do there exist functions and that satisfy the following conditions? Prove that your answers are correct.

(a)    and is injective.

(b)    and is surjective.

(c)    and .

(d)    and .

5.44 Let be the function defined in Exercise 5.33. Let be defined by

For example,

Describe the composition .

5.45 The arcsine function, , is a function from to , where if and only if . In this exercise we ask you to describe the functions and : for each composition, justify your answers to the following questions:

(a)   What is the domain of the composition?

(b)   What is the range of the composition?

(c)   Is the composition injective?

(d)   Is the composition surjective?

(e)   Is the composition bijective?

Note that the range of arcsine is properly contained in the domain of the sine function. As we remarked at the end of Section 5.4, a composition like still makes sense, even though the range of is not identical to the domain of .

5.46 Prove that function composition is associative. That is, if

then

5.47 Consider the function defined by

For example, , and .

(a)   What is the range of h?

(b)   We have heard this function called the Popcorn Function as well as Stars Over Babylon. Why are those appropriate names? Plot at least 12 points on the graph of this function using rational x-values with .

(c)   A function f is an idempotent if and f are the same function. Show that is an idempotent. Two simpler idempotent functions can be found in Exercise 5.24.

(d)   Comment on Zippy in Figure 9.

Figure 9. Idempotent functions are defined in Exercise 5.47.

5.48 Define a function by

It is easy to see that the only values of x for which are those with . In this exercise you will extend this insight to iterated versions of f, namely the functions

It may be helpful to sketch the graphs of f and , before starting these problems.

(a)   Which values of x satisfy ?

(b)   Which values of x satisfy ?

(c)   Which values of x satisfy ?

(d)   Let . Which values of x satisfy ?

(e)   What is Range(f )? Range()?

Exercises you can work on after Section 5.5

5.49 Determine which of the following are functions with the given domains X and codomains Y. For those that are functions, determine which are injective, surjective, or bijective.

(a)    and .

(b)   , , and .

(c)   , , and .

(d)   , , and .

(e)    and

For example, because has two distinct prime factors.

(f)   , , and

For example, .

5.50 Prove that the composition of two functions is a function, using the ordered pairs definition of functions.

5.51 The functions and κ were defined in Section 5.1. Does either or make sense? If so, describe the effect of the resulting function(s).

5.52 Let be a function.

(a)   Prove that f is injective if and only if

for all .

(b)   Prove that f is surjective if and only if

for all .

5.53 Let be a function. In many situations you may want to restrict the domain of f or expand its range.

(a)   If , then define the restriction of f to C as

Prove that is a function from C to B.

(b)   If D is any set that contains B, then you can use f to define a function with domain A and codomain D, using the fact that

Prove that f is still a function in this setting.

5.54 Give two examples of infinite subsets where , the restriction of the sine function, is an injective function. (The restriction of a function is defined in Exercise 5.53.)

5.55 Prove that the restriction of sine to the integers, , is injective. (The graph of , for integers between and 20, is shown in Figure 10.) We recommend using the trigonometric identity

You may assume that , a fact that you can prove in Section 8.6.

Figure 10. The sine function restricted to the integers.

Was one of your answers to Exercise 5.54?

5.56 In a class of n students, some students are friends and others are not. We assume that being friends is a symmetric relationship, so that if Alice is friends with Bob, then Bob is also friends with Alice. Prove that there must be two students in the class with the same number of friends. Here’s a hint: can Alice have no friends in the class while at the same time Bob is friends with students?

5.57 Let

Prove that if 19 distinct elements are chosen from S, then two of those integers must sum to 104.

Exercises you can work on after Section 5.6

5.58 The function and its inverse are shown in Figure 11.

(a)   What is ?

(b)   What is ?

(c)   What is ?

(d)    is between which two integers?

Figure 11. The function is shown with a solid curve and its inverse is represented by the dotted curve.

5.59 Define by

Prove that f is a bijection, and describe .

5.60 For any set S, let be the function from to taking a subset of S to its complement in S.

(a)   Prove that is a bijection.

(b)   Prove that is its own inverse.

5.61 Let be a bijection. By Theorem 5.23, is also function; moreover, by Exercise 5.20 it is a bijection. Since is a bijection, it follows that it has an inverse function, . Prove that f and are the same function.

Exercises you can work on after Sections 5.7 and 5.8

5.62 Let , as shown in Figure 5.

(a)   What is the pre-image of 5?

(b)   For what values of x does the set have exactly two elements? If it’s helpful, the minimum values of occur at the points .

5.63 Let be defined by

In other words, r takes a polynomial to its set of real roots.

(a)   Verify that , and determine .

(b)   Find a polynomial where .

(c)   Show that is not empty.

5.64 Let and . Then . Show by an example that it is possible to have without having .

5.65 Determine and for the following functions and subsets.

(a)    given by , with and .

(b)    given by , with and .

(c)    given by if is a fraction in lowest terms, with and .

5.66 Given a function f from a set A to a set B, we defined and in Section 5.7.

(a)   Verify that the “function” is actually a function.

(b)   Verify that the “function” is actually a function.

5.67 Let , as shown in Figure 5.

(a)   What is ?

(b)   What is ?

(c)   What is ?

5.68 Let be a function, and let be an indexed family of subsets of A. Prove the following.

(a)   

(b)   

More Exercises!

5.69 Let and .

(a)   Assuming that , construct a definition of the composition (as described in Remark 5.17) using the unambiguous definition of a function.

(b)   Give an unambiguous definition of which only requires

and explain why this is different from the situation in part (a).

(c)   If it is not the case that , what is the maximal subset such that you can define the composition ? Here denotes the restriction of f to X, as defined in Exercise 5.53.

5.70 Given a partition of the set , let be the function where is the size of the block of that contains a. Prove that for any two partitions of D, and , there are distinct numbers such that and .

5.71 We have seen that a bijection has an inverse function , with and . If is any function (not necessarily a bijection) then we say f has a left inverse if there is a function such that .

(a)   Let be defined by

Find a left inverse for f.

(b)   Find another left inverse for f, thereby showing that left inverses are not unique.

(c)   Prove that if is an injection, then f has a left inverse.

5.72 Construct a similar exercise to Exercise 5.71 that defines and explores right inverses instead of left inverses.

5.73 The goal of this exercise is to prove the following claim:

Let , and define . Let A be any subset of with . Then A must contain x and y, where x is a proper divisor of y.

Our approach draws on ideas from Chapter 4, particularly the Fundamental Theorem of Arithmetic (Theorem 4.11).

(a)   Use the Fundamental Theorem of Arithmetic (Theorem 4.11) to prove that every natural number has a unique expression as where k is a non-negative integer and is an odd natural number.

(b)   Define a function via , and prove that the restriction of to the set A is not injective.

(c)   Conclude that there must be an x and where x is a proper divisor of y.

(d)   Explain why we really do have to assume that , regardless of the value of n.

5.74 We use to denote the set of functions from A to B. Let be a bijection. Define by

or if you prefer

Prove that is a bijective function.

If You Have Studied Calculus

5.75 Find a condition on the coefficients that characterizes when a cubic polynomial is bijective, and prove that your characterization is correct.

5.76 Recall that is the set of all polynomials with integer coefficients.

(a)   Let be the derivative. For example, and . Explain why d is a function.

(b)   Is d injective? Give a proof or find a counterexample.

(c)   Is d surjective? Give a proof or find a counterexample.

5.77 Let , with the domain of f equal to the set of positive real numbers.

(a)   Explain why you know that is injective, and has an inverse.

(b)   What is ?

(c)    is between what two integers?

5.78 Let be the set of all polynomials with rational coefficients.

(a)   Construct a similar set of questions to Exercise 5.76 in the context of integration. Take care with “+C”!

(b)   Answer your questions.

---

¹   As an example, you might have defined your function from to by . That is valid, but not interesting. The function strikes us as being more interesting. We hope your answer to (b) is even more interesting than this. And please don’t ask us to define “interesting”!

²   The notation is technically incorrect; the input element is the ordered pair , so the output should be denoted , as we did in the previous sentence with f. But, in fact, notation like is quite standard, to reduce the number of parentheses in a context where the meaning is clear.

³   Yes, the order of f and g in the name is opposite to the order presented in and in Figure 3. This is due to standard function notation like having the function name on the left, while mathematical text and visuals such as ours are naturally read left-to-right.