- #1
- 3,020
- 2
I have encountered this set problem that seems simple enough at first glance, but I'm pretty ignorant about formal set theory and unsure of the rules. As I encountered it, this is how it was written:
For any set S let P(S) denote all subsets of S.
For example S={1,2}
Then P(S)= {Ø, {1}, {2}, {1,2}
If T has 3 members how many members does set P(P(T)) [have]?
a.) 2^3
b.) 3^2
c.) 3^4
d.) 2^8
Based on what little I have read here I am assuming the line above should read
Then P(S)= {{Ø}, {1}, {2}, {1,2}}
or maybe the null set is a special case that does not need brackets? Notation problems aside, this defining equation spells out the basic structure of P(S) for S with 2 elements. The extension to P(T) for T with three elements seems straightforward.
T = {1,2,3}
P(T)= {{Ø}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
which clearly has 8 elements. What the question asks for is the number of elements in P(P(T)), so I need to count the subsets of P(T). I know that for any set with N elements the number of subsets is going to be countable using the sum of binomial coefficients with the result being 2^N. Since P(T) has 8 elements I'm inclined to say the answer to the question is
d.) 2^8
What I am concerned about is redundancy of subsets. That issue might be resolved by making a proper distinction between these two things
P(T)= {{Ø}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
p(T) = {{Ø}, 1, 2, 3, {1,2}, {1,3}, {2,3}, {1,2,3}}
If I was forming subsets of the latter of these two, I think I might have to say that the set {1,2} formed from elements 1 and 2 of p(T) is redundant with the subset that is the single element {1,2}. If so, should I be counting that set twice when I count the subsets of p(T)? I'm not sure how many redundancies there are, or what the proper treatment would be for the subset made up of the elements 1 and {1,2}. Would it be {1,1,2} or just {1,2}? If I had to bet, I would go with the first of these.
Now for P(T), where each element is itself a set, I am assuming that each set element retains its identity, so that there is no redundancy between {{1},{2}} and {1,2}. That makes the 2^8 answer look a lot better, except for one last issue. Since {Ø} is already an element of P(T), is it proper to count {Ø} a second time as the null set of P(T), or is this one last remaining redundancy being overcounted?
If I'm on the wrong track with any of this, someone please enlighten me, and please comment on that last issue of the duplicate null set.
For any set S let P(S) denote all subsets of S.
For example S={1,2}
Then P(S)= {Ø, {1}, {2}, {1,2}
If T has 3 members how many members does set P(P(T)) [have]?
a.) 2^3
b.) 3^2
c.) 3^4
d.) 2^8
Based on what little I have read here I am assuming the line above should read
Then P(S)= {{Ø}, {1}, {2}, {1,2}}
or maybe the null set is a special case that does not need brackets? Notation problems aside, this defining equation spells out the basic structure of P(S) for S with 2 elements. The extension to P(T) for T with three elements seems straightforward.
T = {1,2,3}
P(T)= {{Ø}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
which clearly has 8 elements. What the question asks for is the number of elements in P(P(T)), so I need to count the subsets of P(T). I know that for any set with N elements the number of subsets is going to be countable using the sum of binomial coefficients with the result being 2^N. Since P(T) has 8 elements I'm inclined to say the answer to the question is
d.) 2^8
What I am concerned about is redundancy of subsets. That issue might be resolved by making a proper distinction between these two things
P(T)= {{Ø}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
p(T) = {{Ø}, 1, 2, 3, {1,2}, {1,3}, {2,3}, {1,2,3}}
If I was forming subsets of the latter of these two, I think I might have to say that the set {1,2} formed from elements 1 and 2 of p(T) is redundant with the subset that is the single element {1,2}. If so, should I be counting that set twice when I count the subsets of p(T)? I'm not sure how many redundancies there are, or what the proper treatment would be for the subset made up of the elements 1 and {1,2}. Would it be {1,1,2} or just {1,2}? If I had to bet, I would go with the first of these.
Now for P(T), where each element is itself a set, I am assuming that each set element retains its identity, so that there is no redundancy between {{1},{2}} and {1,2}. That makes the 2^8 answer look a lot better, except for one last issue. Since {Ø} is already an element of P(T), is it proper to count {Ø} a second time as the null set of P(T), or is this one last remaining redundancy being overcounted?
If I'm on the wrong track with any of this, someone please enlighten me, and please comment on that last issue of the duplicate null set.