CIS 607: Mathematical Basis for ComputingSOLUTIONS OF HOMEWORK 2Homework 2 – Sets, Functions and RelationsDue Date: March 9, 2017In this homework, you will answer the following questions. Prepare a pdf file for your solutions and upload that pdf file into the blackboard system.Q1)a) Find the power set of each of these sets, where a and b are distinct elements.∙{a, b, c}→ PS({a,b,c}) = {∅, {a},{b},{c},{a,b}{a,c},{b,c},{a,b,c}}∙{∅, {∅}}→ PS({∅, {∅}}) = {∅, {∅},{{∅}},{∅,{∅}}}b)Find A3 if∙ A = {a}.→ A3 = {(a, a, a)}∙ A = {0, a}.→ A3 = {(0, 0, 0), (0, 0, a), (0, a, 0), (0, a, a), (a, 0, 0), (a, 0, a), (a, a, 0), (a, a, a)}c) Cardinalities of Cartesian products.∙How many different elements does A × B have if A has m elements and B has n elements?→ mn∙How many different elements does A × B × C have if A has m elements, B has n elements, and C has p elements?→ mnp∙How many different elements does A n have when A has m elements and n is a positive integer?→ m nQ2)a)Let A, B, and C be sets. Show that_________ _ _ _∙ A ∩ B ∩ C = A ∪ B ∪ C→Suppose that x in the left side.x ∉A ∩ B ∩ Cx ∉ A or x ∉ B or x ∉ Cx in the right side.←Suppose that x in the right side.x is not in A, or x is not in B or x is not in C.So, x is not in A ∩ B ∩ CSo, x is the left side.∙(A − B) − C ⊆ A – CSuppose that x ∈ (A − B) − C.Then x is in A−B but not in C.Since x ∈A−B, we know that x ∈ A.Since we have established that x ∈ A but x ∉C, we have proved that x ∈A − C.∙(A − C) ∩ (C − B) = ∅To show that the set given on the left-hand side is empty, it suffices to assume that x is some element in that set and derive a contradiction, thereby showing that no such x exists.So suppose that x ∈(A−C) ∩(C −B).Then x & A − C and x & C − B. The first of these statemen ts implies by definition that x ∉C, while the second implies that x ∈ C.This is impossible, so our proof by contradiction is complete.∙(B − A) ∪(C − A) = (B ∪C) − A.To establish the equality, we need to prove inclusion in both directions.To prove that (B − A)∪(C −A) ⊆(B ∪C) − A, suppose that x ∈(B − A) ∪(C − A).Then either x ∈(B − A) or x ∈(C − A).Without loss of generality, assume the former (the proof in the latter case is exactly parallel.) Then x ∈ B and x ∉A.From the first of these assertions, it follows that x ∈ (B ∪ C).Thus we can conclude that x ∈ (B ∪C) − A, as desired.For the converse, that is, to show that (B ∪C) − A ⊆(B − A) ∪(C − A),So, suppose that x ∈ (B ∪C) − A.This means that x ∈ (B ∪C) and x ∉ A.The first of these assertions tells us that either x ∈ B or x ∈ C.Thus either x ∈B − A or x ∈C − A. In either case, x ∈(B − A) ∪(C − A).b) What can you say about the sets A and B if we know that∙ A ∪ B = A?→ B ⊆ A∙ A ∩ B = A?→ A ⊆ B∙ A − B = A?→ A ∩ B = {}∙ A − B = B − A?→ A = Bc) Find ⋃A i ∞i=1 and ⋂A i ∞i=1if for every positive integer i,∙ A i = {i, i + 1, i + 2, . . .}. →⋃A i ∞i=1 = Z + (the set of positive integers) ⋂A i ∞i=1= ∅∙ A i = {0, i}.→⋃A i ∞i=1 = N (the set of natural numbers) ⋂A i ∞i=1= {0}∙ A i = (0, i), that is, the set of real numbers x with 0 < x < i.→ ⋃A i ∞i=1 = R + (the set of positive real numbers)⋂A i ∞i=1= (0, 1) (the interval of all real numbers between 0 and 1, exclusive)∙ A i = (i,∞), that is, the set of real numbers x with x > i.→ ⋃A i ∞i=1 = (1,∞) (all real numbers greater than 1).) ⋂A i ∞i=1= ∅a)Determine whether each of these functions from Z to Z is one-to-one and/or onto.∙ f (n) = n − 1This is one-to-one. This is onto.∙ f (n) = n2 + 1This is NOT one-to-one. This is NOT onto.∙ f (n) = n3This is one-to-one. This is NOT onto.∙ f (n) = ⌈n/2⌉This is NOT one-to-one. This is onto.b) Give an example of a function from N to N that is∙one-to-one but not onto.f(n) = n + 5∙onto but not one-to-one.f (n) = ⌈n/2⌉∙both onto and one-to-one (but different from the identity function).We let f(n) = n − 1 for even values of n, and f(n) = n + 1 for odd values of n.Thus we have f(1) = 2, f(2) = 1, f(3) = 4, f(4) = 3, and so on. Note that this is just one function, even though its definition used two formulae, depending on the the parity of n.∙neither one-to-one nor onto.f(n) = 5c) Determine whether each of these functions is a bijection from R to R.∙ f (x) = −3x + 4This is a bijection since the inverse function is f−1(x) = (4 − x)/3.∙ f (x) = −3x2 + 7This is NOT a bijection since it is not one-to-one ( f(1) = f(−1) ).∙ f (x) = (x + 1)/(x + 2)This is NOT a bijection since -2 is not in its domain.∙ f (x) = x5 + 1This is a bijection since the inverse function is f−1(x) =a)Let S = {−1, 0, 2, 4, 7}. Find f_image (S) if∙ f (x) = 1.f_image (S) = {1}∙ f (x) = 2x + 1.f_image (S) = {−1, 1, 5, 8, 15}∙ f (x) = ⌈x /5⌉.f_image (S) = {0, 1, 2}∙ f (x)=⌊(x2 + 1)/3⌋.f_image (S) = {0, 1, 5, 16}b) Find f ◦ g and g ◦ f , where f (x) = x2 + 1 and g(x) = x + 2, are functions from R to R.c) Let f (x) = ax + b and g(x) = cx + d, where a, b, c, and d are constants. Determine necessary and sufficient conditions on the constants a, b, c, and d so that f ◦ g = g ◦ f .d) Show that the function f (x) = ax + b from R to R is invertible, where a and b are constants, with a ≠ 0, and find the inverse of f .∙This function is a bijection when a≠0.o when f(y)=ay+b and f(z)=az+b → f(y)=f(z) ; ay+b=az+b → y=z f is one-to-oneo f is also onto since y=(x-b)/a for all y in R.∙f−1(x) = (x-b)/aa) Find the solution to each of these recurrence relations with the given initial conditions. Use an iterative approach.∙a n= −a n−1, a0 = 5∙a n = a n−1− n, a0 = 4a∙a n = 2a n−1− 3, a0= −1∙a n = 2na n−1, a0 = 3b)A person deposits $1000 in an account that yields 9% interest compounded annually.∙Set up a recurrence relation for the amount in the account at the end of n years.∙Find an explicit formula for the amount in the account at the end of n years.∙How much money will the account contain after 100 years?c) An employee joined a company in 2009 with a starting salary of $50,000. Every year this employee receives a raise of $1000 plus 5% of the salary of the previous year.∙Set up a recurrence relation for the salary of this employee n years after 2009.∙What will the salary of this employee be in 2017?∙Find an explicit formula for the salary of this employee n years after 2009.a)Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.∙integers not divisible by 3∙the real numbers with decimal representations consisting of all 1s∙the real numbers with decimal representations of all 1s or 9s∙This set is countable but a little tricky. We can arrange the numbers in a 2-dimensional table as follows:Thus we have shown that our set is the countable union of countable sets (each of the countable sets is one row of this table). Therefore, the entire set is countable. For an explicit correspondence with the positive integers, we can zigzag along the positive-sloping diagonals 1 ⟷ .1, 2 ⟷ 1.1,3 ⟷ .1,4 ⟷ .11,5 ⟷ 1, and so on.∙This set is not countable. We can prove it by the same diagonalization argument as was used to prove that the set of all reals is uncountable. All we need to do is choose d i = 1 when d ii = 9 andchoose d i = 9 when d ii = 1 or d ii is blank (if the decimal expansion is finite).b) Give an example of two uncountable sets A and B such that A − B is∙finite.∙countably infinite.∙uncountable.a) Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric, and/or transitive, where (x, y) ∈ R if and only if∙x + y = 0.∙x = ±y.∙x = 2y.∙xy ≥ 0.b) For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive.∙{(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}not reflexive ; not symmetric ; not antisymmetric ; transitive∙{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}reflexive ; symmetric ; not antisymmetric ; transitive∙{(2, 4), (4, 2)}not reflexive ; symmetric ; not antisymmetric ; not transitive∙{(1, 2), (2, 3), (3, 4)}not reflexive ; not symmetric ; antisymmetric ; not transitivec) Write all binary relations on the set A={a,b}. Determine which ones are reflexive, symmetric, antisymmetric, transitive and/or functions from A to A.{} not reflexive ; symmetric ; antisymmetric ; transitive ; not function{(a,a)} not reflexive ; symmetric ; antisymmetric ; transitive ; not function{(a,b)} not reflexive ; not symmetric ; antisymmetric ; transitive ; not function{(b,a)} not reflexive ; not symmetric ; antisymmetric ; transitive ; not function{(b,b)} not reflexive ; symmetric ; antisymmetric ; transitive ; not function{(a,a),(a,b)} not reflexive ; not symmetric ; antisymmetric ; transitive ; not function{(a,a),(b,a)} not reflexive ; not symmetric ; antisymmetric ; transitive ; function{(a,a),(b,b)} reflexive ; symmetric ; antisymmetric ; transitive ; function{(a,b),(b,a)} not reflexive ; symmetric ; antisymmetric ; not transitive ; function{(a,b),(b,b)} not reflexive ; not symmetric ; antisymmetric ; transitive ; function{(b,a),(b,b)} not reflexive ; not symmetric ; antisymmetric ; transitive ; not function{(a,a),(a,b),(b,a)} not reflexive ; symmetric ; not antisymmetric ; not transitive ; not function {(a,a),(a,b),(b,b)} reflexive ; not symmetric ; antisymmetric ; transitive ; not function{(a,a),(b,a),(b,b)} reflexive ; not symmetric ; antisymmetric ; transitive ; not function{(a,b),(b,a),(b,b)} not reflexive ; symmetric ; antisymmetric ; not transitive ; not function{(a,a),(a,b),(b,a),(b,b)} reflexive ; symmetric ; not antisymmetric ; transitive ; not functiona) Suppose that R and S are reflexive relations on a set A. Prove or disprove each of these statements.∙R ∪ S is reflexive.∙R ∩ S is reflexive.∙S ◦ R is reflexive.b) Show the following properties on relations∙Show that the relation R on a set A is symmetric if and only if R = R−1, where R−1 is the inverse relation.Let (x,y) ∊ R(y,x) ∊ R since R is symmetric(x,y) and (y,x) ∊ R−1 by definition of inverse relationSo, R=R−1∙Show that the relation R on a set A is antisymmetric if and only if R ∩ R−1 is a subset of the diagonal relation Δ = {(a, a) | a ∈ A}.∙Show that the relation R on a set A is reflexive if and only if the inverse relation R−1 is reflexive.R is reflexive iff ∀x[x∊U ⟶ (x,x) ∊ R]iff ∀x[x∊U ⟶ (x,x) ∊ R-1] by definition of inverse relationR-1 is reflexivea)Which of these relations on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack.∙{(a, b) | a and b are the same age}equivalence relation∙{(a, b) | a and b have the same parents}equivalence relation∙{(a, b) | a and b share a common parent}This is not an equivalence relation, since it need not be transitive. (We assume that biologicalparentage is at issue here, so it is possible for A to be the child of W and X, B to be the child of X and Y, and C to be the child of Y and Z . Then A is related to B, and B is related to C, but A isnot related to C.)∙{(a, b) | a and b speak a common language}This is not an equivalence relation, since it need not be transitive.b)∙Show that the relation R consisting of all pairs (x, y) such that x and y are bit strings of length three or more that agree in their first three bits is an equivalence relation on the set of all bitstrings of length three or more.Transitive equivalence relation∙Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) ∈ R if and only if ad = bc. Show that R is an equivalence relation.Q10)a) Which of these relations on {0, 1, 2, 3} are partial orderings? Determine the properties of a partial ordering that the others lack.∙{(0, 0), (2, 2), (3, 3)}∙{(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 3)}∙{(0, 0), (1, 1), (1, 2), (2, 2), (3, 1), (3, 3)}∙{(0, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 2), (2, 3), (3, 0), (3, 3)}b)Let (S,R) be a poset. Show that (S,R−1) is also a poset, where R−1 is the inverse of R. The poset (S R−1) is called the dual of (S,R).。
