EF Sets of sets

Skip to main content

Section 9.7 Sets of sets

Note 9.7.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 9.7.2.

Consider

\begin{aligned} T & = {3 n | n \in N}, & X & = {A \subset N | A \cap T = \emptyset}, & Y & = X \cup T . \end{aligned}

Elements of

T

are numbers. Elements of

X

are subsets of

N

— that is,

X

is a set of subsets of

N,

but is not itself a subset of

N .

Elements of

Y

are either from

X

or from

T,

so some elements of

Y

are numbers, and some elements of

Y

are sets of numbers.

power set: 🔗
given a set $A,$ the power set of $A$ is the set ${B \subseteq A}$ of all subsets of $A$
$P (A)$: 🔗
the power set of the set $A$

Warning 9.7.3.

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

Fact 9.7.4. A power set is never empty.

For every set

A,

P (A) \neq \emptyset .

Proof.

Both

\emptyset

and

A

are subsets of

A,

so both are elements of

P (A) .

Even if

A = \emptyset,

we still have

P (\emptyset) = {\emptyset} \neq \emptyset .

Example 9.7.5. Power set of a “small” set.

For

A = {a, b, c},

we have

P (A) = {\emptyset, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} .

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 9.7.6. A set of sets as a subset of a power set.

For

X

as in Example 9.7.2, we have

X \subseteq P (N) .

Warning 9.7.7.

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

Example 9.7.8.

Let

R = {any set X | X is not an element of itself.} .

First note that there exist sets which satisfy the condition for membership in

R;

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,

which contradicts the case assumption.

Case $R \notin R$ .

Then

R \in R,

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 9.7.9.

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

N \cup P (N)

would not be allowed, as

N

is a set of numbers while

P (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 ?

” 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.

<Prev ^Top Next>