9.7: Sets of sets

Note \(\PageIndex{1}\)

Sets can be made up of any kind of objects, even other sets! (But now we must be careful of the use of the phrase “contained in”.)

Example \(\PageIndex{1}\)

Consider

\begin{align*} \mathscr{T} & = \{3n \vert n\in\mathbb{N}\} \text{,} & X & = \{A\subset \mathbb{N} \vert A \cap \mathscr{T} = \varnothing\} \text{,} & Y & = X \cup \mathscr{T} \text{.} \end{align*}

Elements of \(\mathscr{T}\) are numbers. Elements of \(X\) are subsets of \(\mathbb{N}\) — that is, \(X\) is a set of subsets of \(\mathbb{N}\text{,}\) but is not itself a subset of \(\mathbb{N}\text{.}\) Elements of \(Y\) are either from \(X\) or from \(\mathscr{T}\text{,}\) so some elements of \(Y\) are numbers, and some elements of \(Y\) are sets of numbers.

Definition: power set

given a set \(A\text{,}\) the power set of \(A\) is the set \(\{ B \subseteq A \}\) of all subsets of \(A\)

Definition: \(\mathscr{P}(A)\)

the power set of the set \(A\)

Warning \(\PageIndex{1}\)

The elements of a power set are subsets of the set in question.

Fact \(\PageIndex{1}\): A power set is never empty.

For every set \(A\text{,}\) \(\mathscr{P}(A) \ne \emptyset\text{.}\)

Proof

Both \(\emptyset\) and \(A\) are subsets of \(A\text{,}\) so both are elements of \(\mathscr{P}(A)\text{.}\) Even if \(A = \emptyset\text{,}\) we still have

\begin{equation*} \mathbb{P}{\emptyset} = \{\emptyset\} \ne \emptyset \text{.} \end{equation*}

Example \(\PageIndex{2}\): Power set of a “small” set.

For \(A = \{a,b,c\}\text{,}\) we have

\begin{equation*} \mathscr{P}(A) = \left\{ \; \emptyset, \; \{a\}, \; \{b\}, \; \{c\},\; \{a,b\},\; \{a,c\},\; \{b,c\},\; \{a,b,c\} \; \right\}\text{.} \end{equation*}
Note the use of curly braces here. In particular, note that \(\emptyset\) has not been placed in its own set of curly braces because it is already a set itself.

Example \(\PageIndex{3}\): A set of sets as a subset of a power set.

For \(X\) as in Example \(\PageIndex{1}\), we have \(X \subseteq \mathscr{P}{\mathbb{N}}\text{.}\)

Warning \(\PageIndex{2}\)

We are not completely free to define sets any way we want.

Example \(\PageIndex{4}\)

Let

\begin{equation*} R = \{ \text{any set } X \vert X \text{ is not an element of itself.} \}\text{.} \end{equation*}

First note that there exist sets which satisfy the condition for membership in \(R\text{;}\) for example, the empty set. So \(R\) should not be not empty. If \(R\) is a set, then it is a “candidate” for membership in itself! Break into cases.

Case \(R \in R\).
Then \(R\notin R\text{,}\) which contradicts the case assumption.

Case \(R \notin R\).
Then \(R\in R\text{,}\) which contradicts the case assumption.

Since all cases lead to a contradiction, \(R\) is cannot be a set! This is called Russell's Paradox, and is one of the reasons we rely upon “naive set theory” in this course.

Remark \(\PageIndex{1}\)

One of the ways to avoid Russell's Paradox is by requiring every object, including sets, to have a type, similar to how variables in a computer language can be declared to have a type. In such a scheme, a set is never just a set — it is always a set of a certain kind of object. Then an operation such as \(\mathbb{N} \cup \mathscr{P}{\mathbb{N}}\) would not be allowed, as \(\mathbb{N}\) is a set of numbers while \(\mathscr{P}(\mathbb{N})\) is a set of sets of numbers, and we have a type mismatch. And, more importantly, asking a question like “Is \(R \in R\text{?}\)” becomes nonsensical, as on the left of the \({} \in {}\) symbol \(R\) is required to be some type of object while on the right \(R\) is required to be a set of that type of object, and again we have a type mismatch.