Cardinal number, subsets and the power set

Once we can write sets down, the next ques­tions are how big a set is and how two sets com­pare. Are they the same set? Do they have the same num­ber of ele­ments? Is one of them inside the other? This les­son answers these ques­tions with the ideas of car­di­nal num­ber, equal and equiv­a­lent sets, sub­sets, the power set and the uni­ver­sal set. Along the way we meet a neat count­ing result: a set with $n$ ele­ments has exactly $2^n$ sub­sets.

Car­di­nal num­ber#

The num­ber of dis­tinct ele­ments con­tained in a finite set $A$ is called its car­di­nal num­ber, writ­ten $n(A)$.

For exam­ple, if $A = \{1, 2, 3, 4\}$ then $n(A) = 4$. For the let­ters of "BANANA", the set is $\{B, A, N\}$ and its car­di­nal num­ber is 3: repeated let­ters are counted once. And $n(\phi) = 0$.

Equal sets#

Two sets $A$ and $B$ are said to be equal if every ele­ment of $A$ is an ele­ment of $B$ and every ele­ment of $B$ is an ele­ment of $A$. We write $A = B$.

For exam­ple, $A = \{1, 2, 3\}$ and $B = \{3, 1, 2\}$ are equal: they have exactly the same ele­ments, only listed in a dif­fer­ent order. Sim­i­larly $\{x : x^2 = 4\} = \{-2, 2\}$.

Equiv­a­lent sets#

Two finite sets $A$ and $B$ are equiv­a­lent if $n(A) = n(B)$. This is writ­ten $A \sim B$, read "$A$ is equiv­a­lent to $B$".

For exam­ple, $A = \{1, 2, 3\}$ and $B = \{x, y, z\}$ have no ele­ment in com­mon, but $n(A) = n(B) = 3$, so $A \sim B$.

Equal sets are always equiv­a­lent, but equiv­a­lent sets need not be equal. Equal means "the same ele­ments"; equiv­a­lent means only "the same num­ber of ele­ments".

Sub­set and super­set#

A set $A$ is said to be a sub­set of a set $B$ if every ele­ment of $A$ is also an ele­ment of $B$. In sym­bols we write $A \subseteq B$, read "$A$ is a sub­set of $B$". Here $B$ is called a super­set of $A$.

For exam­ple, let $A = \{1, 2, 3\}$ and $B = \{1, 2, 3, 4, 5\}$. Then:

• $A \subseteq B$, since 1, 2 and 3 are all in $B$.
• $A \subseteq A$: every set is a sub­set of itself.
• $B \not\subseteq A$, since $4 \in B$ but $4 \notin A$.
• $\phi \subseteq A$ and $\phi \subseteq B$: the empty set is a sub­set of every set, because it has no ele­ment that could fail to belong.

Two sets are equal exactly when each is a sub­set of the other: $A = B$ means $A \subseteq B$ and $B \subseteq A$.

The num­ber sets fit inside each other: $N \subseteq W \subseteq Z \subseteq Q \subseteq R$.

All the sub­sets of a set#

Exam­ple 1#

Write all pos­si­ble sub­sets of $A = \{1, 2, 3\}$.

List them by size:

• with no ele­ment: $\phi$
• with one ele­ment: $\{1\}, \{2\}, \{3\}$
• with two ele­ments: $\{1, 2\}, \{1, 3\}, \{2, 3\}$
• with three ele­ments: $\{1, 2, 3\} = A$

That makes $1 + 3 + 3 + 1 = 8$ sub­sets, and $8 = 2^3$, where $3 = n(A)$.

The num­ber of pos­si­ble sub­sets of a set $A$ is $2^{n(A)}$.

The rea­son: to build a sub­set, go through the ele­ments one at a time and decide "in" or "out" for each. There are 2 choices for each of the $n$ ele­ments, so $2 \times 2 \times \cdots \times 2 = 2^n$ sub­sets in all.

Exam­ple 2#

If $n(A) = 4$, how many sub­sets does $A$ have? List them for $A = \{1, 2, 3, 4\}$.

