Counting the elements of a set of sets

OlderDan

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.

matt grime

You are slghtly on the wrong track. If S has cardinality n (some integer) then P(S) has 2^n elements. That is true. And thus P(P(S)) is just the power set of a set with 2^n elements in it. What those elements are or how you choose to denote them is immaterial, the final answer is 2^(2^n).

There is no "redundancy".

honestrosewater

I can't get through a proof of this, but I suspect that if, in forming P(P(S)), {x} could be formed twice, then x would have appeared twice in P(S). ??

Oh, and {Ø} is in P(S) iff Ø is in S. Since Ø is a subset of every set, Ø is in every P(S).

OlderDan

I "like" Matt's answer because it fits with the simple counting scheme I used to choose an answer to the problem. In this case 2^(2^n) = 2^8 is clean and simple. But in daytime hours I realize the issue of the null set is bigger than what I stated in the wee hours of the morning. If {Ø} is one of the eight elements of P(T), then every combination of elements used to form subsets that includes {Ø} is a candidate for "rendundency".

For example, one subset of P(T) would be {1}, and another would be {{Ø},{1}}. On the one hand I can almost buy the idea that what {Ø} is and how it is represented is immaterial. On the other hand I have this notion that the null set has special properties that distinguish it from other sets. Would one not say that the union {Ø}U{A} = {A} for all {A}, and is that not a unique property of {Ø}? If so, then I need to convince myself that {{Ø},{1}} and {Ø}U{1} are not the same thing, or that the set {1} can be included and counted twice in P(P(T)), once because it is an element of P(T) already, and once because it is combined with another element of P(T) that just happens to be the null set.

It's not that I don't believe you Matt. It just still doesn't feel quite right. If anyone would care to elaborate on this, or point me to a reference link that might help me sort it out, I would appreciate it.

master_coda

While it is true that Ø U{A} = {A}, why would you think that {Ø}U{A} = {A}? Note that {Ø} is not the null set.

honestrosewater

(I like empty braces {} = Ø.) {} contains no elements. {{}} contains one element: {}. {} is still a set. {} U {A} = {A}. {{}} U {A} = {{}, A}.
bah, beat to the punch again.

OlderDan

Because I am not fluent in the notation. This suggests to me that perhaps my first error was in writing

P(S)= {{Ø}, {1}, {2}, {1,2}}

and subsequently writing

