Operations and families · Definition

Power set

set theoryoperations and families

Before you start you need to know

The power set collects every way of choosing elements from \(A\), including choosing none and choosing all of them.

Definition

The set of all subsets of a set \(A\), denoted \(\mathcal{P}(A)\).

\[\mathcal{P}(A) = \{X : X \subseteq A\}\]

For a set \(A\), \(\mathcal{P}(A)\) contains exactly the sets \(X\) with \(X \subseteq A\). It always contains the empty set \(\varnothing\) and \(A\) itself. If \(A\) has \(n\) elements, \(\mathcal{P}(A)\) has \(2^n\) elements, because each element of \(A\) is independently either included or excluded from each subset.

Worked example: let \(A = \{a, b\}\). Then \(\mathcal{P}(A) = \{\varnothing, \{a\}, \{b\}, \{a,b\}\}\), which has \(2^2 = 4\) elements. Note that \(\{a\} \in \mathcal{P}(A)\), but \(a \notin \mathcal{P}(A)\): the elements of the power set are subsets of \(A\), not elements of \(A\).

Typical mistake: confusing \(\varnothing\) with \(\{\varnothing\}\). The first has no elements; the second has exactly one, namely \(\varnothing\). By Cantor’s theorem, \(\mathcal{P}(A)\) always has strictly larger cardinality than \(A\), including when \(A\) is infinite.

Think about it

Why does \(\varnothing\) belong to \(\mathcal{P}(A)\) for every \(A\)?

Because \(\varnothing \subseteq A\) holds for any set \(A\).

Exercises 10

  1. What is \(\mathcal{P}(A)\)?
  2. How many elements does \(\mathcal{P}(\varnothing)\) have?
  3. How many elements does \(\mathcal{P}(\{1,2,3\})\) have?
  4. If \(X \in \mathcal{P}(A)\), what holds?
  5. Is \(\varnothing \in \mathcal{P}(A)\) for every set \(A\)?
  6. Let \(A=\{1,2,3,4\}\). How many elements of \(\mathcal{P}(A)\) have exactly two elements?
  7. What is \(\mathcal{P}(\{a\}) \cap \{a\}\)?
  8. Which statement is true for every set \(A\)?
  9. Let \(A=\{a,b\}\). How many pairs \((X,Y)\) with \(X,Y \in \mathcal{P}(A)\) satisfy \(X \subseteq Y\)?
  10. Let \(|A|=2\). How many subsets does \(\mathcal{P}(A)\) have?

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.