1
$\begingroup$

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?

  • 0
    Asaf has given a nice expanded version; why don’t you go ahead and accept his instead.2019-02-19

1 Answers 1

1

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.