P(T)= {{Ø}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

in my original post. I added the brackets around the Ø. Should it have been

P(T)= {Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}?

and if so, what does that do to the count of the subsets of P(P(T))?

master_coda

Yes, P(T)= {Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} is correct. That means that P(T) contains 8 elements, and so P(P(T)) contains 2^8=256 elements.

HallsofIvy

Notice that the "elements" of P are the numbers 1, 2, 3. φ is not one of those elements, it is a set itself (the empty set) and not a member of any set which is what
{φ} would mean. {φ} is a set that is not empty- it has one member which happens to be the empty set.

OlderDan

Thanks all. I think most of this is sinking in. Going back to my earlier statement, with the notation hopefully corrected

I can handle that. If I do get it, I would have to say it is just a specific example of the general case

{{a},{a,b}} [tex]\ne[/tex] {a}U{a,b} = {a,b}

I'm still a little uncomfortable with the idea that Ø, being an element of P(T), is counted among the single element subsets of

P(T)= {Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

in addition to being counted as the null set of P(T). To build P(T) from T, I have

T = {1, 2, 3}, a three element set with 2^3 = 8 subsets, which are the elements of

P(T)= {Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

If I start listing the subsets of P(P(T)) in order from smallest (fewest elements) to largest, to get 2^8 = 256 subsets the list has to include a null set, then the eight individual elements of P(T), the first of which is a null set, then all 28 combinations of 8 elements taken 2 at a time, etc., etc.

P(P(T)) = {Ø, Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, . . . }

I'm OK with all the other combinations of elements of P(T) being unique elements of P(P(T)), but I'm still seeing two null sets as subsets of P(P(T)). Is there some notion of distinguishable null sets? Are the two Øs in the list really different things? My issue is sort of "resolved" if I go back to Matt's statement and identify the eight elements of P(P(T)) as

P(P(T)) = {A, B, C, D, E, F, G, H}

ignoring what those elements are. That's effectively what I did when I first encounterd the problem, but that seems a bit like hiding the issue instead of resolving it.

fourier jr

if there were two different empty sets one would have element(s) different from the other one. since they both have no elements, the two "different" empty sets are really the same set, so there is a unique empty set.

fourier jr

make a list of all the n elements in your set:
a_1, a_2,... a_n

since an element can be either in a subset or not in a subset, that makes 2 possibilities for an element. since there are n elements, you get (2x2x...x2) = 2^n elements in the power set of a set. so in general when you add 1 element to a set, you double the number of subsets of the same set.

example: there's an algorithm to help figure this out. take {a,b} & we want to count up the number of subsets of {a,b,c}. make a list of all the subsets of {a,b}: {empty set, {a}, {b}, {a,b}} which makes 4 subsets of {a,b}. now add the single element c & you get another list of 4 subsets: {{c}, {a,b}, {b,c}, {a,b,c}}. there are 4 subsets of {a,b,c} with c, & without c. it works for any finite set

OlderDan

Let Ø = empty set, because it is easier to write

S = {a,b}
P(S) = {Ø, {a}, {b}, {a,b}}

P(S) is the set whose elements are the subsets of S

If I now add an element, c, to my original set S I obtain a new set T

T = SU{c} = {a,b,c}
P(T) = {Ø, {a}, {b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}}
P(T) = {Ø, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

There are the original four subsets and the new four you talked about. I know that if I add another element to T to form a new set that I will double the number of subsets to 16, and that every additional element is going to double the number again. That was the starting point for this discussion. For a set with N elements the number of subsets is 2^N. The issue here is that the set P(T) contains 8 elements that happen, by construction, to be subsets of a set with 3 elements. So P(T) already contains an empty set as one of its elements.

It now occurs to me that I was writing P(P(T)) wrong, and that it should be

P(P(T)) = {Ø, {Ø}, {{a}}, {{b}}, {{c}}, {{a,b}}, {{a,c}}, {{b,c}}, {{a,b,c}}, {{Ø},{a}}, {{Ø},{b}}. . . . . .}

with 2^8 elements. Somebody tell me this is right and I will go away happy.

fourier jr

yes if T has 3 elements then P(T) would have 2^3 = 8 elements & P(P(T)) would have 2^(2^3) = 2^8 elements. there's still only one empty set though, & that fact has nothing to do with this particular problem. P(P(T)) would have the empty set and also the set {empty set} in it. i wonder if that's what's confusing.

matt grime

There are not two phi's in the list of P(P(T)). There is one phi and one set that contains phi.

Your list of elements of P(P(T)) is not correct since ti does not contain any sets of things in P(T).

If T={1,2}

Then P(T) has as elements 0, {1}, {2}, {1,2} where i use 0 for the empty set.

P(P(T)) has elements

0, {0} {{1}}, {{2}}, {{1,2}}, {0,{1}}, {0,{2}}, {0,{1,2}}

{{1},{2}}, {{1},{1,2}} {{2},{1,2}}, {0,{1},{2}} {0,{2},{1,2}}

{0,{1},{1,2}} {{1},{2},{1,2} and {0,{1},{2},{1,2}


which is horribly ugly but correct and has 16 elements.

Remember things in P(P(T)) are sets of subsets of T.

master_coda

Yes, that seems to be correct now.

OlderDan

That is what I was missing. I understood the distinction between Ø and {Ø} from earlier posts in this thread, but when I started writing the elements of P(P(T)) I was using elements of P(T) instead of subsets of P(T)

Sorry to put you through all that work Matt. I finally got this through my head before my last post. You lost a couple of }s in your post, but conceptually it is all there. Thanks. I should have written it out for a starting set of two elements in the first place. I might have gotten here quicker.

Thanks all. I've got it.