04-S Functions - Dr. Vaidy PDF

Preview

Summary

Dr. Vaidy...

Description

EE 4740 (Spring 2016)—Solution to Problems on Functions EE 4740 (Spring 2016)

page 1 of 11

Solution to Problems on Functions

“Anyone who has never made a mistake has never tried anything new.” —Albert Einstein

1. (Section 2.3, Exercise 2, page 152) (a) Since f(n) = n or −n, the mapping is not well-defined; i.e., there is no “single” element to which f can claim to map n. So f is not a function.

(b) For each n ∈ Z, the quantity n2 +1 and its positive square root,

√ n2 + 1 are well-defined,

and represent a single element. So f is a function.

(c) If n = ±2, the n2 − 4 = 0 and so f(n) is not defined. Therefore, f is not a function

as defined in class. However, there is a class of functions called partial functions that do not necessarily map all points of the domain. However, any point that is mapped, is mapped to a single element of the codomain (see also the note before problem 39, page 71 of the text).

2. (Section 2.3, Exercise 4, page 152) (a) The domain is the set of non-negative integers, N = {0, 1, 2, · · ·} and the range is the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} of decimal digits.

(b) The domain is the set Z+ = {1, 2, 3, · · ·} of positive integers and the range is Z+ − {1} = {2, 3, 4, · · ·}.

(c) To keep the solution simple here, let us assume that each binary string contains at least one bit. For any integer i ≥ 1, let {0, 1}i denote {0, 1} × {0, 1} × · · · × {0, 1} . For | {z } i times example, {0, 1}2 = {0, 1} × {0, 1} and{0, 1}3 = {0, 1} × {0, 1} × {0, 1}. Thus, {0, 1}i is

the set of all binary string with exactly i bits.

The domain consisting of the set of all binary strings is

