# inductive proof of size of power sets

Printable View

• September 14th 2007, 10:07 AM
polypus
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
• September 14th 2007, 10:12 AM
polypus
worries
i'm just worried that the fact that my consequent is essentially included in my antecedent invalidates the proof, correct?
• September 14th 2007, 11:01 AM
Plato
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\} )$.
All times are GMT -8. The time now is 09:09 AM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 25, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9452171325683594, "perplexity_flag": "middle"}