Date: Tue, 23 Oct 2001 06:34:53 -0500 (CDT) From: Mark Jacobson To: 810-080-01@uni.edu, 810-080-02@uni.edu Subject: PowerSet({a,b,c}) represented in binary - 000 to 111 Suppose set A = {a, b, c} PowerSet of {a, b, c} will have 2 cubed or 8 elements. Cardinality( {a,b,c} ) 3 Cardinality(PowerSet( {a,b,c} ) = 2 = 2 Cardinality(A) 3 Cardinality(PowerSet(A) = 2 = 2 = 8 Suppose we wish to represent the sets by using a 0 to indicate the element is not present and a 1 to indicate the element is present. 000 would represent the empty set, i.e. 000 is {} 111 would represent the set {a,b,c} 100 would represent the set {a} 010 would represent the set {b} 001 would represent the set {c} 110 would represent the set {a,b} 101 would represent {a,c} 011 would represent {b,c} abc 000 { } <----- Empty set 000 0 001 { c} 001 1 010 { b } 010 2 011 { b,c} 011 3 100 {a } 100 4 101 {a, c} 101 5 110 {a,b } 110 6 111 {a,b,c} <----- A 111 7 If we add a 4th element to set A, making it B = {a,b,c,d}, for example, the binary number 1111 = 15 = F would represent B. 2 10 16 0001 would represent {d} 1001 would represent {a,d} 0000 would represent {} There would be 16 different subsets of B, from 0000 = 0 to 1111 = 15 2 10 2 10 The PowerSet(B) = PowerSet( {a,b,c,d} ) could be represented as the 16 hexadecimal base 16 digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F 0 = 0000 {} 1 = 0001 {d} 2 = 0010 {c} ... D = 1101 {a,b,d} E = 1110 {a,b,c} F = 1111 {a,b,c,d}