Problem Set 12
8 points
The problems are taken from the text. Keep in mind starred problems
have solutions in the back!
Required to do, but not to turn in:
Chapter 4.1
2 (all), 5(a), 6(c-d), 9(all)
Chapter 4.2
1(f, g), 3b, 14(a)
Chapter 4.3
1(c,d,e,f,g), 4 (all)
Chapter 4.4
1(a), 2, 10(c)
Chapter 4.5
q(a,b), 2(a,c), 5(a,b), 6(all), 10(a,c, d), 11(b)
To be turned in:
(Select Solutions)
Chapter 4.1
5(b), 8(b), 11(c), 12, 19(a,c)
Chapter 4.2
4(all), 5(d), 13
13. Remember the definition of h u g. You simply take the order pairs of points in the function h and the function g. So since
h = {(a,b): a is in A and b is in B}
g = {(c,d): c is in C and d is in D}
so that
h u g := {(x,y): (x is in A and y is in B) or (x is in C and d is in D)}
Let's define f = h u g to be the relation given by this set. We are asked to show that f is a function.
Now, let E be the intersection of A and C, and suppose that h|E = g|E. Then the definition on page 186 tells us that f = h u g
is a function if it satisfies two conditions. The domain in this case
is A u C. The issue is whether property (ii) is satisfied. In this
case, if (x,y) is in f, then if x is in A-C, we have y=h(x). Since x is not in C, there is no value g(x). Since h is a function, it satisfies (ii) so (x,y) and (x,z) in f implies y=z.
Now suppose x is in E, the intersection of A and C. Suppose also that (x,y) is in f and (x,z) is in f. Then since h is a function, y = h|E(x). But h|E(x)= g|E(x)=z, since g is a function. Therefore, we have we have y=z.
If on the other hand, f:= h u g is a fuction, we have the property that (x,y) in f and (y,z) in f implies y=z. We prove that h|E = g|E by contradiction. Suppose x is in E (the intersection of A and C) and suppose h|E(x) != g|E(x) (where != means "not equal"). Then let y = h|E(x) and z = g|E(x). Then (x,y) is in f and (x,z) is in f, but y is not equal to z. This contrdicts the assumption that f is a function.
Chapter 4.3
3(b,d), 5, 6
3(b) The canonical map is the map that takes each element k of Z to the same element mod 5. So for example, 6 goes to [1] (because 6=1(mod 5)). This map is definitely ONTO because we can find an element that maps to each of the elements in Z5, mainly 0,1,2,3,4 map to [0], [1], [2], [3], and [4]. The map is not 1-1 because many elements map to the same element in Z5. For example, both 0 and 5 map to [0]. (Keep in mind to show that something is not 1-1, you need only find two elements of the domain that have the same image under the function.)
Chapter 4.4
1(d), 9(b), 10(a, b)
1(d) Suppose G(m,n)=G(m',n'). We need to show that (m,n)=(m'n'). Since G(m,n)= 2m+2(2n-1), we have 2m+2(2n-1)=2m'+2(2n'-1). Suppose that m is not equal to m'. Without loss of generality, assume m'>m. Then divide both sides by 2m+2. We obtain 2n-1=2(m'-m)(2n-1). Since m'>m, the right hand side is an even number. However, the left hand side is an odd number. This is a contradiction, so m=m'. We can then cancel the term 2m+2and obtain 2n-1=2n'-1. This easily simplifies to n=n'. Therefore the pair (m,n)=(m',n') showing that G is injective.
Chapter 4.5
4(a,d,e), 8(b), 13, 18(b)
13. We assume that X is a subset
of A and that f is one-to one. We want to show two sets are equal, so
we show that one is included in the other, and vice versa. Let y be an element of f(A-X). Then there exists an element x in A-X such that f(x)=y. In particular, x is in A, so that y is in f(A). You might be tempted now to say that x is not in X, so y is not in f(X). However, you need to be sure that there is no other element x' that is in X with f(x')=y, otherwise y would be in f(X). Since f is one-to-one, x is the only element of A such that y=f(x). Therefore, y is not in the image f(X). Therefore y is in f(A)-f(X).
Now suppose that y is in f(A)-f(X). Then y in f(A) implies there exists an element x in A such that f(x)=y. Furthermore, since y is in f(A)-f(X), there is no element x' in X such that y=f(x'). Therefore, x is not in X, so that x in A-X. Therefore y in f(A-X).