Problems involving relation composition Prove or disprove If a relation R defined as a subset of A x A is symmetric 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 R R then b a R R If a b R R by the definition of function composition we must have an element c A such that a c R and c b R But we know R is symmetric Thus we can deduce that c a R and b c R But if this is the case by the definition of function composition we must have b a R R because b c R and c a R This is exactly what we needed to prove Thus R R is symmetric Prove R is transitive R R R We must show that if a b R R then a b R First of all if a b R R then by the definition of function composition there exists an element c of A such that a c R and c b R But we also know that R is transitive Since we have a c R and 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 functions Consider 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 the set 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 unique element is the set B Since both sets are of an equal size T is a bijection 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 b 2 we can cross multiply a 2 b 2 a 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 not equal 0 we find that no value of a makes h a 1 Let f A B and g B C denote two functions If a function g f A C is a surjection and g is an injection prove that f is a surjection Since g f is a surjection we must have that there exists an element x in A such that g f x c for all elements c in the set C 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 that f y b for all elements b of the set B Assume to the contrary that there is an element b such that there is no y where f y b But we know that there does exist an 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 an element of C But we also know that g f x c since g f is a surjection Since we have assumed that there exists no element y 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 is injective 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 1 m if m is an even integer otherwise g m m 3 if m is an odd integer 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 …
View Full Document
Unlocking...