Let X = {1, 2, 3, 4} and Y = {a, b, c, d, e}. Define g: X

Problem 53E Exercise refers to the Euler phi function, denoted ?, which is defined as follows: For each integer n ? 1, ?(n) is the number of positive integers less than or equal to n that have no common factors with n except ±1. For example, ?(10) = 4 because there are four positive integers less than or equal to 10 that have no common factors with 10 except ±1; namely, 1, 3, 7, and 9. Exercise Prove that there are infinitely many integers n for which ?(n) is a perfect square.

Problem 1E Let X = {1, 3, 5} and Y = {s, t, u, v}. Define f: X ? Y by the following arrow diagram. a. Write the domain of f and the co-domain of f. ________________ b. Find f (1), f (3), and f (5). ________________ c. What is the range of f? ________________ d. Is 3 an inverse image of s? Is 1 an inverse image of u? ________________ e. What is the inverse image of s? of u? of v? ________________ f. Represent f as a set of ordered pairs.

Problem 2E Let X = {1, 3, 5} and Y = {a, b, c, d}. Define g: X ?Y by the following arrow diagram. a. Write the domain of g and the co-domain of g. ________________ b. Find g(1), g(3), and g(5). ________________ c. What is the range of g? ________________ d. Is 3 an inverse image of a? Is 1 an inverse image of b? ________________ e. What is the inverse image of b? of c? ________________ f. Represent g as a set of ordered pairs.

Problem 3E Indicate whether the statements in parts (a)-(d) are true or false. Justify your answers. a. If two elements in the domain of a function are equal, then their images in the co-domain are equal. ________________ b. If two elements in the co-domain of a function are equal, then their preimages in the domain are also equal. ________________ c. A function can have the same output for more than one input. ________________ d. A function can have the same input for more than one output.

Problem 5E Let IZ be the identity function defined on the set of all integers, and suppose that e, , K(t), and ukj all represent integers. Find a. Iz(e) ________________ b. ________________ c. Iz(K(t)) ________________ d. Iz(ukj)

Problem 6E Find functions defined on the set of nonnegative integers that define the sequences whose first six terms are given below. a. ________________ b. 0, ?2, 4, ?6, 8, ?10

Problem 4E a. Find all functions from X = {a, b} to Y = {u, v}. b. Find all functions from X = {a, b, c} to Y = {u}. c. Find all functions from X = {a, b, c} to Y = {u, v}

Problem 7E Let A = {1, 2, 3, 4, 5} and define a function F: P(A) ? Z as follows: For all sets X in P(A), Find the following: a. F({1, 3, 4}) ________________ b. ________________ c. F({2, 3}) ________________ d. F({2, 3, 4, 5})

Problem 8E Let J5 = {0, 1, 2, 3, 4}, and define a function F: J5 ? J5 as follows: For each x ? J5, F(x) = (x3 + 2x + 4) mod 5. Find the following: a. F(0) ________________ b. F(1) ________________ c. F(2) ________________ d. F(3) ________________ e. F(4)

Problem 9E Define a function S: Z+ ? Z+ as follows: For each positive integer n, S(n)= the sum of the positive divisors of n. Find the following: a. S(1) ________________ b. S(15) ________________ c. S(17) ________________ d. S(5) ________________ e. S(18) ________________ f. S(21)

Problem 10E Let D be the set of all finite subsets of positive integers. Define a function T: Z+ ? D as follows: For each positive integer n, T(n) = the set of positive divisors of n. Find the following: a. T(1) ________________ b. T(15) ________________ c. T(17) ________________ d. T(5) ________________ e. T(18) ________________ f. T(21)

Problem 12E Define G: J5× J5 ? J5 × J5 as follows: For all (a, b) ? J5 × J5, G(a, b) = ((2a + 1) mod 5, (3b ? 2) mod 5). Find the following: a. G(4, 4) ________________ b. G(2, 1) ________________ c. G(3, 2) ________________ d. G(1, 5)

