# 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 $\displaystyle S$

$\displaystyle | \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 $\displaystyle \psi(S) = |\wp(S)|$

and let

$\displaystyle S + 1$

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

|$\displaystyle S + 1| = |S| + 1$

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

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

thus the following also holds for any $\displaystyle S$

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

we take as our inductive hypothesis that

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

recall that for any set $\displaystyle S$ we assume

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

which we can rearrange as follows

$\displaystyle \psi(S + 1) = 2 \times 2^{|S|}$
$\displaystyle \psi(S + 1) = 2^{|S| + 1}$
$\displaystyle \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 $\displaystyle \wp (\{ 1,2,...,n,n + 1\} )$ contains $\displaystyle \wp (\{ 1,2,...,n\} )$ plus $\displaystyle \left\{ {X \cup \{ n = 1\} :X \in \wp (\{ 1,2,...,n\} )} \right\}$.
Hence $\displaystyle \wp (\{ 1,2,...,n, n+1\} )$ contains twice as many sets as $\displaystyle \wp (\{ 1,2,...,n\} )$.