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

worries

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

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 $<br /> \wp (\{ 1,2,...,n\} )$ .