Problem 13E Let J5 = {0, 1, 2, 3, 4}, and define functions f: J5?J5 and g : J5? J5 as follows: For each x ? J5, f (x) = (x + 4)2 mod 5 and g(x) = (x2 + 3x + 1) mod 5. Is f = g? Explain.

Problem 14E Let J5 = {0, 1, 2, 3, 4}, and define functions h: J5?J5 and k: J5? J5 as follows: For each x ? J5, h(x) = (x + 3)3 mod 5 and k(x) = (x3 + 4x2 + 2x + 2) mod 5. Is h = k? Explain.

Problem 11E Define F: Z × Z ? Z × Z as follows: For all ordered pairs (a, b) of integers, F(a, b) = (2a + 1, 3b ? 2). Find the following: a. F(4, 4) ________________ b. F(2, 1) ________________ c. F(3, 2) ________________ d. F(1,5)

Problem 15E Let F and G be functions from the set of all real numbers to itself. Define the product functions F • G: R ? R and G • F: R ? R as follows: For all x ? R, (F • G)(x) = F(x) • G(x) (G • F)(x) = G(x) • F(x) Does F • G = G • F? Explain.

Problem 16E Let F and G be functions from the set of all real numbers to itself. Define new functions F ? G:R ? R and G ? F: R ? R as follows: For all x ? R, (F ? G)(x) = F(x) ? G(x) (G ? F)(x) = G(x) ? F(x) Does F ? G = G ? F? Explain.

Problem 17E Use the definition of logarithm to fill in the blanks below. a. log2 8 = 3 because _____. ________________ b. because _____. ________________ c. log4 4 = 1 because _____. ________________ d. log3(3n) = n because _____. ________________ e. log4 1 = 0 because _____.

Problem 18E Find exact values for each of the following quantities. Do not use a calculator. a. log3 81 ________________ b. log2 1024 ________________ c. ________________ d. log2 1 ________________ e. ________________ f. log3 3 ________________ g. log2(2k)

Problem 19E Use the definition of logarithm to prove that for any positive real number b with b ? 1 , logb b = 1.

Problem 20E Use the definition of logarithm to prove that for any positive real number b with b ? 1, logb 1 = 0.

Problem 21E If b is any positive real number with b ? 1 and x is any real number, b?x is defined as follows: Use this definition and the definition of logarithm to prove that for all positive real numbers u and b, with b

Problem 22E Use the unique factorization for the integers theorem and the definition of logarithm to prove that log3(7) is irrational. Theorem Unique Factorization of Integers Theorem (Fundamental Theorem of Arithmetic) Given any integer n > 1, there exist a positive integer k, distinct prime numbers p1, p2, …, pk, and positive integers e1, e2, …, ek such that and any other expression for n as a product of prime numbers is identical to this except, perhaps, for the order in which the factors are written.

Problem 23E If b and y are positive real numbers such that logb y = 3, what is log1/b(y)? Why?

Problem 24E If b and y are positive real numbers such that logb y = 2, what is logb2 (y)? Why?

Problem 25E Let A = {2, 3, 5} and B = {x, y}. Let p1 and p2 be the projections of A × B onto the first and second coordinates. That is, for each pair (a, b)? A ×B, p1(a, b) = a and p2(a, b) = b. a. Find p1(2, y) and p1(5, x). What is the range of p1? ________________ b. Find p2(2, y) and p2(5, x). What is the range of p2?

Problem 26E Observe that mod and div can be defined as functions from Znonneg × Z+ to Z. For each ordered pair (n, d) consisting of a nonnegative integer n and a positive integer d, let mod(n, d) = n mod d (the nonnegative remainder obtained when n is divided by d). div(n, d) = n div d (the integer quotient obtained when n is divided by d). Find each of the following: a. mod (67, 10) and div (67, 10) ________________ b. mod (59, 8) and div (59, 8) ________________ c. mod (30, 5) and div (30, 5)

