12
$\begingroup$

In my probability book, it says that to count the total number of subsets of n elements is a process of $n$ stages with binary choice of either adding this element to the subset or not to add it. Therefore, the total number is $$2^n$$

But, for instance, we have 3 elements, according to this formula, there are 2 to the power of 3 elements, namely 8, which are $${\emptyset},A,B,C, AB, AC, BC, ABC$$

However, I have a hard time of imagining the process or N stages binary choice that form this many subsets. Can anyone explain/help me to understand it? I mean, ABC, if we are making the choice of A, put it in or do not put it in, exactly which subset are we choosing to put in or not? Thank you.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure what you were trying to ask. I wrote an answer and other people seem to think it doesn't answer the question. Were you asking how for any finite set, it's possible to count all the subsets of that set or were you asking whether there is a uniform way of defining for all finite sets how to do it for that set? $\endgroup$ – Timothy Jan 10 at 7:18
  • 1
    $\begingroup$ @Timothy I was having trouble understanding this in the process described by Eelvex's answer, but now I understood...thanks! $\endgroup$ – commentallez-vous Jan 10 at 8:23
  • $\begingroup$ I'm confused. Was it my answer that you understood? If so, the fact that my answer got 5 downvotes probably means that people sometimes don't know what confusion the OP has when they ask a question. $\endgroup$ – Timothy Jan 10 at 18:10
  • 1
    $\begingroup$ @Timothy, hi Timothey, sorry I haven't checked your answer yet...and I never gave people down vote...but I'll read it now. $\endgroup$ – commentallez-vous Jan 10 at 18:15
65
$\begingroup$

enter image description here

  • "Include A?" is stage 1
  • "Include B?" is stage 2
  • "Include C?" is stage 3.
$\endgroup$
21
$\begingroup$

Label your $n$ elements so that $X=\{x_{1},...,x_{n}\}$. We're going to form a one-to-one correspondence between the subsets of $X$ and the set of length-$n$ binary strings as follows. Given a binary string $$a_{1}\cdots a_{n}$$ imagine that $a_{i}=1$ means "include $x_{i}$ in this subset" and $a_{i}=0$ means "exclude $x_{i}$ in this subset". For example, if $n=4$ then the subset $S=\{x_{1},x_{3}\}$ would be represented as $1010$.

There are exactly $2^{n}$ possible strings, since each $a_{i}$ has two possible values, and there are $n$ of them. And each string corresponds to one and only one subset of $X$. Therefore there are $2^{n}$ subsets.

$\endgroup$
  • $\begingroup$ Thanks pwerth, this is a wonderful and direct view on the process using 1010 as an example. $\endgroup$ – commentallez-vous Jan 9 at 22:32
  • $\begingroup$ You're welcome, glad to help! $\endgroup$ – pwerth Jan 9 at 22:32
5
$\begingroup$

Write out all the binary numbers with $3$ digits. Each digit represents one element ($0$ means exclude, $1$ means include): $$ \begin{array}{|c|c|} \text{decimal}&\text{binary}&\text{subset}\\\hline 0&000&\{\}\\ 1&001&\{C\}\\ 2&010&\{B\}\\ 3&011&\{B,C\}\\ 4&100&\{A\}\\ 5&101&\{A,C\}\\ 6&110&\{A,B\}\\ 7&111&\{A,B,C\}\\ \end{array} $$ This is easily extendible to an $n$ element set with $n$ digit binary numbers.

$\endgroup$
  • 1
    $\begingroup$ Note the relationship between the binary numbers and the subset elements: $000 \to \{ \}, 001 \to \{C\}, 010 \to \{B\}, 011 \to \{B,C\}, \dots$. $\endgroup$ – steven gregory Jan 10 at 14:36
  • $\begingroup$ I believe that this is the same as pwerth's answer. $\endgroup$ – Scott Jan 12 at 5:14
4
$\begingroup$

I think, more directly, what the book is saying can be stated as:

Choosing a subset $U$ of a set $S$ is the same as, for each element $x\in S$, choosing whether $x$ is in $U$ or not.

In particular, there is, at any time, only one set we're considering. So, if $S=\{A,B,C\}$ and we want to choose a subset $U$, we could make the following three choices: $$A\in U$$ $$B\in U$$ $$C\in U$$ And we would get $U=\{A,B,C\}$. So, we've constructed a subset by making three binary choices. We could try this process again to make a different subset; for instance, we could decide instead $$A\not\in U$$ $$B\not\in U$$ $$C\in U$$ And then get $U=\{C\}$. So, we've made a different set of choices and got a different set. So, for each subset, we have to make three choices.

$\endgroup$
  • $\begingroup$ Thank you Milo, I think I got it using your explanation with pwerth's. I really appreciate it! $\endgroup$ – commentallez-vous Jan 9 at 22:34
4
$\begingroup$

The set of subsets of $X$ can be seen as the set of all functions from $X$ to $\{0,1\}$, denoted $\{0,1\}^X$.

For each such function, consider the subset of $X$ consisting of all $x\in X$ such that $f(x)=1$.

This, it turns out, is a $1-1$correspondence.

As a result, the order of the power set is $\mid P(X)\mid=\mid \{0,1\}^X\mid=\mid\{0,1\}\mid^{\mid X\mid}=2^n$.

$\endgroup$
4
$\begingroup$

Proof by induction (on number of elements in the set):

For $n = 0$, there is exactly $2^0=1$ subset of a set with 0 elements, namely the empty set itself.

Assuming that any set $U_n$ with $n$ elements has $2^n$ subset, consider a set $U_{n+1}=U_n \cup \{x\}$ (where $x \notin U_n$). Which subsets of $U_{n+1}$ exists?

  • The subsets which do not include $x$ are exactly the subsets of $U_n$ (there are $2^n$ such subsets)
  • Any other subset includes $x$, so it is of the form $A \cup \{x\}$, where $A$ is a subset of $U_n$ (because all elements in $U_{n+1}$ except $x$ are also elements of $U_n$), and it's clear that such subset exists (and is unique) for each $A \subset U_n$. So, the number of $U_{n+1}$ subsets which include $x$ is also $2^n$.

So, the total count of $U_{n+1}$ subsets is $2^n+2^n=2^{n+1}$. The proof is complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.