CPS102- Homework 2Due on September 29, 2005Questions may continue on the back. Please write clearly. What I cannot read, I will not grade. Typedhomework is preferable. A good compromise is to type the words and write the math by hand.The Duke Community Standard requires every undergraduate student to sign the statement below uponcompletion of each academic assignment. I am not allowed to accept your assignment unless you sign on theline below, if you intend to return this sheet, or you copy and sign the same statement on your own paper.I have adhered to the Duke Community Standard in completing this assignment.Signature:In all answers, show your work in detail. The first problem is problem 18 on page 95 of the book. The second is amodification of problem 32 on the same page.1. Let A, B, and C be sets. Show that(A − B) − C = (A − C) − (B − C) .[Hint: show that each side of the equation is contained in the other (a “mutual inclusion” proof).]2. The symmetric difference of A and B, denoted by A ⊕ B, is the set containing those elements in either A or B, but notin both A and B. In other words, an element in A ⊕ B is either in A but not in B, or in B but not in A:A ⊕ B = (A ∩ B) ∪ (A ∩ B) .Show that the symmetric difference is associative:A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C .Explain your reasoning carefully. [Hint: Either draw a Venn diagram for each side or go through blind formula manipulation.The second method is more straightforward but very boring and error prone, the first is more interesting. If you choose theboring method, you get no credit if you make mistakes in the manipulation.]3. Let A be the set of prime numbers smaller than 15, and B the set of perfect squares less than 15.(a) How many elements are in the power set of the Cartesian product of A and B?(b) How many elements are in the Cartesian product of the power sets of A and B?(c) How many elements are in the power set of the power set of B?(d) How many elements are in the power set of the power set of A?4. The power set of S2= {1, 2} is P (S) = {{}, {1}, {2}, {1, 2}}. Let us write the four elements of P (S2) on the corners of asquare, and draw an arrow from one corner to another whenever the set at the first corner is a subset of the set at the othercorner, and the first corner has exactly one fewer item than the second:{}{1}{2}{1,2}CPS102 — Duke — September 21, 2005Note that there is no arrow from the empty set {} to {1, 2}. This drawing is called a lattice. The lattice for the powerset P (S1) of S1= {1} is obviously simpler:{}{1}Interestingly, you can make the lattice for P (S2) by combining two copies of the lattice for P (S1) as follows. You firstdraw the two copies, and draw arrows from every corner in the first copy to its corresponding corner (that is, the corner withthe same set) in the second copy. On the left side of the figure below, copy 1 is drawn with a thick, solid arrow, copy 2 witha thick, dashed arrow, so we can distinguish them, and the connections between corresponding corners are drawn with thin,dotted arrows. Finally, we go through all the sets in copy 2, and add the member of S2that was missing in S1, that, is thenumber 2. This is shown on the right side of the figure below.{} {1}{} {1}{} {1}{2} {1, 2}The figure obtained in this way may not look visually like the lattice for S2we drew earlier, but it is the same in thesense that the arrows connect the same sets in the same way.(a) Draw the lattice for the power set P (S3) of the set S3without following the procedure above. Just connect the sets inthe figure below with an arrow whenever one set is a subset of the other, and the first set has exactly one fewer itemthan the second. The arrow points from the smaller set to the bigger one. Make sure you have all the arrows, and thatyou do not draw any that do not belong.{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}(b) Now redraw the lattice for the power set P (S3) of the set S3= {1, 2, 3} by combining two copies of the lattice forP (S2) with the procedure used above for making P (S2) out of P (S1) (the new element in S3is of course the number3). When doing so, draw arrows in the first copy with thick, solid lines, arrows in the second copy with thick, dashedlines, and arrows that connect the two copies with thin, dotted lines.(c) The lattices you drew in your answers to questions (a) and (b) of this problem probably look visually different, butought to be the same in the sense that the arrows connect the same sets in the same way in the two lattices. To checkthis, redraw the lattice in your answer to part (a) of this problem without changing the layout (i.e., the relative p ositionof the sets on paper), but using the arrow styles you used in part (b): thick, solid arrows when you connect two setsthat do not contain the number 3; thick, dashed arrows when you connect two sets that both contain the number 3;thin, dotted arrows when you connect a set without the number 3 to a set with the number 3. The equivalence of thetwo lattices should be more obvious now.(d) Suppose that instead of drawing your lattice for P (S3) on the plane you draw if in space. Specifically, a set S ∈ P (S3)is drawn at coordinates (x, y, z) according to the following rules:x =½1 if 1 ∈ S0 if 1 /∈ Sy =½1 if 2 ∈ S0 if 2 /∈ Sz =½1 if 3 ∈ S0 if 3 /∈ S.What geometric figure do you obtain when you draw your lattice? [Hint: draw it.]CPS102 — Duke — September 21,
View Full Document
Unlocking...