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

Home > Just Math
Disjointification (Posted on 2004-04-04) Difficulty: 3 of 5
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.)

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Some ThoughtsMissing part of the proofOskar2004-04-13 10:58:49
re: Impossible casesRichard2004-04-05 13:29:25
re: Solution? Too simple?Richard2004-04-05 13:24:58
Some ThoughtsImpossible casese.g.2004-04-05 10:35:35
Solution? Too simple?Jer2004-04-05 09:40:42
re(4): Suggestions from ProposerRichard2004-04-04 20:49:44
Questionre(3): Suggestions from ProposerCharlie2004-04-04 19:23:03
re(2): Suggestions from ProposerRichard2004-04-04 18:44:30
SolutionSolutionFederico Kereki2004-04-04 15:30:49
Solutionre: Suggestions from ProposerCharlie2004-04-04 13:25:50
Suggestions from ProposerRichard2004-04-04 13:15:03
Some ThoughtsthoughtsCharlie2004-04-04 11:30:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information