Problems involving relation compositionProve or disprove: If a relation R, defined as a subset of A x A, issymmetric, then show that R R is symmetric as well.Since R is symmetric, we know that if (a,b)R, then (b,a)R.We must prove under this assumption that if (a,b)RR, then(b,a)RR.If (a,b)RR, by the definition of function composition, wemust have an element cA such that (a,c)R and (c,b)R. But we know R is symmetric. Thus, we can deduce that (c,a)Rand (b,c)R. But, if this is the case, by the definition of functioncomposition, we must have (b,a)RR, because (b,c)R and(c,a)R. This is exactly what we needed to prove. Thus, RR issymmetric.Prove: R is transitive R R R.We must show that if (a,b)RR, then (a,b)R.First of all, if (a,b)RR, then by the definition of function composition, there exists an element c of A such that (a,c)Rand (c,b)R.But, we also know that R is transitive. Since we have (a,c)Rand (c,b)R, we can conclude that (a,b)R, which is exactly what we were trying to prove. Thus, R R R.Let A denote an arbitrary set, and let R denote a transitive relation over A, that is, R A A, and for all x, y, z A, if (x, y) R and (y, z) R then (x, z) R. Prove that the composition relation R2 = R o R is transitive.We must show the following:if (x, y) R o R and (y, z) R o R, then (x, z) R o R,in order to prove that R o R is transitive.Since we have (x, y) R o R, w| (x,w) R and (w,y) R, by definition of relation composition. Since we also have that R is transitive, it follows that (x,y) R.Since we have (y, z) R o R, v| (y,v) R and (v,z) R, by definition of relation composition. Since we also have that R is transitive, it follows that (y,z) R.Now, but definition of relation composition, since (x,y) R and (y,z) R, it follows that (x,z) R o R, which is exactly what we wanted to show.Problems involving functionsConsider a set A = {1, 2, 3}, a set B = {a, b, c}, and a set C = {x, y}. Define a relation R A B as R = {(1, a), (2, b), (2, c)}, a relation S B C as S = {(a, x), (b, y)}, and a relation T A B as T = {(1, a), (2, c), (3, b)}. Is R a function? If so, is it an injection?No, since 2 maps to two different elements in the set B.Is R–1 a function? If so, is it an injection?Yes, since each of a, b, and c in R-1 map to exactly one element. However, R-1 is not injective because both b and c map to the same element.Is S a function? Is S–1 a function?S is not a function because c does not map to any element in theset C. But, S-1 is a function since both x and y are mapped to exactly one element in the set B.Is T a function? If so, is it a surjection?T is a function. It maps each element in the set A to an uniqueelement is the set B. Since both sets are of an equal size, T is abijection (and a surjection, of course.)Is the composed relation S–1 R–1 a function? If so, is it an injection? Is it a surjection?The composition, S–1 R–1 = {(x,1),(y,2)}. Thus it is a function since each of x and y map to an element in A. Let f: C A be the function S–1 R–1. Then we have f(x)f(y)Is the composed relation T S a function? If so, is it an injection? No, since 2 is not mapped to any element in the set C.Define h: R – {2} R where h(x) = (x – 3) / (x – 2). Prove that h(x) is an injection, but not a surjection.We must show that if h(a)=h(b), then a=b.h(a) = (a-3)/(a-2)h(b) = (b-3)/(b-2)(a-3)/(a-2) = (b-3)/(b-2)((a-2)-1)/(a-2) = ((b-2) – 1)/(b-2)1 – 1/(a-2) = 1 – 1/(b-2)1/(a-2) = 1/(b-2), since a,b2, we can cross multiply.a – 2 = b – 2a = b.h is NOT a surjection because there is no value a such that h(a)= 1. To see this note that h(a) = 1 – 1/(a-2). Since 1/(a-2) can notequal 0, we find that no value of a makes h(a)=1.Let f: AB and g: BC denote two functions. If a function gf:AC is a surjection, and g is an injection, prove that f is asurjection.Since gf is a surjection, we must have that there exists anelement x in A such that g(f(x))=c, for all elements c in the setC.Furthermore, if g in an injection, we know that if g(a)=g(b),then a=b.We must now show that there exists an element y in A such thatf(y)=b for all elements b of the set B.Assume to the contrary that there is an element b such thatthere is no y where f(y)=b. But, we know that there does existan element x such that g(f(x)) = c for all elements c of the set C.Let g(b) = c’. Since g is a function from B to C, c’ must be anelement of C. But we also know that g(f(x))=c’, since gf is asurjection. Since we have assumed that there exists no elementy in the set A such that f(y) = b, we must have that b f(x).BUT, that gives us a situation were g(b) = g( f(x) ), but b f(x),which contradicts the assumption that g was injective. Thus,our assumption must have been wrong meaning that f isinjective.Let Z = {0, 1, 1, 2, 2, …} denote the set of all integers (zero, positive, and negative). Define a function g: Z Z by the following formula:integer. oddan is if ,3otherwise, integer;even an is if ,1)(mmmmmg(Thus, for example, g(0) = 1 0 = 1; g(1) = 1 + 3 = 4; etc.) Prove that the function g defines a bijection from Z to Z; that is, prove that g is an injection (one-to-one) and g is a surjection (onto).First, let’s show that the function is an injection. We must showthat if f(a) = f(b), then a = b.Assume f(a) = f(b). We have four distinct cases:Case 1: a and b are both evenCase 2: a and b are both oddCase 3: a is even and b is oddCase 4: a is odd and b is evenCase 1: f(a) = f(b) (Given) 1 – a = 1 – b (since a and b are even) a = bCase 2: f(a) = f(b) (Given) a + 3 = b + 3 (since a and b are odd) a = bCase 3: f(a) = f(b) 1 – a = b + 3 (since a is even and b is odd) a + b = -2 But, this is impossible since a and b are of differentparity. So this case would never occur.Case 4: f(a) = f(b) a + 3 = 1 – b …
View Full Document
Unlocking...