Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Power set"
m
Line 1: Line 1:
 
The '''power set''' of a given [[set]] <math>S</math> is the set <math>\mathcal{P}(S)</math> of [[subset]]s of that set.   
 
The '''power set''' of a given [[set]] <math>S</math> is the set <math>\mathcal{P}(S)</math> of [[subset]]s of that set.   
  
 +
==Examples==
 
The [[empty set]] has only one subset, itself.  Thus <math>\mathcal{P}(\emptyset) = \{\emptyset\}</math>.
 
The [[empty set]] has only one subset, itself.  Thus <math>\mathcal{P}(\emptyset) = \{\emptyset\}</math>.
  
Line 9: Line 10:
 
Similarly, for any [[finite]] set with <math>n</math> elements, the power set has <math>2^n</math> elements.
 
Similarly, for any [[finite]] set with <math>n</math> elements, the power set has <math>2^n</math> elements.
  
 +
==Size comparison==
 
Note that for any [[nonnegative]] [[integer]] <math>n</math>, <math>2^n > n</math> and so for any finite set <math>S</math>, <math>|\mathcal P (S)| > |S|</math> (where [[absolute value]] signs here denote the [[cardinality]] of a set).  The analogous result is also true for [[infinite]] sets (and thus for all sets: for any set <math>S</math>, the cardinality <math>|\mathcal P (S)|</math> of the power set is strictly larger than the cardinality <math>|S|</math> of the set itself.
 
Note that for any [[nonnegative]] [[integer]] <math>n</math>, <math>2^n > n</math> and so for any finite set <math>S</math>, <math>|\mathcal P (S)| > |S|</math> (where [[absolute value]] signs here denote the [[cardinality]] of a set).  The analogous result is also true for [[infinite]] sets (and thus for all sets: for any set <math>S</math>, the cardinality <math>|\mathcal P (S)|</math> of the power set is strictly larger than the cardinality <math>|S|</math> of the set itself.
  

Revision as of 23:50, 27 August 2006

The power set of a given set $S$ is the set $\mathcal{P}(S)$ of subsets of that set.

Examples

The empty set has only one subset, itself. Thus $\mathcal{P}(\emptyset) = \{\emptyset\}$.

A set $\{a\}$ with a single element has two subsets, the empty set and the entire set. Thus $\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$.

A set $\{a, b\}$ with two elements has four subsets, and $\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$.

Similarly, for any finite set with $n$ elements, the power set has $2^n$ elements.

Size comparison

Note that for any nonnegative integer $n$, $2^n > n$ and so for any finite set $S$, $|\mathcal P (S)| > |S|$ (where absolute value signs here denote the cardinality of a set). The analogous result is also true for infinite sets (and thus for all sets: for any set $S$, the cardinality $|\mathcal P (S)|$ of the power set is strictly larger than the cardinality $|S|$ of the set itself.

Proof

There is a natural injection $S \hookrightarrow \mathcal P (S)$ taking $x \mapsto \{x\}$, so $|S| \leq |\mathcal P(S)|$. Suppose for the sake of contradiction that $|S| = |\mathcal P(S)|$. Then there is a bijection $f: \mathcal P(S) \to S$. Let $T \subset S$ be defined by $T = \{x \in S \;|\; x \not\in f(x) \}$. Then $T \in \mathcal P(S)$ and since $f$ is a bijection, $\exists y\in S \;|\; T = f(y)$.

Now, note that $y \in T$ by definition if and only if $y \not\in f(y)$, so $y \in T$ if and only if $y \not \in T$. This is a clear contradiction. Thus the bijection $f$ cannot really exist and $|\mathcal P (S)| \neq |S|$ so $|\mathcal P(S)| > |S|$, as desired.

See Also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Power_set&oldid=9915"