Math 74 Homework 10Due Monday, November 3rdNovember 1, 20081. Let X be a set, and suppose that X is not finite. Using an inductivedefinition, show that there is an injective function f : N → X.2. (The construction of Q from Z)(a) Let ∼ be the relation on Z × (Z \ {0}) given by (a, b) ∼ (c, d) iffad = bc. Show that ∼ is an equivalence relation.(b) Let Q := Z × (Z \ {0})/∼. We’ll write [a, b] for [(a, b)] in Q tomake notation less confusing. Define operations +, −, · on Q by[a, b] + [c, d] := [ad + bc, bd][a, b] − [c, d] := [ad − bc, bd][a, b] · [c, d] := [ac, bd],and define division on Q by [a, b]/[c, d] := [ad, bc] for c 6= 0. Showthat these operations are well-defined.(c) Show that there is a well-defined function f : Q → Q defined byf([a, b]) =ab, and that this function is a bijection. Show moreoverthat f preserves the operations defined in (b).3. (Equivalence Relations and Partitions are in Bijective Correspondence)(a) Let X be a set, and let P ⊆ P (X) be a partition of X. Definea relation RPon X by aRPb iff there exists an A ∈ P such thata ∈ A and b ∈ A. Show that RPis an equivalence relation.(b) Now let R be an arbitrary equivalence relation on X. We showedin class that the set X/R ⊆ P (X) is a partition of X. Showthat the functions R 7→ X/R and P 7→ RPare inverse bijec-tions between the set of equivalence relations on X and the setof partitions of X.14. Let X be a set, let ≤ be a partial order relation on X, and let Y ⊆ X.Show that if a least upper bound for Y exists, then it is unique. Dothe same for greatest lower bounds for Y .5. Let a, b ∈ N \ {0}. Let p1< p2< · · · < pn∈ N be all of the primenumbers appearing in the prime factorizations of either a or b. Thenthere exist unique numbers r1, r2, . . . , rn, s1, s2, . . . , sn∈ N such thata = pr11· pr22· · · prnnand b = ps11· ps22· · · psnn.(a) Show that a divides b if and only if ri≤ sifor all i ∈ {1, . . . , n}.(b) For each i ∈ {1, . . . , n}, let min(ri, si) denote the smaller of riand si(so min(1, 2) = 1, for example). Show thatgcd(a, b) = pmin(r1,s1)1· pmin(r2,s2)2· · · pmin(rn,sn)n.(c) Calculate the prime factorizations of 38700 and 32760. Use part(b) to calculate gcd(38700, 32760).6. Find an inverse to 8 mod 45. Use this to find a solution to the equation8x = 13 mod 45.7. Show that the equation x6+ 9x2+ 1 = 0 has no integer