The example 1.2.2 of the book Statistical Inference by Casella and Berger states: if S has n elements, there are 2^n sets...(please see attached).
Could you please explain how the authors derived that formula? Thank you.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ In set theory, the cardinal number $2^n$ is defined to be the cardinality of the set of functions from a set of $n$ elements to a set of $2$ elements. Writing the latter set as $\{0,1\}$ (with no loss of generality) shows these functions can be identified with the indicator functions on $\mathcal B$--but an indicator function is determined by, and determines, the subset of $\mathcal B$ on which it equals $1,$ QED. In this way the quoted statement makes sense even when $\mathcal B$ is countably infinite. $\endgroup$– whuber ♦Commented Nov 18, 2019 at 17:27
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
It is the number of subsets of a given set. While constructing a subset, we have two choices for each element in the set, i.e. take it or leave it. For $n$ elements, we have $2\times2...2=2^n$ choices, so there are $2^n$ different subsets of a given set.
-
1$\begingroup$ Thanks, @gunes. Your answer was so elegant. It would be perfect if you could please point out why the multiplication (but not addition) was used, that is, 2 x 2 x... x 2 (instead of 2 + 2 + ... + 2)? $\endgroup$– NemoCommented Nov 18, 2019 at 6:03
-
6$\begingroup$ It’s one of the basic principles of counting. If you have $k$ different possibilities of a variable and $m$ different for another, there are $km$ possibilities for the tuple. $\endgroup$– gunesCommented Nov 18, 2019 at 6:12
-
1$\begingroup$ @gunes That principle actually has its own name: en.wikipedia.org/wiki/Rule_of_product $\endgroup$ Commented Nov 19, 2019 at 2:05
$\begingroup$
$\endgroup$
5
Although I am personally a fan of the answer laid out by @gunes (+1) for its simplicity, it is worth mentioning an alternative method of proof.
The number of subsets of $S$ consisting of exactly $k$ elements is "n choose k", i.e.
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}.$$
Thus the total number of subsets is given by
$$\begin{align*} |\mathcal B| &= \sum_{k=0}^n\binom{n}{k} \\[1.2ex] &= \sum_{k=0}^n\binom{n}{k}\times 1^k \times 1^{n-k} \\[1.2ex] &= (1+1)^n \\[1.2ex] &= 2^n \end{align*}$$ where the second to last equality is due to the binomial theorem.
-
1$\begingroup$ Thanks @knrumsey for showing me another perspective. Your answer does look like a rigorous proof but unfortunately it is too complex for me (not strong in Maths) to follow. I'm not sure what |S| is (absolute value of S?) and where the equality (that follows |S|) comes from. Also, I'm confused about the switching positions of n and k, that is, n choose k (n k) then k choose n (k n). I'll keep going back to your post hopefully one day I will understand it though. $\endgroup$– NemoCommented Nov 18, 2019 at 12:05
-
1$\begingroup$ @Nemo |S| denotes the number of elements in set S. The (k,n) switch is a typo. And, you need to look up binomial theorem, i.e. $(x+y)^n$ to understand this better. $\endgroup$– gunesCommented Nov 18, 2019 at 12:29
-
3$\begingroup$ This is not "more rigorous" than the answer from @gunes . It just proves a stronger result (which the OP does not need) and then deduces the size of the power set. $\endgroup$ Commented Nov 18, 2019 at 16:53
-
1$\begingroup$ @Nemo I don't want to discourage you but if this is too complex for you then you may want to consider going back and brushing up on your basics before attacking Casella and Berger. While sigma algebra stuff doesn't play too much of a role past the first introductory chapter (unless they've changed that since I've gone through the book) the arguments laid out in this answer should be something you can follow if you want to get through the chapter on discrete distributions. $\endgroup$– DasonCommented Nov 18, 2019 at 21:44
-
$\begingroup$ Thanks, @Dason. That's a great idea. Could you please advise what book would quickly bring me up to speed of that of Casella and Berger? $\endgroup$– NemoCommented Nov 18, 2019 at 23:22
$\begingroup$
$\endgroup$
2
This is called power set.
The other answers have information contained in the linked wikipedia page, though none of them surprisingly contain the term 'power set'. I think this answers a question that didn't ask but needs to know the answer to: 'What's the $\mathcal B$ called?' If Nemo knew what it was called, then Nemo wouldn't even be asking this question since Nemo would instead search google or wikipedia for 'number of elements in power set'.
-
1$\begingroup$ +1 @Mitjackson for the new concept (to me). Indeed I didn't know B is called power set. The book (Statistical Inference) called it Sigma Algebra (or Borel field). Thanks for pointing that out. $\endgroup$– NemoCommented Nov 18, 2019 at 23:18
-
3$\begingroup$ @Nemo, $\mathcal B$ is the power set since $S$ is finite. Note that a sigma algebra is not always equivalent to the power set. For instance, if $S = \mathbb R$, then the Borel field is not equivalent to the power set. $\endgroup$– knrumseyCommented Nov 19, 2019 at 1:18