# 3.1.5: Sets of sets

Sets can contain other sets as elements. For example, the notation {a, {b}} defines a set that contains two elements, the entity a and the set {b}. Since the set {b} is a member of the set $$\{a,\{b\}\},$$ we have that $$\{b\} \in\{a,\{b\}\} .$$ On the other hand, provided that $$a \neq b$$ the statement $$\{b\} \subseteq\{a,\{b\}\}$$ is false, since saying $$\{b\} \subseteq\{a,\{b\}\}$$ is equivalent to saying that $$b \in\{a,\{b\}\},$$ and the entity $$b$$ is not one of the two members of $$\{a,\{b\}\} .$$ For the entity $$a,$$ it is true that $$\{a\} \subseteq\{a,\{b\}\}$$ and for the set $$\{b\},$$ it is true that $$\{\{b\}\} \subseteq\{a,\{b\}\}$$ Study these examples carefully before you continue, as many students struggle with the notion and notation of putting sets in sets.

Given a set A, we can construct the set that contains all the subsets of A. This set is called the power set of $$A,$$ and is denoted $$\mathscr{P}(A) .$$ Formally, we define

$$\mathcal{P}(A)=\{X | X \subseteq A\}$$

For example, if A = {a, b}, then the subsets of A are the empty set, {a}, {b}, and {a, b}, so the power set of A is set given by

P(A) = {∅, {a}, {b}, {a,b}}.
So the power set of of A has four elements. Does this surprise you?

Note that since the empty set is a subset of any set, the empty set is an element of the power set of any set. That is, for any set A, ∅ ⊆ A and ∅ ∈ P(A). Since the empty set is a subset of itself, and is its only subset, we have that P(∅) = {∅}. The set {∅} is not empty. It contains one element, namely ∅.

The Nobel Prize was won by Bertrand Russell (1872– 1970), a dominant figure in British thought during the twentieth century. Russell was a philosopher and mathematician, and also a historian, social critic and political activist. With A. N. Whitehead, Russell wrote Principia Mathematica, an epic attempt to create a lo- gical basis for mathematics. His work has had a consid- erable influence on computer science, and not just for his contributions to logic and set theory: he proposed the beginnings of what are now type systems.

Source: en.Wikipedia.org/wiki/Bertrand_Russell.

We remarked earlier in this section that the notation {x | P(x)} is only valid if the domain of discourse of P is a set. This might seem a rather puzzling thing to say—after all, why and how would the domain of discourse be anything else? The answer is related to Russell’s Paradox, which we mentioned briefly in Chapter 3 and which shows that it is logically impossible for the set of all sets to exist. This impossibility can be demonstrated using a proof by contradiction. In the proof, we use the existence of the set of all sets to define another set which cannot exist because its existence would lead to a logical contradiction.

Theorem 4.2.

There is no set of all sets.

Proof. Suppose that the set of all sets exists. We will show that this assumption leads to a contradiction. Let V be the set of all sets. We can then define the set R to be the set which contains every set that does not contain itself. That is,

$$R=\{X \in V | X \notin X\}$$

Now, we must have either R R or R . We will show that either case leads to a contradiction.

Consider the case where R R. Since R R, R must satisfy the condition for membership in $$R .$$ A set $$X$$ is in $$R$$ iff $$X \notin X .$$ To say that $$R$$ satisfies this condition means that $$R \notin R .$$ That is, from the fact that $$R \in R,$$ we deduce the contradiction that $$R \notin R$$.

Now consider the remaining case, where $$R \notin R .$$ since $$R \notin R, R$$ does not satisfy the condition for membership in $$R .$$ since the condition for membership is that $$R \notin R$$ and this condition is false, the statement $$R \notin R$$ must be false. But this means that the statement R R is true. From the fact that R , we deduce the contradiction that R R.

Since both possible cases, $$R \in R$$ and $$R \notin R,$$ lead to contradictions, we see that it is not possible for R to exist. Since the existence of R follows from the existence of V, we see that V also cannot exist.

This (in)famous contradiction has been adapted to natural language to make it easier to convey the problem to laymen. Unfortunately many of these translations are flawed. Can you think of a solution for the following for instance?

“The barber of Seville shaves all men who do not shave themselves. Who shaves the barber?”

To avoid Russell’s paradox, we must put limitations on the construction of new sets. We can’t force the set of all sets into existence simply by thinking of it. We can’t form the set {x | P(x)} unless the domain of discourse of P is a set. Any predicate Q can be used to form a set {x X | Q(x)}, but this notation requires a pre-existing set X. Predicates can be used to form subsets of existing sets, but they can’t be used to form new sets completely from scratch.

The notation {x A | P(x)} is a convenient way to effectively limit the domain of discourse of a predicate, P, to members of a set, A, that we are actually interested in. We will use a similar notation with the quantifiers ∀ and ∃. The proposition (∀x A)(P(x))is true if and only if P(a) is true for every element a of the set A. And the proposition(∃x A)(P(x)) is true if and only if there is some element a of the set A for which P(a)is true. These notations are valid only when A is contained in the domain of discourse for P. As usual, we can leave out parentheses when doing so introduces no ambiguity. So, for example, we might write ∀x A P(x).