Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

{1},{1,3}
{2},{2,3}
{1,2},{1,2,3}

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

share|improve this question
4  
$\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

1 Answer 1

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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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