Problem 27E Let S be the set of all strings of a’s and b’s. a. Define f : S ? Z as follows: For each string s in S Find f (aba), f (bbab) and f (b). What is the range of f ? b. Define g: S ? S as follows: For each string s in S, g ( s ) = the string obtained by writing the characters of s in reverse order. Find g(aba), g(bbab), and g(b). What is the range of g?

Problem 28E Consider the coding and decoding functions E and D defined in Example 7.1.9. a. Find E(0110) and D(111111000111). b. Find E(1010) and D(000000111111).

Problem 29E Consider the Hamming distance function defined in Example 7.1.10. a. Find H(10101, 00011) b. Find H(00110, 10111).

Problem 30E Draw arrow diagrams for the Boolean functions defined by the following input/output tables.

Problem 32E Consider the three-place Boolean function f defined by the following rule: For each triple a. Find f (1, 1, 1) and f (0, 0, 1). b. Describe f using an input/output table.

Problem 31E Fill in the following table to show the values of all possible two-place Boolean functions. Input 1 1 1 0 0 1 0 0

Problem 33E Student A tries to define a function g: Q ? Z by the rule for all integers m and n with n ? 0. Student B claims that g is not well defined. Justify student B’s claim.

Problem 34E Student C tries to define a function h: Q ? Q by the rule for all integers m and n with n ? 0. Student D claims that h is not well defined. Justify student D’s claim.

Problem 35E Let J5 = {0, 1, 2, 3, 4}. Then J5 ? {0} = {1, 2, 3, 4}. Student A tries to define a function R: J5 ? {0} ? Z as follows: For each x ? J5 ? {0}, R(x) is the number y so that (xy) mod 5 = 1. Student B claims that R is not well defined. Who is right: student A or student B? Justify your answer.

Problem 36E Let J4= {0, 1, 2, 3}. Then J4 ? {0} = {1, 2, 3}. Student C tries to define a function S: J4 ? {0} ? Z as follows: For each x ? J4 ? {0}, S(x) is the number y so that (xy) mod 4 = 1. Student D claims that S is not well defined. Who is right: student C or student D? Justify your answer.

Problem 37E On certain computers the integer data type goes from ?2, 147, 483, 648 through 2, 147, 483, 647. Let S be the set of all integers from ?2, 147, 483, 648 through 2, 147, 483, 647. Try to define a function f : S ? S by the rule f (n) = n2 for each n in S. Is f well defined? Why?

Problem 40E Let X and Y be sets, let A and B be any subsets of X, and let F be a function from X to Y. Fill in the blanks in the following proof that F (A) U ? F (B) ? F (A ? B). Proof: Let y be any element in F (A) ? F (B). [We must show that y is in F(A ? B).] By definition of union, (a). Case 1, y? F(A): In this case, by definition of F(A), y = F(x) for (b)x ? A. Since A ? A ? B, it follows from the definition of union that x ? (c). Hence, y = F(x) for some x ? A ? B, and thus, by definition of F(A ? B), y ? (d). Case 2, y?F(B): In this case, by definition of F(B), (e) x ? B. Since B ? A ? B it follows from the definition of union that (f). Therefore, regardless of whether y ? F(A) or y ? F(B), we have that y ? F(A ? B) [as was to be shown].

Problem 38E Let X = {a, b, c} and Y = {r, s, t, u, v, w}. Define f: X ?Y as follows: f (a) = v, f (b) = v, and f (c) = t. a. Draw an arrow diagram for f. ________________ b. Let A = {a, b}, C = {t}, D = {u, v}, and E = {r, s}. Find f (A), f (X), f-1 (C), f-1(D), f-1 (E), and f-1 (Y).

Problem 39E Let X = {1, 2, 3, 4} and Y = {a, b, c, d, e}. Define g: X ?Y as follows: g(1) = a, g(2) = a, g(3) = a, and g(4) = d. a. Draw an arrow diagram for g. ________________ b. Let A = {2, 3}, C = {a}, and D = {b, c}. Find g(A), g(X), g-1(C), g-1(D), and g?1(Y).

