# count the number of subsets

How many subsets are there in {{1,2,3},{4,5,6},{7,8,9}}. The answer I gave was three, but I was told that was incorrect. There were no other words in the question (pairwise, etc).I was told by someone that I should have considered all possible combinations of all the elements but that makes no sense to me (to do that, not that I don't know how).

-
"How many subsets are there in ..." makes sense (to me) only if what follows in the sentences is a set. It's not clear in that notation what are the elements of that set. If we consider each triplet as an element of our set (call {1,2,3}=A {4,5,6}=B...) we have a set of 3 elements, which give us 8 subsets. This would be quite a confusing way of specifying a set, but I cannot think of something more reasonable. – leonbloy Jun 2 '11 at 15:07
That was the way the question was phrased. What would make more sense? – soandos Jun 2 '11 at 15:09
@leonbloy: I don't see why it's confusing… writing a set as {A, B, C} is standard notation, and here A happens to be {1,2,3}, etc. This seems a straightforward question to me. – ShreevatsaR Jun 2 '11 at 15:11
@ShreevatsaR I don recall if there were letter there or numbers, but I assume that that also would not matter. Why is my answer wrong? – soandos Jun 2 '11 at 15:14

A set {A,B,C} has 8 subsets. The subsets are:

• $\emptyset$, the empty set
• {A}, here {1,2,3}
• {B}, here {4,5,6}
• {C}, here {7,8,9}
• {B,C}, here {{4,5,6},{7,8,9}}
• {A,C}, here {{1,2,3},{7,8,9}}
• {A,B}, here {{1,2,3},{4,5,6}}
• {A,B,C}, the set itself, here {{1,2,3},{4,5,6},{7,8,9}}

More generally, a set with $n$ elements has $2^n$ subsets. One way of seeing this is that for each of the $n$ element you have 2 choices: whether to include it in the subset or not.

-
And the elements of A are sub-sub-sets and so are not counted? – soandos Jun 2 '11 at 15:31
@soandos: The elements of A are just elements of A. There exist subsets of A like {1,2} or {1}, but they are subsets of A and not subsets of the set {A,B,C}. From the point of view of a set {A,B,C}, it doesn't matter what A, B, C, are; its subsets are exactly those sets in which element is either A, B, or C — namely, the 8 mentioned above. For instance a strange set like {{1,2,{3,4,5}}, "hello", 42} will still have exactly 8 subsets. – ShreevatsaR Jun 2 '11 at 15:38
Got it, thanks. – soandos Jun 2 '11 at 15:42

There are 8 subsets. As leonbloy mentioned in his comment, the set given to you has 3 elements. The elements happen to be sets themselves, but that doesn't matter. To be explicit, if $a=\{1,2,3\}$, $b=\{4,5,6\}$, and $c=\{7,8,9\}$ then the set is $A=\{a,b,c\}$ and its subsets are $\emptyset$, $\{a\}=\{\{1,2,3\}\}$, $\{b\}=\{\{4,5,6\}\}$, $\{c\}$, $\{a,b\}$, $\{a,c\}$, $\{b,c\}$, and $\{a,b,c\}=A$.

This may sound confusing at the beginning as one tends to think of "types": there are elements, then sets, then "families of sets" if need be, and rarely anything else. But in some contexts it is actually a natural situation. In set theory, everything is a set, so the elements of any set are always sets.

-
Why isn't every element also a subset? – soandos Jun 2 '11 at 15:25