[ i∈

have 0 or more ones in it, the range is N = {0, 1, 2, · · ·}.

{0, 1}i . Since a string can

Sometimes, it is necessary to consider a string with no bits in it; this string is called the empty string. If the empty string is included,then i can be 0 as well in the expression for the domain. The range is still the same, however. (d) The domain is the same as in part 2c. The range is N, if the domain includes the empty string; otherwise the range is Z.

EE 4740 (Spring 2016)—Solution to Problems on Functions

page 2 of 11

3. (Section 2.3, Exercise 12, page 153) (a) f(n) = f (m) ⇐⇒ n − 1 = m − 1 ⇐⇒ n = m, so f is injective. For any m ∈ Z, f(n) = n − 1 = m =⇒ n = m + 1 ∈ Z. That is, for any m ∈ Z, there is an element n ∈ Z such that n = m + 1 and f(n) = m. Thus, every point m in the codomain is mapped on and so the function is surjective.

(b) f(n) = f (m) ⇐⇒ n2 + 1 = m2 + 1 ⇐⇒ n2 = m2 ⇐⇒ n = ±m 6=⇒ n = m. The function is not injective as it maps n and −n to the same point. √ For any m ∈ Z, f(n) = n2 + 1 = m =⇒ n = ± m − 1 6∈ Z. For instance, if m = 3, √ then n would have to be 2 which is not in Z. So f is not surjective.

(c) f(n) = f (m) ⇐⇒ n3 = m3 ⇐⇒ n = m, so f is an injection. 1

For any m ∈ Z, f(n) = n3 = m =⇒ n = m 3 6∈ Z. So f is not a surjection.

(d) f(n) = f (m) ⇐⇒ ⌈ 2n ⌉ = ⌈ m2 ⌉ 6=⇒ n = m. For instance if n = 2k − 1 and m = 2k, then f(n) = f(m) = k. However, n 6= m, so f is not an injection.

⌉ = m; since 2m ∈ Z, the function is surjective. For any m ∈ Z, f(2m) = ⌈ 2m 2

4. (Section 2.3, Exercise 22, page 153) A function is a bijection iff it is both an injection and a surjection. (a) For real number(s) x, y, f(x) = f (y) ⇐⇒ −3x + 4 = −3y + 4 ⇐⇒ −3x = −3y ⇐⇒ x = y. Therefore f is an injection.

For any real number x, if there is a y such that f(y) = x, then x = −3y + 4; that is, y=

4−x , 3

which is a real number. Therefore, ∀x ∈ R, ∃y =

surjection and hence a bijection.

4−x 3

∈ R, f (y) = x, so f is a

(b) For any x, y ∈ R, f(x) = f (y) ⇐⇒ −3x2 +7 = −3y2 +7 ⇐⇒ x2 = y2 ⇐⇒ x = ±y ∈ R. There are two different values, x and −x, such that f(x) = f (−x), so f is not an injection. q , which is imaginary, if x < 7. So For any If f(y) = x = −3y2 + 7, then y = ± x−7 3 x < 7, there is no point y with f(y) = x and therefore, f is not a surjection.

(c) In this case the “function” is not defined for the point −2. So we will assume its domain to be R − {2}.

For any x, y ∈ R, f(x) = f (y) ⇐⇒ is an injection.

x+1 x+2

=

y+1 y+2

1 =1− ⇐⇒ 1 − x−2

1 y−2

⇐⇒ x = y, so f

EE 4740 (Spring 2016)—Solution to Problems on Functions If f(y) = x = 1 −

1 , y−2

then y = 2 +

1 , 1−x

page 3 of 11

which is not defined forx = 1. Therefore, no

point in the domain is mapped to 1 and the function is not a surjection. However, if the function is defined from R − {2} to R − {1},then it would be a bijection. 1

(d) For any x, y ∈ R, f(x) = f (y) ⇐⇒ x5 + 1 = y5 + 1 ⇐⇒ x5 = y5 ⇐⇒ x = (y5 ) 5 = y (there is only one real 5th root of a real number). Therefore, f is an injection. 1

If f(y) = x = y5 + 1, then y = (x − 1) 5 . As observed above, there is areal 5th root of a

real number. Therefore, f is a surjection and hence, a bijection.

5. (Section 2.3, Exercise 30, page 154) For all parts the answer is simply {f(−1), f (0), f (2), f (4), f (7)}. (a) f(S) = {1, 1, 1, 1, 1} = {1}. (b) f(S) = {−1, 1, 5, 9, 15}. (c) f(S) = {0, 0, 1, 1, 2} = {0, 1, 2}. (d) {0, 0, 1, 5, 16} = {0, 1, 5, 16}.

6. (Section 2.3, Exercise 32, page 154) (a) The set {2x : x ∈ Z} of all even integers. (b) The set {2x : x ∈ N} of all even non-negative integers. (c) The set {2x : x ∈ R} = R of all reals.

7. We need to prove that function composition is associative. That is, for any functions f : A −→ B, g : B −→ C and h : C −→ D,

(h ◦ g) ◦ f = h ◦ (g ◦ f).

Consider functions f : A −→ B, g : B −→ C and h : C −→ D.For any a ∈ A, let f(a) = b ∈ B

and let g(b) = c ∈ C and let h(c) = d ∈ D.Clearly given a, the elements b, c and d are completely defined by functions f, g and h.

Therefore (g ◦ f)(a) = g (f(a)) = g (b) = c and hence (h ◦ (g ◦ f ))(a) = h((g ◦ f )(a)) = h(c) =

d.Also ((h ◦ g) ◦ f)(a) = (h ◦ g)(f(a)) = (h ◦ g)(b) = h(g(b)) = h(c) = d = (h ◦ (g ◦ f))(a).

EE 4740 (Spring 2016)—Solution to Problems on Functions

page 4 of 11

8. (Section 2.3, Exercise 34, page 154) Let g : A −→ B and f : B −→ C be functions. Intuitively (or with the aid of a small example), you should have been able to guess that if f and f ◦ g are both injective, then g must be injective. We prove this by contradiction. Suppose g is not injective. Therefore there

are distinct elements a1 , a2 ∈ A such that g(a1 ) = g (a2 ). Therefore(f ◦ g )(a1 ) = f (g (a1 )) = f(g(a2 )) = (f ◦ g)(a2 ) and so f ◦ g cannot be injective. This is the necessary contradiction.

Observe that we have essentially proved that if f ◦g is injective,then g will have to be injective (regardless of whether or not f is injective).Could f be non-injective here ?

9. (Section 2.3, Exercise 38, page 154) (f ◦ g )(x) = f (g(x)) = f (cx + d) = a(cx + d) + b = acx + (ad + b), and (g ◦ f )(x) = g (f (x)) =

g(ax + b) = c(ax + b) + d = acx + (cb + d).If f ◦ g = g ◦ f, then ad + b = cb + d; that is, a−1 b

=

c−1 . d

10. (Section 2.3, Exercise 42, page 154) (a) f −1 ({1}) = {r ∈ R : r 2 = 1} = {−1, 1}, as the solution to r 2 = 1 is ±1. (b) f −1 ({x 2

:

0 < x < 1}) = {r ∈ R

:

r 2 ∈ {x

:

0 < x < 1}}. Observe that

r ∈ {x : 0 < x < 1} iff 0 < r < 1 or 0 > r > −1. Therefore f −1 ({x : 0 < x < 1}) = {r ∈ R : 0 < r < 1 or − 1 < r < 0}.

(c) f −1 ({x : x > 4}) = {r ∈ R : r 2 ∈ {x : x > 4}}. Observe that r 2 ∈ {x : x > 4} iffr > 2 or r < −2. Therefore f −1 ({x : x > 4}) = {r ∈ R : r > 2 or r < −2}.

11. (Section 2.3, Exercise 44, page 154) (a) For any x ∈ A, x ∈ f −1 (S ∪ T ) ⇐⇒ f(x) ∈ S ∪ T

[definition of f −1 ]

⇐⇒ f(x) ∈ S or f(x) ∈ T

⇐⇒ x ∈ f

−1

(S) or x ∈ f

−1

⇐⇒ x ∈ f −1 (S) ∪ f −1 (T ) Therefore f −1 (S ∪ T ) = f −1 (S) ∪ f −1 (T ).

[definition of ∪]

(T ) [definition of f −1 ] [definition of ∪]

EE 4740 (Spring 2016)—Solution to Problems on Functions

page 5 of 11

(b) For any x ∈ A, x ∈ f −1 (S ∩ T ) ⇐⇒ f(x) ∈ S ∩ T

[definition of f −1 ]

⇐⇒ f(x) ∈ S ∧ f(x) ∈ T ⇐⇒ x ∈ f

−1

(S) ∧ x ∈ f

−1

[definition of ∩]

(T ) [definition of f −1 ]

⇐⇒ x ∈ f −1 (S) ∩ f −1 (T )

[definition of ∩]

Therefore f −1 (S ∩ T ) = f −1 (S) ∩ f −1 (T ).

12. (Section 2.3, Exercise 52, page 154) Only the answer to part (a) is provided; part (b) is a dual of part (a) and its answer is similar. The “if” part is easy; x < n =⇒ ⌊x⌋ ≤ x < n. Let x ≥ n. If x = n, then x is an integer

and ⌊x⌋ = x = n. On the other hand if x > n, then ⌊x⌋ ≥ n as well, as⌊x⌋ is the largest

integer that is ≤ x. In short, if x ≥ n, then ⌊x⌋ ≥ n. This suffices for an indirect proof for ⌊x⌋ < n =⇒ x < n.

13. (Section 2.3, Exercise 66, page 155) We consider some cases. • If x is an even integer: • If x is an odd integer:

Here f(x) =

3x 2

.

Here f(x) = x +

• If x is not an integer and ⌈x⌉ is even:

x−1 2

=

3x−1 . 2

For integer k, let x lie between consecutive

integers i − 1 = 2k − 1 and i = 2k; that is, i − 1 = 2k − 1 < x < 2k = i. Clearly ⌈x⌉ = 2k is even, as presumed.Since

f(x) = 2k +

2k−2 2

=

6k−2 2

=

2k−1 2

3i−2 . 2

• If x is not an integer and ⌈x⌉ is odd:

<

x 2

< k, we have ⌊x⌋ =

2k−2 . 2

Therefore,

For integer k, let x lie between consecutive

integers i − 1 = 2k and i = 2k + 1; that is, i − 1 = 2k < x < 2k + 1 = i. Clearly 2k < x2 2 3(2k+1)−1 = 3i−1 . 2 2

⌈x⌉ = 2k + 1 is odd, as presumed. Since

f(x) = 2k + 1 +

2k 2

6k+2 2

=

=

<

2k+1 , 2

we have ⌊x⌋ =

2k .Therefore, 2

Observe that the second and fourth cases can be written as a single case where i − 1 < x ≤ i

and i is odd. Here f(x) = In summary, f(x) =

3i−1 2

      

.

3i−1 , 2 3i−2 2 3x 2

if i − 1 < x ≤ i and i is an odd integer

if i − 1 < x < i and i is an even integer

if x is an even integer

EE 4740 (Spring 2016)—Solution to Problems on Functions

page 6 of 11

The graph for the function is shown below.

4

3

2

1 −3

−2

−1 1

2

3

−1 x −2

y

denotes the interval (x,y]

−3

−4

14. (Section 2.3, Exercise 70, page 155) Let h : A −→ B be any function. It is easy to prove that ιB ◦ h = h = h ◦ ιA ; try to prove it.

We will use this observation below. Let f : Y −→ Z and g : X −→ Y be invertible functions

(bijections).To prove that (f ◦g)−1 = g −1 ◦f −1 , we only need show that (f ◦g)◦(g −1 ◦f −1 ) = ιZ and (g −1 ◦ f −1 ) ◦ (f ◦ g) = ιX .

From the definition of inverse and the associative property of function composition (see Problem 7) we have, (f ◦ g) ◦ (g −1 ◦ f −1 ) = f ◦ (g ◦ g −1 ) ◦ f −1 = f ◦ ιY ◦ f −1 = f ◦ f −1 = ιZ and (g −1 ◦ f −1 ) ◦ (f ◦ g) = g −1 ◦ (f −1 ◦ f) ◦ g = g −1 ◦ ιY ◦ g = g −1 ◦ g = ιX

EE 4740 (Spring 2016)—Solution to Problems on Functions

page 7 of 11

15. (Section 2.3, Exercise 78, page 152) (a) We only need to show that f ∗ is well-defined. For any a ∈ A,if f(a) is (well)-defined, then so is f ∗ (a) = f (a). If f (a) is not defined, then we map a to an element u, so f ∗ (a) is well-defined. (b) We only need identify elements in the domain for which the function is not defined, and map these elements to an element u that is not in the codomain of the function in question. • f : Z −→ R, f(n) = n1 . This is undefined only at n = 0, so f ∗ (x) =

(

1 , n

if x 6= 0

if x = 0

u

• f : Z −→ Z, f(n) = ⌈ n2 ⌉. This is already a total function, so f ∗ = f. • f : Z × Z −→ Q, f(m, n) =

m . n

This is not defined when n = 0. Therefore,

f ∗ (m, n) =

(

m , n

u

if n 6= 0

if n = 0

• f : Z × Z −→ Z, f(m, n) = mn. This is already a total function, so f ∗ = f . • f : Z × Z −→ Z, f(m, n) = m − n, if m > n. This is not defined when m ≤ n. So ∗

f (m, n) =

(

m − n, if m > n u

if m ≤ n

16. Let A = {a0 , a1 , · · · , an−1 } and B = {b0 , b1 , · · · , bm−1 }. (a) A function f : A −→ B can map an element ai ∈ A to any element of B; that is, there are m choices for f(ai ), independent of the choices for other elements of A. Therefore, the total number of choices for the function f : A −→ B is n m | ×m× {z· · · × m} = m n times

The set {f | f : A −→ B} is often denoted by B A . This problem establishes that

|B A | = |B ||A| , for finite sets A and B .

EE 4740 (Spring 2016)—Solution to Problems on Functions

page 8 of 11

(b) For f : A −→ B to be an injection n = |A| ≤ |B| = m. Suppose this is the case. Element a0 can be mapped by f to any element of B; that is, f(a0 ) has m possibilities.

Given that a0 has been mapped to some element of B, element a1 now has only m − 1 possibilities (as f(a1 ) 6= f (a0 ), if f is an injection). Similarly f (a2 ) has m−2 possibilities

and, in general, for 0 ≤ i < n, f(ai ) has m − i possibilities. Therefore the total number of possibilities for f is n Y

i=0

m − i = m(m − 1)(m − 2) · · · (m − (n − 2))(m − (n − 1))(m − n) =

m(m−1)(m−2)···(m−(n−2))(m−(n−1))(m−n)(m−(n+1))(m−(n+2))···3·2·1 (m−(n+1))(m−(n+2))···3·2·1

=

m! (m − n)!

Therefore, the number of injections from A to B is

   0,  

if |A| > |B |

(|B |)! , (|B |−|A|)!

if |A| ≤ |B |

(c) When A and B are finite sets, function f : A −→ B is a bijection iff it is an injection.

That is, we can consider bijection f : A −→ B to be a special case of an injection where

n = |A| = |B| = m. With is observation and the previous part we have, the number of bijections from A to B is

   0,

if |A| 6= |B |

  (|A|)!, if |A| = |B |

Note that the above results depend only on the cardinalities of Aand B, rather than their actual contents. Therefore, the number of bijectionsf : A −→ B with |A| = |B| is the same as the number of bijections of the form f : A −→ A. A bijection f : A −→ A is simply a rearrangement of the elements of A. That is, if A is viewed as an ordered sequence of ele-

ments (a0 , a1 , · · · , an−1 ), then f simple rearranges the elements as(f(a0 ), f (a1 ), · · · , f (an−1 )).

Therefore, a bijection f : A −→ A is also called a permutation of A. It is well known that

n elements can be permuted in n! ways. Therefore it is not surprising that there are(|A|)!

bijections from A to B, when |A| = |B |.   m Also note that for m ≥ n ≥ 0, = n

m! is n!(m−n)!

the number of ways in which n elements   n-element subsets of an can be selected out of a set ofm elements. That is, there are mn

m-element set. An injection f : A −→ B can be viewed as a bijection from A to f(A), the   such ranges and for each range of f; the range of f has |A| = n elements.We can choose m n one of them we can obtainn! bijections. So it is not surprising that when m ≥ n, the number

EE 4740 (Spring 2016)—Solution to Problems on Functions of injections f : A −→ B is n!

  m n

=

page 9 of 11

m! . (m−n)!

17. Let f : A −→ B. (a) No left or right inverse: left inverse,

f −1 ℓ ,then

Define f : {0, 1} −→ {a, b} as f(0) = f (1) = a. If f has a

−1 −1 −1 f −1 ℓ (f(0)) = fℓ (a) = 0 and fℓ (f(1)) = f ℓ (a) = 1. That

is 0 = f −1 (a) = 1, which is clearly not possible for a function.Suppose this function has a right inverse, then f(f −1 r (b)) = b. This is not possible as, regardless of where f r−1 maps b, the function f can never map it back to b (as b 6∈ f(A) = range of f ).

Intuitively, since f is not injective, two points in the domain are mapped to the same

point in the codomain, so the distinction between then is lost in the transformation. Therefore it is not possible to get back (with a left inverse) to the starting point in the domain of f. Since f is not surjective, there is a point, p, in the codomain that is not mapped on to. If the right inverse starts from this point p, then f can never take it back to p. So f cannot have a right inverse. No left inverse, but multiple right inverses:

Define g : {0, 1} −→ {a} with f(0) =

f(1) = a. As in the case of function f above, g cannot have a left inverse. Consider

functionsh1 , h2 : {a} −→ {0, 1} with h1 (a) = 0 and h2 (a) = 1. Clearly,f(h1 (a)) =

f(h2 (a)) = a. Therefore, both h1 and h2 qualify to be right inverses of f. Intuitively, g is not injective and so, as with function f above, it has no left inverse. For a function h to be a right inverse of f, it must map points in such a way that f

can return this mapping to the starting point of h. Suppose f maps several points p1 , p2 , · · · , pi in its domain to the same point q in its codomain, then h could map

q to any of the pointsp1 , p2 , · · · , pi and still ensure that f returns it to the starting point q. This situation offers i possibilities for the right inverse of f .

No right inverse, but multiple left inverses:

Notice that the functions h1 and h2 above

have no right inverses but g is a left inverse for both of them. Consider now the function k : {a, b} −→ {0, 1, 2} withk (a) = 0,

k(b) = 1 and

functions m1 , m2 : {0, 1, 2} −→ {a, b} such thatm1 (0) = m2 (0) = a, m1 (1) =

m2 (1) = b, m1 (2) = a and m2 (2) = b. Verify thatm1 (k(a)) = m2 (k (a)) = a and

m1 (k(b)) = m2 (k(b)) = b. Therefore both m1 and m2 qualify to be left inverses of k. As in the first case, k has no right inverse as it is not surjective.Suppose no point in the domain of k is mapped to point p in the codomain.Then a left inverse of k could map p to any point in the domain of k.If the domain has i elements, then this situation offers i possibilities for the left inverse of i.

EE 4740 (Spring 2016)—Solution to Problems on Functions

page 10 of 11

Single left/right inverse: Define n : {0} −→ {a} with n(0) = a. Clearly, n−1 : {a} −→ {0} with n−1 (a) = 0 is the inverse of n.

(b) Suppose function f : A −→ B has both a left inverse f ℓ−1 and a right inverse f r−1 . Then f ℓ−1 ◦ f = ιA and f ◦ fr−1 = ιB . Recall that function composition ◦is associative and that

for any function g : X −→ Y , ιY ◦ g = g ◦ ιA = g. Therefore,

fℓ−1 = f ℓ...