Back to the on-screen lesson ·
The set of all subsets and the set of all ordered pairs, the two counts they carry, and what one element of each actually looks like.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to list a power set, count it as two-to-the-n by matching subsets with sequences of in-or-out decisions, count a Cartesian product as a product of sizes, and say what a single element of each construction looks like. You will also be able to compose the two counts — a relation is a subset of a product — and say why counting relations is hopeless and classifying them is not.
Lesson 11 treated a set's elements as the things you argue about. This lesson builds sets whose elements are themselves sets, or pairs, and the only difficulty in it is keeping straight which level you are on. The counts themselves are the product rule, which you have used since school.
The power set $\mathcal{P}(A)$ is the set of all subsets of $A$, including $\varnothing$ and $A$. The Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$; $A^2$ means $A \times A$. An ordered pair is not a two-element set: $(1, 2)$ and $(2, 1)$ differ, and $(1, 1)$ exists while $\{1, 1\}$ is just $\{1\}$.
The power set. To build a subset of $A$, walk along its elements and answer one question for each: in, or out? Every subset corresponds to exactly one sequence of answers, and every sequence of answers to exactly one subset. So $$|\mathcal{P}(A)| = 2^{|A|}.$$ The argument is a bijection — a matching between subsets and answer sequences — and that is the form most counting arguments in unit 4 will take: rather than count the things, match them with things you have already counted.
$\mathcal{P}(\{1,2\})$ is $\{\varnothing, \{1\}, \{2\}, \{1,2\}\}$: four elements, each of them a set. Note that $\varnothing$ and $A$ are both in there. Leaving them out is the standard error and gives $2^n - 2$.
The product. To build a pair, choose a first coordinate and then a second, independently, so $$|A \times B| = |A| \, |B|.$$ Products are how a structure with two components gets written down: a point of the plane is an element of $\mathbb{R} \times \mathbb{R}$, and a relation on $A$ — the whole subject of the next lesson — is a subset of $A \times A$.
Composing the two counts gives a number worth seeing once: the relations on a set of $n$ elements number $2^{n^2}$, which is $512$ for $n = 3$ and over thirty million for $n = 5$. Counting relations is hopeless; classifying them is the only way forward, and that is what lesson 13 does.
Another way: steps
To count a set built from another:
Another way: picture
A row of $n$ switches, one per element, each up or down. Every setting of the switches is a subset, and every subset is a setting: two positions, $n$ switches, $2^n$ settings. The empty set is all switches down and the whole set is all switches up, which is why neither can be left out of the count.
The power set count treats all sizes together. Splitting it by size gives the binomial coefficients of unit 4:
| $n$ | size $0$ | $1$ | $2$ | $3$ | $4$ | total |
|---|---|---|---|---|---|---|
| $2$ | $1$ | $2$ | $1$ | $4$ | ||
| $3$ | $1$ | $3$ | $3$ | $1$ | $8$ | |
| $4$ | $1$ | $4$ | $6$ | $4$ | $1$ | $16$ |
Each row adds to $2^n$, which is not a coincidence: the rows are the same count sorted two different ways, and counting one set two ways is a proof technique in its own right. Unit 4 will use it to establish identities that are painful to prove algebraically and immediate once you say what is being counted.
Leaving out $\varnothing$ and $A$. They are subsets. The count is $2^n$, not $2^n - 2$.
Confusing $a$ with $\{a\}$. $1 \in \{1, 2\}$ but $\{1\} \in \mathcal{P}(\{1,2\})$, and $1 \in \mathcal{P}(\{1,2\})$ is false.
Treating a pair as a two-element set. $(1, 2) \ne (2, 1)$, and $(1, 1)$ is a perfectly good pair.
Adding when the choices are independent. Two sets of sizes $3$ and $4$ give $12$ pairs and $7$ elements in the union; those are different questions, and which one is being asked is decided by whether an object needs one choice or two.
$\mathcal{P}(A)$ is not a bigger version of $A$ and does not contain any element of $A$. If $A = \{1, 2\}$ then $1 \notin \mathcal{P}(A)$, because the things in $\mathcal{P}(A)$ are sets and $1$ is not one. The habit that fixes this for good is to write down one element of every set you meet: for $\mathcal{P}(A)$ that is $\{1\}$, with braces, and the braces are the whole difference.
$A = \{a, b, c\}$. By size: one empty set; three of size one; three of size two; one of size three.
Sorted by size.
That is $1 + 3 + 3 + 1 = 8$. By switches: three elements, two positions each, $2^3 = 8$.
The same count, two ways.
The agreement is not luck — the two counts are of the same set — and an identity proved by counting one set two ways is proved as firmly as by algebra.
A proof technique, met here in its smallest case.
How many relations are there on a set of three elements? A relation is a set of ordered pairs, so first count the pairs.
Say what one element of the answer is.
$A \times A$ has $3 \times 3 = 9$ pairs.
The product count.
A relation is a subset of those nine, so there are $2^9 = 512$ of them. Each construction was easy; the size comes from putting one inside the other.
Compose the counts, do not add them.
Work from the inside out. $A \times B$ has $2 \times 3 = 6$ pairs.
Count the product first.
The power set of a six-element set has $2^6 = 64$ elements.
Then the subsets of that.
So the answer is $64$, and one of those $64$ elements is a set of ordered pairs — for instance $\{(a_1, b_1), (a_2, b_3)\}$, which is exactly what a relation from $A$ to $B$ is. Writing down one element is what makes the answer mean something.
A set $A$ has $2$ elements. Fill in the two counts.
| How many | |
|---|---|
| Elements of $A$ | 2 |
| Subsets of $A$ | |
| Ordered pairs in $A \times A$ |
A set $A$ has $3$ elements. How many subsets does it have?
Answer:
$|A| = 2$ and $|B| = 4$. How many ordered pairs are there in $A \times B$?
Answer:
Let $A = \{1, 2\}$. Match each set to what one of its elements looks like.
| A number, such as $1$ | A subset of $A$, such as $\{1\}$ | An ordered pair, such as $(1, 2)$ | A set of subsets, such as $\{\{1\}, \varnothing\}$ | |
|---|---|---|---|---|
| $A$ | ||||
| $\mathcal{P}(A)$ | ||||
| $A \times A$ | ||||
| $\mathcal{P}(\mathcal{P}(A))$ |
A set has $6$ elements. Fill in the two counts.
Subsets with exactly one element: one. Subsets altogether: all.
A relation on $A$ is any set of ordered pairs from $A$. If $|A| = 3$, how many relations are there on $A$?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A set $A$ has $2$ elements. Fill in the two counts.
| How many | |
|---|---|
| Elements of $A$ | 2 |
| Subsets of $A$ | |
| Ordered pairs in $A \times A$ |
You can count subsets and pairs, and say what one element of a power set or a product is. Say in your own words why the power set of an n-element set has two-to-the-n elements, and why the empty set and the whole set are both in it. Next: the relations themselves, and the three properties that sort them into kinds.
10. Your turn: how many elements has $\mathcal{P}(A \times B)$ when $|A| = 2$ and $|B| = 3$?, step 3