There are $2^4 = 16$ sub­sets: $\phi$; $\{1\}, \{2\}, \{3\}, \{4\}$; $\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}$; $\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}$; and $A$ itself. Count­ing by size: $1 + 4 + 6 + 4 + 1 = 16$.

Proper sub­sets#

A set $A$ is a proper sub­set of $B$ if every ele­ment of $A$ is an ele­ment of $B$, but not every ele­ment of $B$ is an ele­ment of $A$. In other words, $A \subseteq B$ and $A \neq B$. We write $A \subset B$, read "$A$ is a proper sub­set of $B$".

A set $A$ itself is a sub­set of $A$, but it is not a proper sub­set; it is called the improper sub­set of $A$. So all the sub­sets except $A$ itself are proper.

For $A = \{1, 2, 3\}$, the proper sub­sets are $\phi$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1, 2\}$, $\{2, 3\}$, $\{1, 3\}$: seven of them.

The num­ber of pos­si­ble proper sub­sets of a set $A$ is $2^{n(A)} - 1$.

The power set#

The set formed by all the sub­sets of a given set $A$ is called the power set of $A$, writ­ten $P(A)$. Its ele­ments are them­selves sets.

For $A = \{1, 2, 3\}$:

$$P(A) = \{\phi, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, A\}$$

The num­ber of ele­ments in $P(A)$ is $2^{n(A)}$. Notice that $\phi \in P(A)$ and $A \in P(A)$, while $1 \notin P(A)$ (the ele­ment 1 is not a sub­set; the set $\{1\}$ is).

Exam­ple 3#

If $A = \{a, b\}$, write $P(A)$ and find $n(P(A))$ and $n(P(P(A)))$.

$P(A) = \{\phi, \{a\}, \{b\}, \{a, b\}\}$, so $n(P(A)) = 4$. Then $P(A)$ is a set with 4 ele­ments, so $n(P(P(A))) = 2^4 = 16$.

The uni­ver­sal set#

A set con­tain­ing all the ele­ments under con­sid­er­a­tion is known as the uni­ver­sal set, denoted $U$. Which set is uni­ver­sal depends on the prob­lem. When study­ing the dig­its, $U$ might be $\{0, 1, 2, \ldots, 9\}$; when solv­ing equa­tions in whole num­bers, $U = W$; when study­ing real num­bers, $U = R$. Every set in a given prob­lem is a sub­set of $U$.

Exam­ple 4#

Let $U = \{1, 2, 3, \ldots, 10\}$. Write in ros­ter form the sub­sets $A = \{x : x \text{ is prime}\}$ and $B = \{x : x \text{ is a multiple of } 3\}$, and find $n(A)$ and $n(B)$.

$A = \{2, 3, 5, 7\}$ with $n(A) = 4$, and $B = \{3, 6, 9\}$ with $n(B) = 3$. Nei­ther is a sub­set of the other.

Prac­tice#

1. Find $n(A)$ for $A = \{x : x \text{ is a letter of the word "MATHEMATICS"}\}$.
2. Are $\{1, 2, 3, 4\}$ and $\{4, 3, 2, 1\}$ equal? Are $\{1, 2\}$ and $\{p, q\}$ equal or equiv­a­lent?
3. Is $\{x : x^2 = 1\}$ equal to $\{1\}$? Explain.
4. State true or false: (a) $\{2\} \subseteq \{1, 2, 3\}$ (b) $2 \subseteq \{1, 2, 3\}$ (c) $\phi \subseteq \{5\}$ (d) $\{1, 4\} \subset \{1, 2, 3\}$
5. Write all the sub­sets of $\{a, b, c\}$.
6. How many sub­sets and how many proper sub­sets does a set with 5 ele­ments have?
7. Write the power set of $\{0, 1\}$.
8. A set has 64 sub­sets. How many ele­ments does it have?
9. If $n(A) = 3$, find $n(P(P(A)))$.
10. Arrange $N$, $Z$, $W$, $R$, $Q$ so that each is a sub­set of the next.

Answers#