All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Disjointification (Posted on 2004-04-04)
Given N possibly overlapping sets, give formulas that specify, using intersections and complements of the given sets, N disjoint sets with the same union as the original N sets. The sets that result are to be the same as the given sets in the case where the given sets are already disjoint.

 Submitted by Richard Rating: 3.1667 (6 votes) Solution: (Hide) Let the given sets be A,B,C, etc. For the new sets we may take A,BA',CB'A', etc. where BA' denotes the intersection of B and the complement of A and CB'A' denotes the intersection of C with the complements of B and A. Supposing that the element k is in the given set K but not in any of the earlier given sets A, B,...,J, then k is in KJ'I'...A'. But k is not in any one of the earlier new sets IH'G'...A', HG'F'...A',...,A since it is not in any of H, G,...,A. Neither is k in any of the later new sets LK'J'...A', etc. all of which have a factor K'. Thus k is in the one and only new set KJ'I'...A', which means that every element of the given sets is in exactly one of the new sets and this makes the new sets disjoint and makes their union the same as the union of the given sets. (Page 7 of www.mcs.drexel.edu/~phitczen/notesfin.ps gives a typeset version of this solution. See also Exercise 2 on page 61 for an application.)

 Subject Author Date Missing part of the proof Oskar 2004-04-13 10:58:49 re: Impossible cases Richard 2004-04-05 13:29:25 re: Solution? Too simple? Richard 2004-04-05 13:24:58 Impossible cases e.g. 2004-04-05 10:35:35 Solution? Too simple? Jer 2004-04-05 09:40:42 re(4): Suggestions from Proposer Richard 2004-04-04 20:49:44 re(3): Suggestions from Proposer Charlie 2004-04-04 19:23:03 re(2): Suggestions from Proposer Richard 2004-04-04 18:44:30 Solution Federico Kereki 2004-04-04 15:30:49 re: Suggestions from Proposer Charlie 2004-04-04 13:25:50 Suggestions from Proposer Richard 2004-04-04 13:15:03 thoughts Charlie 2004-04-04 11:30:07

 Search: Search body:
Forums (0)