Subject: HW8: 200909_102694_CH From: "William J. Rapaport" Date: Wed, 4 Nov 2009 20:28:30 -0500 (EST) Concerning HW 8, problem 12: First, some notation: I'll use "u" for union, "n" for intersection, "e" for set-membership, and "<=" for the subset relation (which, don't forget, looks like a less-than-or-equal sign). Several of you have emailed me with sample proofs of: A u (A n B) = A. I haven't yet seen any that are completely correct. So let me give you some suggestions. *One* way to prove that two sets are equal is to prove that each is a subset of the other, because, for any sets S,T: S=T <-> (S<=T ^ T<=S). So you could consider 2 cases: case 1: Au(AnB) <= A case 2: A <= Au(AnB) To prove case 1, show that an arbitrary x e Au(AnB) is also such that x e A (see suggestion in next paragraph). To show case 2, show the converse of that. To show the first subset relationship, convert the "x e Au(AnB)" proposition into its propositional-logic definition; then you can use the rules of propositional logic to show that x e A. *Another* way to prove that two sets are equal is to use the other method that I showed in lecture, namely, start with the definition of Au(AnB) = {x | x e Au(AnB)} = [here, replace the set by its propositional logic definition, and keep transforming it till you get to...] = {x | x e A} = A.