Problem 41E Let X and Y be sets, let A and B be any subsets of X, and let C and D be any subsets of Y. Determine which of the properties are true for all functions F from X to Y and which are false for at least one function F from X to Y. Justify your answers. Exercise If A ? B then F(A) ? F(B).

Problem 42E Let X and Y be sets, let A and B be any subsets of X, and let C and D be any subsets of Y. Determine which of the properties are true for all functions F from X to Y and which are false for at least one function F from X to Y. Justify your answers. Exercise F(A ? B)? F(A) ? F(B)

Problem 43E Let X and Y be sets, let A and B be any subsets of X, and let C and D be any subsets of Y. Determine which of the properties are true for all functions F from X to Y and which are false for at least one function F from X to Y. Justify your answers. Exercise F(A) ? F(B)? F(A ? B)

Problem 44E Let X and Y be sets, let A and B be any subsets of X, and let C and D be any subsets of Y. Determine which of the properties are true for all functions F from X to Y and which are false for at least one function F from X to Y. Justify your answers. Exercise For all subsets A and B of X, F(A ? B)= F(A) ? F(B).

Problem 47E Let X and Y be sets, let A and B be any subsets of X, and let C and D be any subsets of Y. Determine which of the properties are true for all functions F from X to Y and which are false for at least one function F from X to Y. Justify your answers. Exercise For all subsets C and D of Y, F-1(C ? D) = F-1(C) ? F-1(D).

Problem 48E Let X and Y be sets, let A and B be any subsets of X, and let C and D be any subsets of Y. Determine which of the properties are true for all functions F from X to Y and which are false for at least one function F from X to Y. Justify your answers. Exercise For all subsets C and D of Y, F?1(C ? D) = F?1(C) ? F?1 (D).

Problem 49E F(F-1(C)) ? C

Problem 46E Let X and Y be sets, let A and B be any subsets of X, and let C and D be any subsets of Y. Determine which of the properties are true for all functions F from X to Y and which are false for at least one function F from X to Y. Justify your answers. Exercise For all subsets C and D of Y, F-1(C ? D) = F-1(C) ? F-1(D).

Problem 50E Given a set S and a subset A, the characteristic function of A, denoted ?a, is the function defined from S to Z with the property that for all u ? S, Show that each of the following holds for all subsets A and B of S and all u ? S. a. ?A?B(u)= ?A(u)• ?B(u) ________________ b. ?A?B(u)= ?A(u)+ ?B(u) ? ?A(u)• ?B(u)

Problem 52E Exercise refers to the Euler phi function, denoted ?, which is defined as follows: For each integer n ? 1, ?(n) is the number of positive integers less than or equal to n that have no common factors with n except ±1. For example, ?(10) = 4 because there are four positive integers less than or equal to 10 that have no common factors with 10 except ±1; namely, 1, 3, 7, and 9. Exercise Prove that if p is a prime number and n is an integer with n > 1, then ?(pn) = pn ? pn?1.

Problem 51E Exercise refers to the Euler phi function, denoted ?, which is defined as follows: For each integer n ? 1, ?(n) is the number of positive integers less than or equal to n that have no common factors with n except ±1. For example, ?(10)= 4 because there are four positive integers less than or equal to 10 that have no common factors with 10 except ±1; namely, 1, 3, 7, and 9. Exercise Find each of the following: a. ?(15) ________________ b.?(2) ________________ c. ?(5) ________________ d. ?(12) ________________ e. ?(11) ________________ f. ?(1)

Problem 45E Let X and Y be sets, let A and B be any subsets of X, and let C and D be any subsets of Y. Determine which of the properties are true for all functions F from X to Y and which are false for at least one function F from X to Y. Justify your answers. Exercise For all subsets C and D of Y, if C ? D, then F-1(C) ? F-1(D).