knowt logoknowt logo
HomeExploreExamsBlog
knowt logoKnowt
Rating
0.0(0)
Exam Icon
Take a practice test
Tags
Explore Top Notes
Chapter 29: Prosperity and a New World Order (1988–2000)
noteNote
studied byStudied by 11 people
5.0 Stars(1)
Sociology Mock
noteNote
studied byStudied by 4 people
5.0 Stars(1)
COUNTRIES AFFECTED AND EVENTS
noteNote
studied byStudied by 21 people
5.0 Stars(1)
Chapter 8 - Photosynthesis
noteNote
studied byStudied by 57 people
5.0 Stars(1)
Chapter 1: The Global Tapestry from c. 1200 to c. 1400
noteNote
studied byStudied by 2535 people
4.9 Stars(37)
Chapter 24: The Innate and Adaptive Immune Systems
noteNote
studied byStudied by 4 people
5.0 Stars(1)
knowt logo

nn

Johnsonbaugh-50623 book February 3, 2017 14:23 ❦

❦ ❦ ❦ 3.1 Functions Credit card numbers typically consist of 13, 15, or 16 digits. For example, 4690 3582 1375 4657 (3.1.1) is a hypothetical credit card number. The first digit designates the system. In (3.1.1), the first digit, 4, shows that the card would be a Visa card. The following digits specify other information such as the account number and the bank number. (The precise meaning depends on the type of card.) The last digit is special; it is computed from the preceding digits and is called a check digit. In (3.1.1), the check digit is 7 and is computed from the preceding digits 4690 3582 1375 465. Credit card check digits are used to identify certain erroneous card numbers. It is not a security measure, but rather it is used to help detect errors such as giving a credit card number over the phone and having it transcribed improperly or detecting an error in entering a credit card number while ordering a product online. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ The check digit is computed as follows. Starting from the right and skipping the check digit, double every other number. If the result of doubling is a two-digit number, add the digits; otherwise, use the original digit. The other digits are not modified. 46 9 035 8 213 7 546 5 ↓↓ ↓ ↓↓↓ ↓ ↓↓↓ ↓ ↓↓↓ ↓ Double every other digit. 8 6 18 0 6 5 16 2 2 3 14 5 8 6 10 ↓↓ ↓ ↓↓↓ ↓ ↓↓↓ ↓ ↓↓↓ ↓ Add digits of two-digit numbers. 86 9 065 7 223 5 586 1 Sum the resulting digits 8 + 6 + 9 + 0 + 6 + 5 + 7 + 2 + 2 + 3 + 5 + 5 + 8 + 6 + 1 = 73. If the last digit of the sum is 0, the check digit is 0. Otherwise, subtract the last digit of the sum from 10 to get the check digit, 10−3 = 7. Verify the check digit on your favorite Visa, MasterCard, American Express, or Diners Club card. This method of calculating a check digit is called the Luhn algorithm. It is named after Hans Peter Luhn (1896– 1964), who invented it while at IBM. Although originally patented, it is now in the public domain and is widely used. One common error in copying a number is to change one digit. Each undoubled digit contributes a unique value to the sum (0 → 0, 1 → 1, etc.). Each doubled digit also contributes a unique value to the sum (0 → 0, 1 → 2,..., 4 → 8, 5 → 1, 6 → 3,..., 9 → 9). Thus if a single digit is changed in a credit card number, the sum used in the Luhn algorithm will change by an absolute amount less than 10, and the check digit will change. In the preceding example if 1 is changed to 7, the Luhn algorithm calculation becomes 46 9 035 8 2 7 3 7 546 5 ↓↓ ↓ ↓↓↓ ↓ ↓ ↓ ↓ ↓ ↓↓↓ ↓ Double every other digit 8 6 18 0 6 5 16 2 14 3 14 5 8 6 10 ↓↓ ↓ ↓↓↓ ↓ ↓ ↓ ↓ ↓ ↓↓↓ ↓ Add digits of two-digit numbers. 86 9 065 7 2 5 3 5 586 1 and the sum becomes 8 + 6 + 9 + 0 + 6 + 5 + 7 + 2 + 5 + 3 + 5 + 5 + 8 + 6 + 1 = 76. Therefore the check digit changes to 4. Thus, if 1 is inadvertently transcribed as 7, the error will be detected. Another common error is transposition of adjacent digits. For example, if 82 is inadvertently written as 28, the error will be detected by the Luhn algorithm because the check digit will change (check this). In fact, the Luhn algorithm will detect every transposition of adjacent digits except for 90 and 09 (see Computer Exercise 4). The Luhn algorithm gives an example of a function. A function assigns to each member of a set X exactly one member of a set Y. (The sets X and Y may or may not be the same.) The Luhn algorithm assigns to each integer 10 or greater (so there is a number available to compute a check digit) a single-digit integer, the check digit. In the preceding example, the integer 469035821375465 is assigned the value 7, and the integer 469035827375465 is assigned the value 4. We can represent these assignments as ordered pairs: (469035821375465, 7) and (469035827375465, 4). Formally, we define a function to be a particular kind of set of ordered pairs. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ Definition 3.1.1 Let X and Y be sets. A function f from X to Y is a subset of the Cartesian product X ×Y having the property that for each x ∈ X, there is exactly one y ∈ Y with (x, y) ∈ f . We sometimes denote a function f from X to Y as f: X → Y. The set X is called the domain of f and the set Y is called the codomain of f . The set {y | (x, y) ∈ f} (which is a subset of the codomain Y) is called the range of f . Example 3.1.2 For the check digit function, the domain is the set of positive integers 10 or greater and the range is the set of single-digit integers. We can take the codomain to be any set containing the set of single-digit integers, for example, the set of nonnegative integers. 1 2 3 a b c f X Y Figure 3.1.1 The arrow diagram of the function of Example 3.1.3. There is exactly one arrow from each element in X. Example 3.1.3 The set f = {(1, a), (2, b), (3, a)} is a function from X = {1, 2, 3} to Y = {a, b, c}. Each element of X is assigned a unique value in Y: 1 is assigned the unique value a; 2 is assigned the unique value b; and 3 is assigned the unique value a. We can depict the situation as shown in Figure 3.1.1, where an arrow from j to x means that we assign the letter x to the integer j. We call a picture such as Figure 3.1.1 an arrow diagram. For an arrow diagram to be a function, Definition 3.1.1 requires that there is exactly one arrow from each element in the domain. Notice that Figure 3.1.1 has this property. Definition 3.1.1 allows us to reuse elements in Y. For the function f , the element a in Y is used twice. Further, Definition 3.1.1 does not require us to use all the elements in Y. No element in X is assigned to the element c in Y. The domain of f is X, the codomain of f is Y, and the range of f is {a, b}. Example 3.1.4 The set {(1, a), (2, a), (3, b)} (3.1.2) is not a function from X = {1, 2, 3, 4} to Y = {a, b, c} because the element 4 in X is not assigned to an element in Y. It is also apparent from the arrow diagram (see Figure 3.1.2) that this set is not a function because there is no arrow from 4. The set (3.1.2) is a function from X′ = {1, 2, 3} to Y = {a, b, c}. 1 2 3 4 a b c X Y Figure 3.1.2 The arrow diagram of the set in Example 3.1.4, which is not a function because there is no arrow from 4. Example 3.1.5 The set {(1, a), (2, b), (3, c), (1, b)} is not a function from X = {1, 2, 3} to Y = {a, b, c} because 1 is not assigned a unique element in Y (1 is assigned the values a and b). It is also apparent from the arrow diagram (see Figure 3.1.3) that this set is not a function because there are two arrows from 1. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ 1 2 3 a b c X Y Figure 3.1.3 The arrow diagram of the set in Example 3.1.5, which is not a function because there are two arrows from 1. Given a function f from X to Y, according to Definition 3.1.1, for each element x in the domain X, there is exactly one y in the codomain Y with (x, y) ∈ f . This unique value y is denoted f(x). In other words, f(x) = y is another way to write (x, y) ∈ f . Example 3.1.6 For the function f of Example 3.1.3, we may write f(1) = a, f(2) = b, and f(3) = a. Example 3.1.7 If we call the check digit function L, we may write L(469035821375465) = 7 and L(469035827375465) = 4. The next example shows how we sometimes use the f(x) notation to define a function. Example 3.1.8 Let f be the function defined by the rule f(x) = x2. For example, f(2) = 4, f(−3.5) = 12.25, and f(0) = 0. Although we frequently find functions defined in this way, the definition is incomplete since the domain and codomain are not specified. If we are told that the domain is the set of all real numbers and the codomain is the set of all nonnegative real numbers, in ordered-pair notation, we would have f = {(x, x2 )| x is a real number}. The range of f is the set of all nonnegative real numbers. Example 3.1.9 Most calculators have a 1/x key. If you enter a number and hit the 1/x key, the reciprocal of the number entered (or an approximation to it) is displayed. This function can be defined by the rule R(x) = 1 x . The domain is the set of all numbers that can be entered into the calculator and whose reciprocals can be computed and displayed by the calculator. The range is the set of all the reciprocals that can be computed and displayed. We could define the codomain also to be the set of all the reciprocals that can be computed and displayed. Notice that by the nature of the calculator, the domain and range are finite sets. Another way to visualize a function is to draw its graph. The graph of a function f whose domain and codomain are subsets of the real numbers is obtained by plotting points in the plane that correspond to the elements in f . The domain is contained in the horizontal axis and the codomain is contained in the vertical axis. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ Example 3.1.10 The graph of the function f(x) = x2 is shown in Figure 3.1.4. f(x) 1 4 22 21 21 x Figure 3.1.4 The graph of f(x) = x2. (0, 0) (3, 0) (1, 1) (2, 2) (1, 3) x y Figure 3.1.5 A set that is not a function. The vertical line x = 1 intersects two points in the set. We note that a set S of points in the plane defines a function precisely when each vertical line intersects at most one point of S. If some vertical line contains two or more points of some set, the domain point does not assign a unique codomain point and the set does not define a function (see Figure 3.1.5). Functions involving the modulus operator play an important role in mathematics and computer science. Definition 3.1.11 If x is an integer and y is a positive integer, we define x mod y to be the remainder when x is divided by y. Example 3.1.12 We have 6 mod 2 = 0, 5 mod 1 = 0, 8 mod 12 = 8, 199673 mod 2 = 1. Example 3.1.13 The check digit calculated by the Luhn algorithm can be written [10 − (S mod 10)] mod 10, where S is the sum used in the intermediate step of the calculation. The last digit in S is given by S mod 10. It this digit is 1 through 9, inclusive, 10 − (S mod 10) gives the check digit and the last “mod 10” is unnecessary, but harmless. However, if the last digit in S is 0, 10 − (S mod 10) = 10. In this case, adding the last “mod 10” gives the check digit as 0. Example 3.1.14 What day of the week will it be 365 days from Wednesday? SOLUTION Seven days after Wednesday, it is Wednesday again; 14 days after Wednesday, it is Wednesday again; and in general, if n is a positive integer, 7n days after Wednesday, it is Wednesday again. Thus we need to subtract as many 7’s as possible from 365 and see how many days are left, which is the same as computing 365 mod 7. Since 365 mod 7 = 1, 365 days from Wednesday, it will be one day later, namely Thursday. This explains why, except for leap year, when an extra day is added to February, the identical month and date in consecutive years move forward one day of the week. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ Example 3.1.15 Hash Functions Suppose that we have cells in a computer memory indexed from 0 to 10 (see Figure 3.1.6). We wish to store and retrieve arbitrary nonnegative integers in these cells. One approach is to use a hash function. A hash function takes a data item to be stored or retrieved and computes the first choice for a location for the item. For example, for our problem, to store or retrieve the number n, we might take as the first choice for a location, n mod 11. Our hash function becomes h(n) = n mod 11. Figure 3.1.6 shows the result of storing 15, 558, 32, 132, 102, and 5, in this order, in initially empty cells. 132 0 1 2 102 3 15 4 5 5 257 6 7 558 8 9 32 10 Figure 3.1.6 Cells in a computer memory. Now suppose that we want to store 257. Since h(257) = 4, then 257 should be stored at location 4; however, this position is already occupied. In this case we say that a collision has occurred. More precisely, a collision occurs for a hash function H if H(x) = H(y), but x ̸= y. To handle collisions, a collision resolution policy is required. One simple collision resolution policy is to find the next highest (with 0 assumed to follow 10) unoccupied cell. If we use this collision resolution policy, we would store 257 at location 6 (see Figure 3.1.6). If we want to locate a stored value n, we compute m = h(n) and begin looking at location m. If n is not at this position, we look in the next-highest position (again, 0 is assumed to follow 10); if n is not in this position, we proceed to the next-highest position, and so on. If we reach an empty cell or return to our original position, we conclude that n is not present; otherwise, we obtain the position of n. If collisions occur infrequently, and if when one does occur it is resolved quickly, then hashing provides a very fast method of storing and retrieving data. As an example, personnel data are frequently stored and retrieved by hashing on employee identification numbers. Example 3.1.16 Pseudorandom Numbers Computers are often used to simulate random behavior. A game program might simulate rolling dice, and a client service program might simulate the arrival of customers at a bank. Such programs generate numbers that appear random and are called pseudorandom numbers. For example, the dice-rolling program would need pairs of pseudorandom numbers, each between 1 and 6, to simulate the outcome of rolling dice. Pseudorandom numbers are not truly random; if one knows the program that generates the numbers, one could predict what numbers would occur. The method usually used to generate pseudorandom numbers is called the linear congruential method. This method requires four integers: the modulus m, the multiplier a, the increment c, and a seed s satisfying 2 ≤ a < m, 0 ≤ c < m, and 0 ≤ s < m. We then set x0 = s. The sequence of pseudorandom numbers generated, x1, x2,..., is given by the formula xn = (axn−1 + c) mod m. The formula computes the next pseudorandom number using its immediate predecessor. For example, if m = 11, a = 7, c = 5, and s = 3, then x1 = (ax0 + c) mod m = (7 · 3 + 5) mod 11 = 4 Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ and x2 = (ax1 + c) mod m = (7 · 4 + 5) mod 11 = 0. Similar computations show that the sequence continues: x3 = 5, x4 = 7, x5 = 10, x6 = 9, x7 = 2, x8 = 8, x9 = 6, x10 = 3. Since x10 = 3, which is the value of the seed, the sequence now repeats: 3, 4, 0, 5, 7, .... Much efort has been invested in finding good values for a linear congruential method. Critical simulations such as those involving aircraft and nuclear research require “good” random numbers. In practice, large values are used for m and a. Commonly used values are m = 231 −1 = 2,147,483,647; a = 75 = 16,807; and c = 0, which generate a sequence of 231 − 1 integers before repeating a value. In the 1990s, Daniel Corriveau of Quebec won three straight games of a computer keno game in Montreal, each time choosing 19 of 20 numbers correctly. The odds against this feat are 6 billion to 1. Suspicious ofcials at first refused to pay him. Although Corriveau attributed his success to chaos theory, what in fact happened was that whenever power was cut, the random number generator started with the same seed, thus generating the same sequence of numbers. The embarrassed casino finally paid Corriveau the $600,000 due him. We next define the floor and ceiling of a real number. Definition 3.1.17 The floor of x, denoted ⌊x⌋, is the greatest integer less than or equal to x. The ceiling of x, denoted ⌈x⌉, is the least integer greater than or equal to x. Example 3.1.18 ⌊8.3⌋ = 8, ⌈9.1⌉ = 10, ⌊−8.7⌋ = −9, ⌈−11.3⌉ = −11, ⌈6⌉ = 6, ⌈−8⌉ = −8 The floor of x “rounds x down” while the ceiling of x “rounds x up.” We will use the floor and ceiling functions throughout the book. Example 3.1.19 Figure 3.1.7 shows the graphs of the floor and ceiling functions. A bracket, [ or ], indicates that the point is to be included in the graph; a parenthesis, ( or ), indicates that the point is to be excluded from the graph. … … [ ) [ ) [ ) [ ) [ ) 22 21 123 2 1 21 22 … … 22 21 123 2 1 21 22 ] ] ] ] ( ( ( ( Figure 3.1.7 The graphs of the floor (left graph) and ceiling (right graph) functions. Example 3.1.20 The first-class postage rate for mail up to 13 ounces is 92 cents for the first ounce or fraction thereof and 20 cents for each additional ounce or fraction thereof. The postage P(w) as a function of weight w is given by the equation Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ P(w) = 92 + 20⌈w − 1⌉ 13 ≥ w > 0. The expression ⌈w−1⌉ counts the number of additional ounces beyond 1, with a fraction counting as one additional ounce. As examples, P(3.7) = 92 + 20⌈3.7 − 1⌉ = 92 + 20⌈2.7⌉ = 92 + 20 · 3 = 152, P(2) = 92 + 20⌈2 − 1⌉ = 92 + 20⌈1⌉ = 92 + 20 · 1 = 112. The graph of the function P is shown in Figure 3.1.8. w P(w) … 332 132 112 92 1 2 3 13 ( ] ( ] ( ] ( ] Figure 3.1.8 The graph of the postage function P(w) = 92 + 20⌈w − 1⌉. The Quotient-Remainder Theorem (Theorem 2.5.6) states that if d and n are integers, d > 0, there exist integers q (quotient) and r (remainder) satisfying n = dq + r 0 ≤ r < d. Dividing by d, we obtain n d = q + r d . Since 0 ≤ r/d < 1, ! n d "

! q + r d " = q. Thus, we may compute the quotient q as ⌊n/d⌋. Having computed the quotient q, we may compute the remainder as r = n − dq. We previously introduced the notation n mod d for the remainder. Example 3.1.21 We have 36844/2427 = 15.18088 ...; thus the quotient is q = ⌊36844/2427⌋ = 15. Therefore, the remainder 36844 mod 2427 is r = 36844 − 2427 · 15 = 439. We have n = dq + r or 36844 = 2427 · 15 + 439. Definition 3.1.22 A function f from X to Y is said to be one-to-one (or injective) if for all x1, x2 ∈ X, if f(x1) = f(x2) then x1 = x2. An equivalent way to state Definition 3.1.22 is: If y is an element of the range of f , then there is exactly one x in the domain of f such that f(x) = y. If there were two distinct elements x1 and x2 of the domain of f with f(x1) = y = f(x2), then we would have f(x1) = f(x2) but x1 ≠ x2—a counterexample to the claim that f is one-to-one. Because the amount of potential data is usually so much larger than the available memory, hash functions are usually not one-to-one (see Example 3.1.15). In other words, most hash functions produce collisions. Example 3.1.23 The function f = {(1, b), (3, a), (2, c)} from X = {1, 2, 3} to Y = {a, b, c, d} is one-toone. Example 3.1.24 The function f = {(1, a), (2, b), (3, a)} is not one-to-one since f(1) = a = f(3). Example 3.1.25 If X is the set of persons who have social security numbers and we assign each person x ∈ X his or her social security number SS(x), we obtain a one-to-one function since distinct persons are always assigned distinct social security numbers. It is because this correspondence is one-to-one that the government uses social security numbers as identifiers. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ Example 3.1.26 If a function from X to Y is one-to-one, each element in Y in its arrow diagram will have at most one arrow pointing to it (see Figure 3.1.9). If a function is not one-to-one, some element in Y in its arrow diagram will have two or more arrows pointing to it (see Figure 3.1.10). 1 2 3 a b c d f X Y Figure 3.1.9 The function of Example 3.1.23. This function is one-to-one because each element in Y has at most one arrow pointing to it. This function is not onto Y because there is no arrow pointing to d. 1 2 3 a b c f X Y Figure 3.1.10 A function that is not one-to-one. This function is not one-to-one because a has two arrows pointing to it. This function is not onto Y because there is no arrow pointing to c. Example 3.1.27 Prove that the function f(n) = 2n + 1 from the set of positive integers to the set of positive integers is one-to-one. SOLUTION We must show that for all positive integers n1 and n2, if f(n1) = f(n2), then n1 = n2. So, suppose that f(n1) = f(n2). Using the definition of f , this latter equation translates as 2n1 + 1 = 2n2 + 1. Subtracting 1 from both sides of the equation and then dividing both sides of the equation by 2 yields n1 = n2. Therefore, f is one-to-one. Example 3.1.28 Prove that the function f(n) = 2n − n2 from the set of positive integers to the set of integers is not one-to-one. SOLUTION We must find positive integers n1 and n2, n1 ̸= n2, such that f(n1) = f(n2). By checking the graph (see Figure 3.1.11) or otherwise, we find that f(2) = f(4). Therefore, f is not one-to-one. 7 6 5 4 3 2 1 0 21 12345 f (n) n Figure 3.1.11 The graph of f(n) = 2n − n2. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ If the range of a function f is equal to its codomain Y, the function is said to be onto Y. Definition 3.1.29 A function f from X to Y is said to be onto Y (orsurjective) if for every y ∈ Y, there exists x ∈ X such that f(x) = y. Example 3.1.30 The function f = {(1, a), (2, c), (3, b)} from X = {1, 2, 3} to Y = {a, b, c} is one-to-one and onto Y. Example 3.1.31 The function f = {(1, b), (3, a), (2, c)} from X = {1, 2, 3} to Y = {a, b, c, d} is not onto Y. Example 3.1.32 If a function from X to Y is onto, each element in Y in its arrow diagram will have at least one arrow pointing to it (see Figure 3.1.12). If a function from X to Y is not onto, some element in Y in its arrow diagram will fail to have an arrow pointing to it (see Figures 3.1.9 and 3.1.10). 1 2 3 a b c f X Y Figure 3.1.12 The function of Example 3.1.30. This function is one-to-one because each element in Y has at most one arrow. This function is onto because each element in Y has at least one arrow pointing to it. Example 3.1.33 Prove that the function f(x) = 1 x2 from the set X of nonzero real numbers to the set Y of positive real numbers is onto Y. SOLUTION We must show that for every y ∈ Y, there exists x ∈ X such that f(x) = y. Substituting the formula for f(x), this last equation becomes 1 x2 = y. Solving for x, we find x = ± 1 √y . Notice that 1/ √y is defined because y is a positive real number. If we take x to be the positive square root x = 1 √y , then x ∈ X. (We could just as well have taken x = −1/ √y.) Thus, for every y ∈ Y, there exists x, namely, x = 1/ √y such that Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ f(x) = f(1/ √y) = 1 (1/ √y)2 = y. Therefore, f is onto Y. A function f from X to Y is not onto Y if for some y ∈ Y, for every x ∈ X, f(x) ≠ y. In other words, y is a counterexample to the claim that for every y ∈ Y, there exists x ∈ X such that f(x) = y. Example 3.1.34 Prove that the function f(n) = 2n − 1 from the set X of positive integers to the set Y of positive integers is not onto Y. SOLUTION We must find an element m ∈ Y such that for all n ∈ X, f(n) ̸= m. Since f(n) is an odd integer for all n, we may choose for y any positive, even integer, for example, y = 2. Then y ∈ Y and f(n) ̸= y for all n ∈ X. Thus f is not onto Y. Definition 3.1.35 A function that is both one-to-one and onto is called a bijection. Example 3.1.36 The function f of Example 3.1.30 is a bijection. Example 3.1.37 If f is a bijection from a finite set X to a finite set Y, then |X|=|Y|, that is, the sets have the same cardinality and are the same size. For example, f = {(1, a), (2, b), (3, c), (4, d)} is a bijection from X = {1, 2, 3, 4} to Y = {a, b, c, d)}. Both sets have four elements. In efect, f counts the elements in Y: f(1) = a is the first element in Y; f(2) = b is the second element in Y; and so on. Suppose that f is a one-to-one, onto function from X to Y. It can be shown (see Exercise 116) that {(y, x) | (x, y) ∈ f} is a one-to-one, onto function from Y to X. This new function, denoted f −1, is called f inverse. Example 3.1.38 For the function f = {(1, a), (2, c), (3, b)}, we have f −1 = {(a, 1), (c, 2), (b, 3)}. Example 3.1.39 Given the arrow diagram for a one-to-one, onto function f from X to Y, we can obtain the arrow diagram for f −1 simply by reversing the direction of each arrow (see Figure 3.1.13, which is the arrow diagram for f −1, where f is the function of Figure 3.1.12). 1 2 3 a b c f 21 Y X Figure 3.1.13 The inverse of the function in Figure 3.1.12. The inverse is obtained by reversing all of the arrows in Figure 3.1.12. Example 3.1.40 The function f(x) = 2x is a one-to-one function from the set R of all real numbers onto the set R+ of all positive real numbers. Derive a formula for f −1(y). Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ SOLUTION Suppose that (y, x) is in f −1; that is, f −1 (y) = x. (3.1.3) Then (x, y) ∈ f . Thus, y = 2x. By the definition of logarithm, log2 y = x. (3.1.4) Combining (3.1.3) and (3.1.4), we have f −1(y) = x = log2 y. That is, for each y ∈ R+, f −1(y) is the logarithm to the base 2 of y. We can summarize the situation by saying that the inverse of the exponential function is the logarithm function. Let g be a function from X to Y and let f be a function from Y to Z. Given x ∈ X, we may apply g to determine a unique element y = g(x) ∈ Y. We may then apply f to determine a unique element z = f(y) = f(g(x)) ∈ Z. This compound action is called composition. Definition 3.1.41 Let g be a function from X to Y and let f be a function from Y to Z. The composition of f with g, denoted f ◦ g, is the function (f ◦ g)(x) = f(g(x)) from X to Z. Example 3.1.42 Given g = {(1, a), (2, a), (3, c)}, a function from X = {1, 2, 3} to Y = {a, b, c}, and f = {(a, y), (b, x), (c,z)}, a function from Y to Z = {x, y,z}, the composition function from X to Z is the function f ◦ g = {(1, y), (2, y), (3,z)}. Example 3.1.43 Given the arrow diagram for a function g from X to Y and the arrow diagram for a function f from Y to Z, we can obtain the arrow diagram for the composition f ◦ g simply by “following the arrows” (see Figure 3.1.14). 1 2 3 g g f f X Y x y z Z a b c X Z 1 2 3 x y z Figure 3.1.14 The composition of the functions of Example 3.1.42. The composition is obtained by drawing an arrow from x in X to z in Z provided that there are arrows from x to some y in Y and from y to z. Example 3.1.44 If f(x) = log3 x and g(x) = x4, then f(g(x)) = log3(x4), and g(f(x)) = (log3 x)4. Example 3.1.45 A store ofers 15% of the price of certain items. A coupon is also available that ofers $20 of the price of the same items. The store will honor both discounts. The function D(p) = 0.85p gives the cost with 15% of the price p. The function C(p) = p−20 gives the cost using the $20 coupon. The composition (D ◦ C)(p) = 0.85(p − 20) = 0.85p − 17 gives the cost using first the coupon and then the 15% discount. The composition (C◦D)(p) = 0.85p−20 gives the cost using first the 15% discount and then the coupon. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ We see that regardless of the price of an item, it is always cheapest to use the discount first. Example 3.1.46 Composition sometimes allows us to decompose complicated functions into simpler functions. For example, the function f(x) = √sin 2x can be decomposed into the functions g(x) = √x, h(x) = sin x, w(x) = 2x. We can then write f(x) = g(h(w(x))). This decomposition technique is important in diferential calculus since there are rules for diferentiating simple functions such as g, h, and w and also rules about how to diferentiate the composition of functions. Combining these rules, we can diferentiate more complicated functions. A binary operator on a set X associates with each ordered pair of elements in X one element in X. Definition 3.1.47 A function from X × X to X is called a binary operator on X. Example 3.1.48 Let X = {1, 2,...}. If we define f(x, y) = x + y, where x, y ∈ X, then f is a binary operator on X. Example 3.1.49 If X is a set of propositions, ∧, ∨, →, and ↔ are binary operators on X. A unary operator on a set X associates with each single element of X one element in X. Definition 3.1.50 A function from X to X is called a unary operator on X. Example 3.1.51 Let U be a universal set. If we define f(X) = X, where X ∈ P(U), then f is a unary operator on P(U). Example 3.1.52 If X is a set of propositions, ¬ is a unary operator on X. 3.1 Problem-Solving Tips The key to solving problems involving functions is clearly understanding the definition of function. A function f from X to Y can be thought of in many ways. Formally, f is a subset of X × Y having the property that for every x ∈ X, there is a unique y ∈ Y such that (x, y) ∈ X × Y. Informally, f can be thought of as a mapping of elements from X to Y. The arrow diagram emphasizes this view of a function. For an arrow diagram to be a function, there must be exactly one arrow from each element in X to some element in Y. A function is a very general concept. Any subset of X ×Y having the property that for every x ∈ X, there is a unique y ∈ Y such that (x, y) ∈ X×Y is a function. A function may be defined by listing its members; for example, {(a, 1), (b, 3), (c, 2), (d, 1)} is a function from {a, b, c, d} to {1, 2, 3}. Here, there is apparently no formula for membership; the definition just tells us which pairs make up the function. On the other hand, a function may be defined by a formula. For example, {(n, n + 2) | n is a positive integer} defines a function from the set of positive integers to the set of positive integers. The “formula” for the mapping is “add 2.” Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ The f(x) notation may be used to indicate which element in the codomain is associated with an element x in the domain or to define a function. For example, for the function f = {(a, 1), (b, 3), (c, 2), (d, 1)}, we could write f(a) = 1, f(b) = 3, and so on. Assuming that the domain of definition is the positive integers, the equation g(n) = n+2 defines the function {(n, n + 2) | n is a positive integer} from the set of positive integers to the set of positive integers. To prove that a function f from X to Y is one-to-one, show that for all x1, x2 ∈ X, if f(x1) = f(x2), then x1 = x2. To prove that a function f from X to Y is not one-to-one, find x1, x2 ∈ X, x1 ≠ x2, such that f(x1) = f(x2). To prove that a function f from X to Y is onto, show that for all y ∈ Y, there exists x ∈ X such that f(x) = y. To prove that a function f from X to Y is not onto, find y ∈ Y such that f(x) ≠ y for all x ∈ X.

EJ
Home
Home
Engineering
Engineering
Computer Engineering
Computer Engineering

nn

Johnsonbaugh-50623 book February 3, 2017 14:23 ❦

❦ ❦ ❦ 3.1 Functions Credit card numbers typically consist of 13, 15, or 16 digits. For example, 4690 3582 1375 4657 (3.1.1) is a hypothetical credit card number. The first digit designates the system. In (3.1.1), the first digit, 4, shows that the card would be a Visa card. The following digits specify other information such as the account number and the bank number. (The precise meaning depends on the type of card.) The last digit is special; it is computed from the preceding digits and is called a check digit. In (3.1.1), the check digit is 7 and is computed from the preceding digits 4690 3582 1375 465. Credit card check digits are used to identify certain erroneous card numbers. It is not a security measure, but rather it is used to help detect errors such as giving a credit card number over the phone and having it transcribed improperly or detecting an error in entering a credit card number while ordering a product online. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ The check digit is computed as follows. Starting from the right and skipping the check digit, double every other number. If the result of doubling is a two-digit number, add the digits; otherwise, use the original digit. The other digits are not modified. 46 9 035 8 213 7 546 5 ↓↓ ↓ ↓↓↓ ↓ ↓↓↓ ↓ ↓↓↓ ↓ Double every other digit. 8 6 18 0 6 5 16 2 2 3 14 5 8 6 10 ↓↓ ↓ ↓↓↓ ↓ ↓↓↓ ↓ ↓↓↓ ↓ Add digits of two-digit numbers. 86 9 065 7 223 5 586 1 Sum the resulting digits 8 + 6 + 9 + 0 + 6 + 5 + 7 + 2 + 2 + 3 + 5 + 5 + 8 + 6 + 1 = 73. If the last digit of the sum is 0, the check digit is 0. Otherwise, subtract the last digit of the sum from 10 to get the check digit, 10−3 = 7. Verify the check digit on your favorite Visa, MasterCard, American Express, or Diners Club card. This method of calculating a check digit is called the Luhn algorithm. It is named after Hans Peter Luhn (1896– 1964), who invented it while at IBM. Although originally patented, it is now in the public domain and is widely used. One common error in copying a number is to change one digit. Each undoubled digit contributes a unique value to the sum (0 → 0, 1 → 1, etc.). Each doubled digit also contributes a unique value to the sum (0 → 0, 1 → 2,..., 4 → 8, 5 → 1, 6 → 3,..., 9 → 9). Thus if a single digit is changed in a credit card number, the sum used in the Luhn algorithm will change by an absolute amount less than 10, and the check digit will change. In the preceding example if 1 is changed to 7, the Luhn algorithm calculation becomes 46 9 035 8 2 7 3 7 546 5 ↓↓ ↓ ↓↓↓ ↓ ↓ ↓ ↓ ↓ ↓↓↓ ↓ Double every other digit 8 6 18 0 6 5 16 2 14 3 14 5 8 6 10 ↓↓ ↓ ↓↓↓ ↓ ↓ ↓ ↓ ↓ ↓↓↓ ↓ Add digits of two-digit numbers. 86 9 065 7 2 5 3 5 586 1 and the sum becomes 8 + 6 + 9 + 0 + 6 + 5 + 7 + 2 + 5 + 3 + 5 + 5 + 8 + 6 + 1 = 76. Therefore the check digit changes to 4. Thus, if 1 is inadvertently transcribed as 7, the error will be detected. Another common error is transposition of adjacent digits. For example, if 82 is inadvertently written as 28, the error will be detected by the Luhn algorithm because the check digit will change (check this). In fact, the Luhn algorithm will detect every transposition of adjacent digits except for 90 and 09 (see Computer Exercise 4). The Luhn algorithm gives an example of a function. A function assigns to each member of a set X exactly one member of a set Y. (The sets X and Y may or may not be the same.) The Luhn algorithm assigns to each integer 10 or greater (so there is a number available to compute a check digit) a single-digit integer, the check digit. In the preceding example, the integer 469035821375465 is assigned the value 7, and the integer 469035827375465 is assigned the value 4. We can represent these assignments as ordered pairs: (469035821375465, 7) and (469035827375465, 4). Formally, we define a function to be a particular kind of set of ordered pairs. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ Definition 3.1.1 Let X and Y be sets. A function f from X to Y is a subset of the Cartesian product X ×Y having the property that for each x ∈ X, there is exactly one y ∈ Y with (x, y) ∈ f . We sometimes denote a function f from X to Y as f: X → Y. The set X is called the domain of f and the set Y is called the codomain of f . The set {y | (x, y) ∈ f} (which is a subset of the codomain Y) is called the range of f . Example 3.1.2 For the check digit function, the domain is the set of positive integers 10 or greater and the range is the set of single-digit integers. We can take the codomain to be any set containing the set of single-digit integers, for example, the set of nonnegative integers. 1 2 3 a b c f X Y Figure 3.1.1 The arrow diagram of the function of Example 3.1.3. There is exactly one arrow from each element in X. Example 3.1.3 The set f = {(1, a), (2, b), (3, a)} is a function from X = {1, 2, 3} to Y = {a, b, c}. Each element of X is assigned a unique value in Y: 1 is assigned the unique value a; 2 is assigned the unique value b; and 3 is assigned the unique value a. We can depict the situation as shown in Figure 3.1.1, where an arrow from j to x means that we assign the letter x to the integer j. We call a picture such as Figure 3.1.1 an arrow diagram. For an arrow diagram to be a function, Definition 3.1.1 requires that there is exactly one arrow from each element in the domain. Notice that Figure 3.1.1 has this property. Definition 3.1.1 allows us to reuse elements in Y. For the function f , the element a in Y is used twice. Further, Definition 3.1.1 does not require us to use all the elements in Y. No element in X is assigned to the element c in Y. The domain of f is X, the codomain of f is Y, and the range of f is {a, b}. Example 3.1.4 The set {(1, a), (2, a), (3, b)} (3.1.2) is not a function from X = {1, 2, 3, 4} to Y = {a, b, c} because the element 4 in X is not assigned to an element in Y. It is also apparent from the arrow diagram (see Figure 3.1.2) that this set is not a function because there is no arrow from 4. The set (3.1.2) is a function from X′ = {1, 2, 3} to Y = {a, b, c}. 1 2 3 4 a b c X Y Figure 3.1.2 The arrow diagram of the set in Example 3.1.4, which is not a function because there is no arrow from 4. Example 3.1.5 The set {(1, a), (2, b), (3, c), (1, b)} is not a function from X = {1, 2, 3} to Y = {a, b, c} because 1 is not assigned a unique element in Y (1 is assigned the values a and b). It is also apparent from the arrow diagram (see Figure 3.1.3) that this set is not a function because there are two arrows from 1. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ 1 2 3 a b c X Y Figure 3.1.3 The arrow diagram of the set in Example 3.1.5, which is not a function because there are two arrows from 1. Given a function f from X to Y, according to Definition 3.1.1, for each element x in the domain X, there is exactly one y in the codomain Y with (x, y) ∈ f . This unique value y is denoted f(x). In other words, f(x) = y is another way to write (x, y) ∈ f . Example 3.1.6 For the function f of Example 3.1.3, we may write f(1) = a, f(2) = b, and f(3) = a. Example 3.1.7 If we call the check digit function L, we may write L(469035821375465) = 7 and L(469035827375465) = 4. The next example shows how we sometimes use the f(x) notation to define a function. Example 3.1.8 Let f be the function defined by the rule f(x) = x2. For example, f(2) = 4, f(−3.5) = 12.25, and f(0) = 0. Although we frequently find functions defined in this way, the definition is incomplete since the domain and codomain are not specified. If we are told that the domain is the set of all real numbers and the codomain is the set of all nonnegative real numbers, in ordered-pair notation, we would have f = {(x, x2 )| x is a real number}. The range of f is the set of all nonnegative real numbers. Example 3.1.9 Most calculators have a 1/x key. If you enter a number and hit the 1/x key, the reciprocal of the number entered (or an approximation to it) is displayed. This function can be defined by the rule R(x) = 1 x . The domain is the set of all numbers that can be entered into the calculator and whose reciprocals can be computed and displayed by the calculator. The range is the set of all the reciprocals that can be computed and displayed. We could define the codomain also to be the set of all the reciprocals that can be computed and displayed. Notice that by the nature of the calculator, the domain and range are finite sets. Another way to visualize a function is to draw its graph. The graph of a function f whose domain and codomain are subsets of the real numbers is obtained by plotting points in the plane that correspond to the elements in f . The domain is contained in the horizontal axis and the codomain is contained in the vertical axis. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ Example 3.1.10 The graph of the function f(x) = x2 is shown in Figure 3.1.4. f(x) 1 4 22 21 21 x Figure 3.1.4 The graph of f(x) = x2. (0, 0) (3, 0) (1, 1) (2, 2) (1, 3) x y Figure 3.1.5 A set that is not a function. The vertical line x = 1 intersects two points in the set. We note that a set S of points in the plane defines a function precisely when each vertical line intersects at most one point of S. If some vertical line contains two or more points of some set, the domain point does not assign a unique codomain point and the set does not define a function (see Figure 3.1.5). Functions involving the modulus operator play an important role in mathematics and computer science. Definition 3.1.11 If x is an integer and y is a positive integer, we define x mod y to be the remainder when x is divided by y. Example 3.1.12 We have 6 mod 2 = 0, 5 mod 1 = 0, 8 mod 12 = 8, 199673 mod 2 = 1. Example 3.1.13 The check digit calculated by the Luhn algorithm can be written [10 − (S mod 10)] mod 10, where S is the sum used in the intermediate step of the calculation. The last digit in S is given by S mod 10. It this digit is 1 through 9, inclusive, 10 − (S mod 10) gives the check digit and the last “mod 10” is unnecessary, but harmless. However, if the last digit in S is 0, 10 − (S mod 10) = 10. In this case, adding the last “mod 10” gives the check digit as 0. Example 3.1.14 What day of the week will it be 365 days from Wednesday? SOLUTION Seven days after Wednesday, it is Wednesday again; 14 days after Wednesday, it is Wednesday again; and in general, if n is a positive integer, 7n days after Wednesday, it is Wednesday again. Thus we need to subtract as many 7’s as possible from 365 and see how many days are left, which is the same as computing 365 mod 7. Since 365 mod 7 = 1, 365 days from Wednesday, it will be one day later, namely Thursday. This explains why, except for leap year, when an extra day is added to February, the identical month and date in consecutive years move forward one day of the week. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ Example 3.1.15 Hash Functions Suppose that we have cells in a computer memory indexed from 0 to 10 (see Figure 3.1.6). We wish to store and retrieve arbitrary nonnegative integers in these cells. One approach is to use a hash function. A hash function takes a data item to be stored or retrieved and computes the first choice for a location for the item. For example, for our problem, to store or retrieve the number n, we might take as the first choice for a location, n mod 11. Our hash function becomes h(n) = n mod 11. Figure 3.1.6 shows the result of storing 15, 558, 32, 132, 102, and 5, in this order, in initially empty cells. 132 0 1 2 102 3 15 4 5 5 257 6 7 558 8 9 32 10 Figure 3.1.6 Cells in a computer memory. Now suppose that we want to store 257. Since h(257) = 4, then 257 should be stored at location 4; however, this position is already occupied. In this case we say that a collision has occurred. More precisely, a collision occurs for a hash function H if H(x) = H(y), but x ̸= y. To handle collisions, a collision resolution policy is required. One simple collision resolution policy is to find the next highest (with 0 assumed to follow 10) unoccupied cell. If we use this collision resolution policy, we would store 257 at location 6 (see Figure 3.1.6). If we want to locate a stored value n, we compute m = h(n) and begin looking at location m. If n is not at this position, we look in the next-highest position (again, 0 is assumed to follow 10); if n is not in this position, we proceed to the next-highest position, and so on. If we reach an empty cell or return to our original position, we conclude that n is not present; otherwise, we obtain the position of n. If collisions occur infrequently, and if when one does occur it is resolved quickly, then hashing provides a very fast method of storing and retrieving data. As an example, personnel data are frequently stored and retrieved by hashing on employee identification numbers. Example 3.1.16 Pseudorandom Numbers Computers are often used to simulate random behavior. A game program might simulate rolling dice, and a client service program might simulate the arrival of customers at a bank. Such programs generate numbers that appear random and are called pseudorandom numbers. For example, the dice-rolling program would need pairs of pseudorandom numbers, each between 1 and 6, to simulate the outcome of rolling dice. Pseudorandom numbers are not truly random; if one knows the program that generates the numbers, one could predict what numbers would occur. The method usually used to generate pseudorandom numbers is called the linear congruential method. This method requires four integers: the modulus m, the multiplier a, the increment c, and a seed s satisfying 2 ≤ a < m, 0 ≤ c < m, and 0 ≤ s < m. We then set x0 = s. The sequence of pseudorandom numbers generated, x1, x2,..., is given by the formula xn = (axn−1 + c) mod m. The formula computes the next pseudorandom number using its immediate predecessor. For example, if m = 11, a = 7, c = 5, and s = 3, then x1 = (ax0 + c) mod m = (7 · 3 + 5) mod 11 = 4 Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ and x2 = (ax1 + c) mod m = (7 · 4 + 5) mod 11 = 0. Similar computations show that the sequence continues: x3 = 5, x4 = 7, x5 = 10, x6 = 9, x7 = 2, x8 = 8, x9 = 6, x10 = 3. Since x10 = 3, which is the value of the seed, the sequence now repeats: 3, 4, 0, 5, 7, .... Much efort has been invested in finding good values for a linear congruential method. Critical simulations such as those involving aircraft and nuclear research require “good” random numbers. In practice, large values are used for m and a. Commonly used values are m = 231 −1 = 2,147,483,647; a = 75 = 16,807; and c = 0, which generate a sequence of 231 − 1 integers before repeating a value. In the 1990s, Daniel Corriveau of Quebec won three straight games of a computer keno game in Montreal, each time choosing 19 of 20 numbers correctly. The odds against this feat are 6 billion to 1. Suspicious ofcials at first refused to pay him. Although Corriveau attributed his success to chaos theory, what in fact happened was that whenever power was cut, the random number generator started with the same seed, thus generating the same sequence of numbers. The embarrassed casino finally paid Corriveau the $600,000 due him. We next define the floor and ceiling of a real number. Definition 3.1.17 The floor of x, denoted ⌊x⌋, is the greatest integer less than or equal to x. The ceiling of x, denoted ⌈x⌉, is the least integer greater than or equal to x. Example 3.1.18 ⌊8.3⌋ = 8, ⌈9.1⌉ = 10, ⌊−8.7⌋ = −9, ⌈−11.3⌉ = −11, ⌈6⌉ = 6, ⌈−8⌉ = −8 The floor of x “rounds x down” while the ceiling of x “rounds x up.” We will use the floor and ceiling functions throughout the book. Example 3.1.19 Figure 3.1.7 shows the graphs of the floor and ceiling functions. A bracket, [ or ], indicates that the point is to be included in the graph; a parenthesis, ( or ), indicates that the point is to be excluded from the graph. … … [ ) [ ) [ ) [ ) [ ) 22 21 123 2 1 21 22 … … 22 21 123 2 1 21 22 ] ] ] ] ( ( ( ( Figure 3.1.7 The graphs of the floor (left graph) and ceiling (right graph) functions. Example 3.1.20 The first-class postage rate for mail up to 13 ounces is 92 cents for the first ounce or fraction thereof and 20 cents for each additional ounce or fraction thereof. The postage P(w) as a function of weight w is given by the equation Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ P(w) = 92 + 20⌈w − 1⌉ 13 ≥ w > 0. The expression ⌈w−1⌉ counts the number of additional ounces beyond 1, with a fraction counting as one additional ounce. As examples, P(3.7) = 92 + 20⌈3.7 − 1⌉ = 92 + 20⌈2.7⌉ = 92 + 20 · 3 = 152, P(2) = 92 + 20⌈2 − 1⌉ = 92 + 20⌈1⌉ = 92 + 20 · 1 = 112. The graph of the function P is shown in Figure 3.1.8. w P(w) … 332 132 112 92 1 2 3 13 ( ] ( ] ( ] ( ] Figure 3.1.8 The graph of the postage function P(w) = 92 + 20⌈w − 1⌉. The Quotient-Remainder Theorem (Theorem 2.5.6) states that if d and n are integers, d > 0, there exist integers q (quotient) and r (remainder) satisfying n = dq + r 0 ≤ r < d. Dividing by d, we obtain n d = q + r d . Since 0 ≤ r/d < 1, ! n d "

! q + r d " = q. Thus, we may compute the quotient q as ⌊n/d⌋. Having computed the quotient q, we may compute the remainder as r = n − dq. We previously introduced the notation n mod d for the remainder. Example 3.1.21 We have 36844/2427 = 15.18088 ...; thus the quotient is q = ⌊36844/2427⌋ = 15. Therefore, the remainder 36844 mod 2427 is r = 36844 − 2427 · 15 = 439. We have n = dq + r or 36844 = 2427 · 15 + 439. Definition 3.1.22 A function f from X to Y is said to be one-to-one (or injective) if for all x1, x2 ∈ X, if f(x1) = f(x2) then x1 = x2. An equivalent way to state Definition 3.1.22 is: If y is an element of the range of f , then there is exactly one x in the domain of f such that f(x) = y. If there were two distinct elements x1 and x2 of the domain of f with f(x1) = y = f(x2), then we would have f(x1) = f(x2) but x1 ≠ x2—a counterexample to the claim that f is one-to-one. Because the amount of potential data is usually so much larger than the available memory, hash functions are usually not one-to-one (see Example 3.1.15). In other words, most hash functions produce collisions. Example 3.1.23 The function f = {(1, b), (3, a), (2, c)} from X = {1, 2, 3} to Y = {a, b, c, d} is one-toone. Example 3.1.24 The function f = {(1, a), (2, b), (3, a)} is not one-to-one since f(1) = a = f(3). Example 3.1.25 If X is the set of persons who have social security numbers and we assign each person x ∈ X his or her social security number SS(x), we obtain a one-to-one function since distinct persons are always assigned distinct social security numbers. It is because this correspondence is one-to-one that the government uses social security numbers as identifiers. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ Example 3.1.26 If a function from X to Y is one-to-one, each element in Y in its arrow diagram will have at most one arrow pointing to it (see Figure 3.1.9). If a function is not one-to-one, some element in Y in its arrow diagram will have two or more arrows pointing to it (see Figure 3.1.10). 1 2 3 a b c d f X Y Figure 3.1.9 The function of Example 3.1.23. This function is one-to-one because each element in Y has at most one arrow pointing to it. This function is not onto Y because there is no arrow pointing to d. 1 2 3 a b c f X Y Figure 3.1.10 A function that is not one-to-one. This function is not one-to-one because a has two arrows pointing to it. This function is not onto Y because there is no arrow pointing to c. Example 3.1.27 Prove that the function f(n) = 2n + 1 from the set of positive integers to the set of positive integers is one-to-one. SOLUTION We must show that for all positive integers n1 and n2, if f(n1) = f(n2), then n1 = n2. So, suppose that f(n1) = f(n2). Using the definition of f , this latter equation translates as 2n1 + 1 = 2n2 + 1. Subtracting 1 from both sides of the equation and then dividing both sides of the equation by 2 yields n1 = n2. Therefore, f is one-to-one. Example 3.1.28 Prove that the function f(n) = 2n − n2 from the set of positive integers to the set of integers is not one-to-one. SOLUTION We must find positive integers n1 and n2, n1 ̸= n2, such that f(n1) = f(n2). By checking the graph (see Figure 3.1.11) or otherwise, we find that f(2) = f(4). Therefore, f is not one-to-one. 7 6 5 4 3 2 1 0 21 12345 f (n) n Figure 3.1.11 The graph of f(n) = 2n − n2. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ If the range of a function f is equal to its codomain Y, the function is said to be onto Y. Definition 3.1.29 A function f from X to Y is said to be onto Y (orsurjective) if for every y ∈ Y, there exists x ∈ X such that f(x) = y. Example 3.1.30 The function f = {(1, a), (2, c), (3, b)} from X = {1, 2, 3} to Y = {a, b, c} is one-to-one and onto Y. Example 3.1.31 The function f = {(1, b), (3, a), (2, c)} from X = {1, 2, 3} to Y = {a, b, c, d} is not onto Y. Example 3.1.32 If a function from X to Y is onto, each element in Y in its arrow diagram will have at least one arrow pointing to it (see Figure 3.1.12). If a function from X to Y is not onto, some element in Y in its arrow diagram will fail to have an arrow pointing to it (see Figures 3.1.9 and 3.1.10). 1 2 3 a b c f X Y Figure 3.1.12 The function of Example 3.1.30. This function is one-to-one because each element in Y has at most one arrow. This function is onto because each element in Y has at least one arrow pointing to it. Example 3.1.33 Prove that the function f(x) = 1 x2 from the set X of nonzero real numbers to the set Y of positive real numbers is onto Y. SOLUTION We must show that for every y ∈ Y, there exists x ∈ X such that f(x) = y. Substituting the formula for f(x), this last equation becomes 1 x2 = y. Solving for x, we find x = ± 1 √y . Notice that 1/ √y is defined because y is a positive real number. If we take x to be the positive square root x = 1 √y , then x ∈ X. (We could just as well have taken x = −1/ √y.) Thus, for every y ∈ Y, there exists x, namely, x = 1/ √y such that Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ f(x) = f(1/ √y) = 1 (1/ √y)2 = y. Therefore, f is onto Y. A function f from X to Y is not onto Y if for some y ∈ Y, for every x ∈ X, f(x) ≠ y. In other words, y is a counterexample to the claim that for every y ∈ Y, there exists x ∈ X such that f(x) = y. Example 3.1.34 Prove that the function f(n) = 2n − 1 from the set X of positive integers to the set Y of positive integers is not onto Y. SOLUTION We must find an element m ∈ Y such that for all n ∈ X, f(n) ̸= m. Since f(n) is an odd integer for all n, we may choose for y any positive, even integer, for example, y = 2. Then y ∈ Y and f(n) ̸= y for all n ∈ X. Thus f is not onto Y. Definition 3.1.35 A function that is both one-to-one and onto is called a bijection. Example 3.1.36 The function f of Example 3.1.30 is a bijection. Example 3.1.37 If f is a bijection from a finite set X to a finite set Y, then |X|=|Y|, that is, the sets have the same cardinality and are the same size. For example, f = {(1, a), (2, b), (3, c), (4, d)} is a bijection from X = {1, 2, 3, 4} to Y = {a, b, c, d)}. Both sets have four elements. In efect, f counts the elements in Y: f(1) = a is the first element in Y; f(2) = b is the second element in Y; and so on. Suppose that f is a one-to-one, onto function from X to Y. It can be shown (see Exercise 116) that {(y, x) | (x, y) ∈ f} is a one-to-one, onto function from Y to X. This new function, denoted f −1, is called f inverse. Example 3.1.38 For the function f = {(1, a), (2, c), (3, b)}, we have f −1 = {(a, 1), (c, 2), (b, 3)}. Example 3.1.39 Given the arrow diagram for a one-to-one, onto function f from X to Y, we can obtain the arrow diagram for f −1 simply by reversing the direction of each arrow (see Figure 3.1.13, which is the arrow diagram for f −1, where f is the function of Figure 3.1.12). 1 2 3 a b c f 21 Y X Figure 3.1.13 The inverse of the function in Figure 3.1.12. The inverse is obtained by reversing all of the arrows in Figure 3.1.12. Example 3.1.40 The function f(x) = 2x is a one-to-one function from the set R of all real numbers onto the set R+ of all positive real numbers. Derive a formula for f −1(y). Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ SOLUTION Suppose that (y, x) is in f −1; that is, f −1 (y) = x. (3.1.3) Then (x, y) ∈ f . Thus, y = 2x. By the definition of logarithm, log2 y = x. (3.1.4) Combining (3.1.3) and (3.1.4), we have f −1(y) = x = log2 y. That is, for each y ∈ R+, f −1(y) is the logarithm to the base 2 of y. We can summarize the situation by saying that the inverse of the exponential function is the logarithm function. Let g be a function from X to Y and let f be a function from Y to Z. Given x ∈ X, we may apply g to determine a unique element y = g(x) ∈ Y. We may then apply f to determine a unique element z = f(y) = f(g(x)) ∈ Z. This compound action is called composition. Definition 3.1.41 Let g be a function from X to Y and let f be a function from Y to Z. The composition of f with g, denoted f ◦ g, is the function (f ◦ g)(x) = f(g(x)) from X to Z. Example 3.1.42 Given g = {(1, a), (2, a), (3, c)}, a function from X = {1, 2, 3} to Y = {a, b, c}, and f = {(a, y), (b, x), (c,z)}, a function from Y to Z = {x, y,z}, the composition function from X to Z is the function f ◦ g = {(1, y), (2, y), (3,z)}. Example 3.1.43 Given the arrow diagram for a function g from X to Y and the arrow diagram for a function f from Y to Z, we can obtain the arrow diagram for the composition f ◦ g simply by “following the arrows” (see Figure 3.1.14). 1 2 3 g g f f X Y x y z Z a b c X Z 1 2 3 x y z Figure 3.1.14 The composition of the functions of Example 3.1.42. The composition is obtained by drawing an arrow from x in X to z in Z provided that there are arrows from x to some y in Y and from y to z. Example 3.1.44 If f(x) = log3 x and g(x) = x4, then f(g(x)) = log3(x4), and g(f(x)) = (log3 x)4. Example 3.1.45 A store ofers 15% of the price of certain items. A coupon is also available that ofers $20 of the price of the same items. The store will honor both discounts. The function D(p) = 0.85p gives the cost with 15% of the price p. The function C(p) = p−20 gives the cost using the $20 coupon. The composition (D ◦ C)(p) = 0.85(p − 20) = 0.85p − 17 gives the cost using first the coupon and then the 15% discount. The composition (C◦D)(p) = 0.85p−20 gives the cost using first the 15% discount and then the coupon. Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ We see that regardless of the price of an item, it is always cheapest to use the discount first. Example 3.1.46 Composition sometimes allows us to decompose complicated functions into simpler functions. For example, the function f(x) = √sin 2x can be decomposed into the functions g(x) = √x, h(x) = sin x, w(x) = 2x. We can then write f(x) = g(h(w(x))). This decomposition technique is important in diferential calculus since there are rules for diferentiating simple functions such as g, h, and w and also rules about how to diferentiate the composition of functions. Combining these rules, we can diferentiate more complicated functions. A binary operator on a set X associates with each ordered pair of elements in X one element in X. Definition 3.1.47 A function from X × X to X is called a binary operator on X. Example 3.1.48 Let X = {1, 2,...}. If we define f(x, y) = x + y, where x, y ∈ X, then f is a binary operator on X. Example 3.1.49 If X is a set of propositions, ∧, ∨, →, and ↔ are binary operators on X. A unary operator on a set X associates with each single element of X one element in X. Definition 3.1.50 A function from X to X is called a unary operator on X. Example 3.1.51 Let U be a universal set. If we define f(X) = X, where X ∈ P(U), then f is a unary operator on P(U). Example 3.1.52 If X is a set of propositions, ¬ is a unary operator on X. 3.1 Problem-Solving Tips The key to solving problems involving functions is clearly understanding the definition of function. A function f from X to Y can be thought of in many ways. Formally, f is a subset of X × Y having the property that for every x ∈ X, there is a unique y ∈ Y such that (x, y) ∈ X × Y. Informally, f can be thought of as a mapping of elements from X to Y. The arrow diagram emphasizes this view of a function. For an arrow diagram to be a function, there must be exactly one arrow from each element in X to some element in Y. A function is a very general concept. Any subset of X ×Y having the property that for every x ∈ X, there is a unique y ∈ Y such that (x, y) ∈ X×Y is a function. A function may be defined by listing its members; for example, {(a, 1), (b, 3), (c, 2), (d, 1)} is a function from {a, b, c, d} to {1, 2, 3}. Here, there is apparently no formula for membership; the definition just tells us which pairs make up the function. On the other hand, a function may be defined by a formula. For example, {(n, n + 2) | n is a positive integer} defines a function from the set of positive integers to the set of positive integers. The “formula” for the mapping is “add 2.” Johnsonbaugh-50623 book February 3, 2017 14:23 ❦ ❦ ❦ ❦ The f(x) notation may be used to indicate which element in the codomain is associated with an element x in the domain or to define a function. For example, for the function f = {(a, 1), (b, 3), (c, 2), (d, 1)}, we could write f(a) = 1, f(b) = 3, and so on. Assuming that the domain of definition is the positive integers, the equation g(n) = n+2 defines the function {(n, n + 2) | n is a positive integer} from the set of positive integers to the set of positive integers. To prove that a function f from X to Y is one-to-one, show that for all x1, x2 ∈ X, if f(x1) = f(x2), then x1 = x2. To prove that a function f from X to Y is not one-to-one, find x1, x2 ∈ X, x1 ≠ x2, such that f(x1) = f(x2). To prove that a function f from X to Y is onto, show that for all y ∈ Y, there exists x ∈ X such that f(x) = y. To prove that a function f from X to Y is not onto, find y ∈ Y such that f(x) ≠ y for all x ∈ X.