|
Size: 801
Comment: Notations
|
← Revision 6 as of 2026-09-01 02:14:00 ⇥
Size: 956
Comment: Notes
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 25: | Line 25: |
| It can be proven that if ''|A| = n'', then ''|𝒫(A)| = 2^n^''. (The second notation above emphasizes this fact.) Furthermore '''Cantor's theorem''' proves that ''|A| < |𝒫(A)|'' for any set ''A''. | If ''|A| = n'', then ''|𝒫(A)| = 2^n^''. (The second notation above emphasizes this fact.) The [[Analysis/BinomialTheorem|binomial theorem]] provides a clever proof of this. Plug ''a = b = 1'' into the general formula: {{attachment:binom1.svg}} {{attachment:binom2.svg}} '''Cantor's theorem''' proves that ''|A| < |𝒫(A)|'' for any set ''A''. |
Power Set
A power set is the set of all subsets.
Contents
Description
Consider a set A = {x,y,z}. There exist 8 unique subsets of A, including the empty set and A itself.
{ } a.k.a. Ø
{x}
{y}
{z}
{x y}
{x z}
{y z}
{x y z}
The set of these subsets is called the power set of A. This is notated either as 𝒫(A) (note the calligraphic P), as 2A, or as {B | B ⊆ A}.
If |A| = n, then |𝒫(A)| = 2n. (The second notation above emphasizes this fact.) The binomial theorem provides a clever proof of this. Plug a = b = 1 into the general formula:
Cantor's theorem proves that |A| < |𝒫(A)| for any set A.