# Thread: inductive proof of size of power sets

1. ## inductive proof of size of power sets

hi everybody,

i have written an inductive proof of the statement that for any set $S$

$| \wp(S) | = 2 ^ {|S|}$

I am using my own notation for denoting set union with a disjoint set of cardinality 1, because it is such a convenience. is there some standard way of doing this? any tips/corrections, mathematical, stylistic, or notational will be highly appreciated.

Let $\psi(S) = |\wp(S)|$

and let

$S + 1$

denote $S \cup T$ where $T$ is some set disjoint from $S$ and where $|T| = 1$, so that we can write

| $S + 1| = |S| + 1$

The following holds trivially for $S = \emptyset$ and we will assume it to hold for any arbitrary set $S$ as well

$[\frac{\psi(S + 1)}{2} = 2 ^ {|S|}] \wedge [\psi(S) = 2 ^ {|S|}]$

thus the following also holds for any $S$

$\psi(S) = 2 ^ {|S|}$

we take as our inductive hypothesis that

$[\psi(S) = 2 ^ {|S|}] \rightarrow [\psi(S + 1) = 2^{|S + 1|}]$

recall that for any set $S$ we assume

$\frac{\psi(S + 1)}{2} = 2 ^ {|S|}$

which we can rearrange as follows

$\psi(S + 1) = 2 \times 2^{|S|}$
$\psi(S + 1) = 2^{|S| + 1}$
$\psi(S + 1) = 2^{|S + 1|}$

which proves the inductive step and the theorem.

thank again for any tips

2. ## worries

i'm just worried that the fact that my consequent is essentially included in my antecedent invalidates the proof, correct?

3. Sorry, but I have absolutely no idea what you have done there!

The usual way is to observe that $\wp (\{ 1,2,...,n,n + 1\} )$ contains $\wp (\{ 1,2,...,n\} )$ plus $\left\{ {X \cup \{ n = 1\} :X \in \wp (\{ 1,2,...,n\} )} \right\}$.
Hence $\wp (\{ 1,2,...,n, n+1\} )$ contains twice as many sets as $
\wp (\{ 1,2,...,n\} )$
.