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