

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

From the Wikipedia article on power sets,

... one can select any element x of a set, S, and gather up the subsets of S itself into pairs (A-, A+) that are identical excepting that A- does not include x and A+ does.

So if S = {1,2,3}, and we choose x to be 3, I get pairs


But there should be 23 = 8 sets. Which am I missing?

share|cite|improve this question
$\varnothing,\{3\}$ – Brian M. Scott Aug 24 '12 at 20:09
so those two would also be a pair? – James Aug 24 '12 at 20:10
Yes, they would; they’re your missing pair. – Brian M. Scott Aug 24 '12 at 20:14
ok, thanks. i would mark this as the answer.. – James Aug 24 '12 at 20:47
Asaf has given a nice expanded version; why don’t you go ahead and accept his instead. – Brian M. Scott Aug 25 '12 at 15:46
up vote 1 down vote accepted

Let us write the power set of $S=\{1,2,3\}$:

$$\mathcal P(S)=\Bigg\{\varnothing,\underbrace{\{1\},\{2\},\{3\}}_{\text{singletons}},\overbrace{\{1,2\},\{1,3\},\{2,3\}}^{\text{pairs}},\{1,2,3\} \Bigg\}$$

You have chosen $3$, so we essentially going to write $S$ as $S\setminus\{3\}\cup\{3\}$. Note that this is to write a set of three elements as $2+1$, taking a power set, in terms of size it to raise by a power of $2$, so we have $2^3=2^{2+1}=2^2\times 2$.

This means that indeed we can write $\mathcal P(S)$ as four pairs of the form: $\langle A,B\rangle$ where $A\subseteq S\setminus\{3\}$ and $B=A\cup\{3\}$. Of course we can replace $S$ by an arbitrary set (even infinite!) and $3$ by an arbitrary element of this set. The calculation pans out the same way:

First we write a table of all the subsets of $\{1,2\}$, and fill the $B$ coloumn:

$$ \begin{array}{lcr} \begin{array}{|c|c|} \hline A & B\\\hline \varnothing & \\\hline \{1\} & \\\hline \{2\} & \\\hline \{1,2\} & \\ \hline \end{array} & \text{We add the }3: \begin{array}{|c|c|} \hline A & B\\\hline \varnothing & \varnothing\cup\{3\}\\\hline \{1\} & \{1\}\cup\{3\}\\\hline \{2\} & \{2\}\cup\{3\}\\\hline \{1,2\} & \{1,2\}\cup\{3\}\\ \hline \end{array} & \text{and finally:} \begin{array}{|c|c|} \hline A & B\\\hline \varnothing & \{3\}\\\hline \{1\} & \{1,3\}\\\hline \{2\} & \{2,3\}\\\hline \{1,2\} & \{1,2,3\}\\ \hline \end{array} \end{array}$$

Indeed four rows, eight elements. We wrote all $\mathcal P(S)$ as a list of pairs as wanted.

share|cite|improve this answer

Your Answer


