Unions and Intersections: Proving SetsDate: 10/17/1999 at 18:33:04 From: Don Edgar Subject: Proving sets with unions and intersections The question given to me is: A student is asked to prove that for any sets A, B and C; A - (B union C) = (A - B) intersect (A - C). The student writes 'Let x be an element of A - (B union C). Then x is an element of A and x is not an element of B, or x is not an element of C. Therefore, x is an element of A - B and x is an element of A - C. Thus, A - (B union C) = (A - B) intersect (A - C).' What, if anything, is wrong with this proof? I have no idea what to do or how to go about this. I'm not sure if he's right or not or how he even came up with that thinking. If you could help me I would be most appreciative. Thank you very much. DE Date: 10/17/1999 at 22:06:06 From: Doctor Ian Subject: Re: Proving sets with unions and intersections Hi Don, I'm going to reformat the proof so I can refer to specific parts of it: [1] Let x be an element of A-(B union C). [2] Then x is an element of A and x is not an element of B or x is not an element of C. [3] Therefore, x is an element of A - B and x is an element of A - C. [4] Thus, A-(B union C) = (A - B)intersect(A - C). Technically, the third line of [2] should begin with 'and' instead of 'or'. Other than that, it's correct. It's easier to see what's going on with pictures. And the pictures are a lot better looking if you use overlapping circles instead of rectangles, but I have to do this with a keyboard, so... Imagine three sets - A, B and C - represented by three overlapping rectangles. +---------------+ | B | +--------|----+ | (Figure 1) | A | | | | | | | | +--------------+ | | | | | | | | | +----|----------+ | | | | +---|---------+ | | | | C | +--------------+ The union of B and C is everything that is in B, or in C, or both: +---------------+ |XXXXXXXXXXXXXXX| +--------|----+XXXXXXXXXX| (Figure 2) | A |XXXX|XXXXXXXXXX| | |XXXX|XXXXXXXXXX| | +--------------+XXXXX| | |XXXX|XXXX|XXXX|XXXXX| | |XXXX+----|----------+ | |XXXXXXXXX|XXXX| +---|---------+XXXX| |XXXXXXXXXXXXXX| |XXXXXXXXXXXXXX| +--------------+ The part left unfilled in the diagram above is everything that is in A that isn't in the union of B and C -- in other words, A - (B union C). A - B is everything that is in A that isn't also in B: +---------------+ | B | +--------|----+ | (Figure 3) |XXXXXXXX| | | |XXXXXXXX| | | |XXX+--------------+ | |XXX|XXXX| | | | |XXX|XXXX+----|----------+ |XXX|XXXXXXXXX| | +---|---------+ | | | | C | +--------------+ A - C is everything that is in A that isn't also in C: +---------------+ | B | +--------|----+ | (Figure 4) |XXXXXXXX|XXXX| | |XXXXXXXX|XXXX| | |XXX+--------------+ | |XXX| | | | | |XXX| +----|----------+ |XXX| | | +---|---------+ | | | | C | +--------------+ The intersection of these two sets is the part they have in common, +---------------+ | B | +--------|----+ | (Figure 5) |XXXXXXXX| | | |XXXXXXXX| | | |XXX+--------------+ | |XXX| | | | | |XXX| +----|----------+ |XXX| | | +---|---------+ | | | | C | +--------------+ The part that is left unfilled in Figure 2 is A - (B union C). The part that is filled in Figure 5 is (A - B) intersect (A - C). They're the same. So A - (B union C) = (A - B) intersect (A - C). Now let's look at the (corrected) proof again: [1] LET x BE AN ELEMENT OF A - (B UNION C). This is given. [2] THEN x IS AN ELEMENT OF A Because it's in the part of A that isn't in some other set, so it must at least be in A. AND X IS NOT AN ELEMENT OF B Because if it were an element of B, it would be in B union C. AND X IS NOT AN ELEMENT OF C. Because if it were an element of C, it would be in B union C. [3] THEREFORE X IS AN ELEMENT OF A - B Because it's in A, but not in B. AND X IS AN ELEMENT OF A - C. Because it's in A, but not in C. [4] THUS, A - (B UNION C) = (A - B) INTERSECT (A - C). Because it's in both (A - B) and in (A - C). I hope this helps. Be sure to write back if you're still confused, or if you have any other questions. - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/