Every object you'll meet in abstract algebra (groups, rings, fields, all of it) is a set with some extra structure bolted on. So before we can do anything fancy, we need to be fluent in the language of sets. Most of this will feel familiar, but pay close attention to the notation: in a proof-based course, the symbols carry the argument, and a single misplaced brace can turn a true statement into a false one.
Here's the definition everything else is built on.
A set is an unordered collection of distinct objects (members or elements of the set).
Two words in there do a lot of work. Unordered means $\{1, 5, 13\}$ and $\{13, 1, 5\}$ are the same set. Distinct means repeats don't count twice: $\{1, 2, 2, 3\}$ is just $\{1, 2, 3\}$. Elements can be anything at all: numbers, letters, symbols, even other sets.
Watch both words at work: pour a list into a bag, shake it, and squash the repeats.
So a set only cares about which objects are in it. Here are a few sets, from tame to strange.
Each of these is a set:
Look closely at that last one: those are six different triangles (different sizes, colors, and directions), so it really does have six elements. If they were six copies of the very same triangle, the set would just be $\{\triangle\}$.
A few sets show up so often that they get their own symbols.
One warning about that first line, because it trips people up when they switch textbooks.
Not everyone agrees on whether $0 \in \mathbb{N}$. In this course, $\mathbb{N}$ starts at $1$. When you read other books, check their convention on page one. You'll also see ℤ⁺ for the natural numbers and { } for the empty set; this site always writes $\mathbb{N}$ and $\emptyset$.
We need a way to say "this thing is in that set."
If $A$ is a set, then:
Try it on the sets we just named.
Which of these are true: $3 \in \mathbb{N}$, $0 \in \mathbb{N}$, $-2 \in \mathbb{Z}$, $\frac{1}{2} \in \mathbb{Z}$?
And we need a way to measure how big a set is.
The cardinality of a finite set $A$ is the number of elements in $A$.
We write it $|A|$, with bars like an absolute value.
Find the cardinality of $\{1, 5, 13\}$, the six-triangle set above, and $\emptyset$.
If $A$ is not finite, then we write $|A| = \infty$. So $|\mathbb{N}| = |\mathbb{Z}| = \infty$.
The bars aren't the only notation out there, so here's a heads-up for when you read other books.
Other books also write #A or card(A) for the cardinality. They mean exactly the same thing as $|A|$, which is what this site always uses.
Before the exercise, sort some rosters: which ones are secretly the same set?
Now one on paper.
Is $\{1, 2, 2, 3\} = \{3, 2, 1\}$? What is $|\{1, 2, 2, 3\}|$?
Yes, they're equal. Order doesn't matter, and the repeated $2$ is the same element listed twice, so both sets have exactly the elements $1$, $2$, and $3$. That makes $|\{1, 2, 2, 3\}| = 3$, not $4$.
The first way is the obvious one: just list everything.
List out the elements of a set between curly braces.
All of the examples so far were written this way. It gets trickier when the elements are themselves sets, and this is where you have to slow down and count braces.
A set inside a set inside a set... how deep does this go? (All the way down: you can build every whole number this way. $0 = \emptyset$, $1 = \{\emptyset\}$, $2 = \{\emptyset, \{\emptyset\}\}$, ...)
List the elements and find the cardinality of $A = \{1, \{1\}\}$ and of $A = \{\emptyset, 2, \{a, b\}, \{1, \{1\}\}\}$.
$A = \{1, \{1\}\}$ has elements $1$ and $\{1\}$, so $|A| = 2$. The number $1$ and the set $\{1\}$ are different objects: one is a number, the other is a box with a number in it.
$A = \{\emptyset, 2, \{a, b\}, \{1, \{1\}\}\}$ has elements $\emptyset$, $2$, $\{a, b\}$, and $\{1, \{1\}\}$, so $|A| = 4$. The set $\{a, b\}$ counts as one element of $A$, no matter how much is inside it.
The trick is to picture every pair of braces as a box. The elements of $A$ are exactly the things sitting directly inside the outermost box. Try it below, then test yourself on statements that trip up almost everyone.
Every pair of braces is a box.
The second way of describing sets is by a rule instead of a list. This is the only option for most infinite sets.
Specify a collection of elements which satisfy certain conditions:
$$\{ \text{elements} : \text{conditions} \}$$
Read the colon as "such that." So $\{n \in \mathbb{Z} : n \ge 0\}$ is "the set of integers $n$ such that $n \ge 0$."
Some books use a vertical bar instead of the colon, as in { n ∈ ℤ | n ≥ 0 }. It means the same thing. This site always uses the colon.
To read a set written this way, test every candidate against the condition and keep the ones that pass. Watch it happen:
Here are some important sets written in set-builder notation.
Some important sets in set-builder notation:
Notice that $\mathbb{Q}$ is built out of $\mathbb{Z}$ and $\mathbb{N}$, and the irrationals are built out of $\mathbb{R}$ and $\mathbb{Q}$. Set-builder notation lets you define new sets from ones you already have.
The small print in a set-builder rule ($\mathbb{N}$ or $\mathbb{Z}$, $<$ or $\le$) changes the set. Match each rule to the set it builds.
Now write a couple out yourself.
Remember even integers written as $2k$? In set-builder notation, the even integers are $\{2k : k \in \mathbb{Z}\}$.
Write each set in roster notation: (a) $\{n \in \mathbb{Z} : n^2 < 10\}$, and (b) $\{x \in \mathbb{R} : x^2 = -1\}$.
(a) The integers whose squares are less than $10$ are $-3, -2, -1, 0, 1, 2, 3$ (since $4^2 = 16$ is too big). So the set is $\{-3, -2, -1, 0, 1, 2, 3\}$.
(b) No real number squares to a negative number, so nothing satisfies the condition: the set is $\emptyset$.
Now we compare two sets.
If $A$ and $B$ are sets, then we say that $A$ is a subset of $B$ if every element of $A$ is also an element of $B$.
We write it like this:
Sometimes we want to rule out the case where the two sets are the same.
If $A \subseteq B$ and $A \neq B$, then we say that $A$ is a proper subset of $B$.
We write $A \subsetneq B$ for "$A$ is a proper subset of $B$." The slash under the symbol is the "$\neq$" part.
Let $A = \{1, 2, 3\}$. Which of $\{1\}$, $\{1, 3\}$, $\{1, 2, 3\}$, and $\emptyset$ are proper subsets of $A$?
$\{1\} \subsetneq A$, $\{1, 3\} \subsetneq A$, and $\emptyset \subsetneq A$: each is a subset of $A$ and is missing something. But $\{1, 2, 3\} = A$, so $\{1, 2, 3\} \subseteq A$ is true while $\{1, 2, 3\} \subsetneq A$ is false.
The next fact is the single most useful tool for proving that two sets are equal. You'll use it constantly, including later on this page.
Two sets are equal if and only if they have exactly the same elements. Equivalently,
$$A = B \quad\text{if and only if}\quad A \subseteq B \text{ and } B \subseteq A.$$
Here's the subset definition at work on the number systems you already know.
How do $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$ compare?
To show $A \not\subseteq B$, one counterexample is enough: a single element of $A$ that isn't in $B$.
Two subsets come for free with every set.
The empty set is a subset of every set. Every single one. It's everywhere. It's watching you.
For any set $A$, we have that $\emptyset \subseteq A$ and $A \subseteq A$.
$A \subseteq A$: every element of $A$ is an element of $A$.
$\emptyset \subseteq A$: to fail, $\emptyset$ would need an element that isn't in $A$. But $\emptyset$ has no elements at all, so there's nothing that could fail. $\blacksquare$
The second half of that proof is what logicians call "vacuously true": a claim about every element of $\emptyset$ holds automatically, because there are no elements to check.
Now for the distinction that causes more mistakes than anything else in this lecture: $\in$ versus $\subseteq$.
Let $A = \{1, \{2\}\}$. Compare $1$ and $\{1\}$, then $\{2\}$ and $\{\{2\}\}$. Then list every subset of $A$.
An element goes on the left of $\in$. A set of elements goes on the left of $\subseteq$. Wrapping something in braces turns "it's an element" into "the set containing it is a subset."
List of all subsets of $A$:
$$\emptyset, \{1\}, \{\{2\}\}, \{1, \{2\}\} = A$$
The trap runs the other way too.
Before writing $x \in A$ or $X \subseteq A$, ask yourself: "Is the thing on the left one of the things listed in $A$, or a collection of them?" Here $\{2\} \subseteq A$ is false, because the only element of $\{2\}$ is $2$, and $2 \notin A$.
Try it with your hands: build a set $S$ out of the things inside $A$ and watch the checks change.
Now predict before you check. Sometimes both statements are true, and sometimes neither is.
Ready for the trickiest set on the page?
Let $A = \{\emptyset, \{\emptyset\}\}$. Which of these are true? (a) $\emptyset \in A$ (b) $\emptyset \subseteq A$ (c) $\{\emptyset\} \in A$ (d) $\{\emptyset\} \subseteq A$ (e) $\{\{\emptyset\}\} \subseteq A$
All five are true.
This set is a great stress test: the same symbols are both elements and subsets.
One more, this time counting.
List every subset of $\{a, b, c\}$. Which of them are proper subsets?
There are eight: $\emptyset$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a, b\}$, $\{a, c\}$, $\{b, c\}$, $\{a, b, c\}$.
Every one except $\{a, b, c\}$ itself is a proper subset, so there are seven proper subsets. (Keep the count of $8 = 2^3$ in mind; it comes back at the end of the page.)
Just like numbers can be added and multiplied, sets can be combined to make new sets. Suppose $A$ and $B$ are two sets.
The union of $A$ and $B$ is the set $A \cup B = \{x : x \in A \text{ or } x \in B\}$.
Where the union keeps anything in either set, the intersection keeps only what the two sets share.
The intersection of $A$ and $B$ is the set $A \cap B = \{x : x \in A \text{ and } x \in B\}$.
The "or" in the union is the inclusive mathematician's "or": an element in both sets is definitely in the union.
If $A = \{a, f, i\}$ and $B = \{a, b, f, g\}$, find $A \cup B$ and $A \cap B$.
$A \cup B = \{a, b, f, g, i\}$ and $A \cap B = \{a, f\}$.
These same two sets, along with every operation on this page, live in the diagram below. Each operation lights up a region of the diagram. The missions ask you to work backward: given a set, which operation builds it?
Union and intersection follow rules that look a lot like the rules for addition and multiplication.
Commutative properties:
$$A \cup B = B \cup A \qquad A \cap B = B \cap A$$
Associative properties:
$$(A \cup B) \cup C = A \cup (B \cup C) \qquad (A \cap B) \cap C = A \cap (B \cap C)$$
Distributive properties:
$$(A \cup B) \cap C = (A \cap C) \cup (B \cap C) \qquad (A \cap B) \cup C = (A \cup C) \cap (B \cup C)$$
Here's one place where sets beat numbers: both operations distribute over each other. With numbers, $a \cdot (b + c) = ab + ac$, but $a + bc \neq (a + b)(a + c)$ in general.
See for yourself: shade the sets below, and watch two different expressions land on the same picture.
Here are both distributive laws, built step by step on two diagrams side by side.
A picture isn't a proof, though. Now prove the first one.
Prove the first distributive property: $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$.
Proof. We show each side is a subset of the other.
($\subseteq$) Let $x \in (A \cup B) \cap C$. Then $x \in C$, and $x \in A$ or $x \in B$. If $x \in A$, then $x \in A \cap C$. If $x \in B$, then $x \in B \cap C$. Either way, $x \in (A \cap C) \cup (B \cap C)$.
($\supseteq$) Let $x \in (A \cap C) \cup (B \cap C)$. Then $x \in A \cap C$ or $x \in B \cap C$. In both cases $x \in C$, and $x$ is in $A$ or in $B$, so $x \in A \cup B$. Therefore $x \in (A \cup B) \cap C$.
By set equality, the two sets are equal. $\blacksquare$
Why stop at two sets? We can take the union or intersection of as many sets as we like, even infinitely many. To keep track of them, we label them with an index.
Suppose that $I$ is some indexing set and that, for each $i \in I$, $A_i$ is a set. Write $\{A_i\}_{i \in I} = \{A_i : i \in I\}$.
So $x$ is in the big union if it's in at least one of the sets, and in the big intersection if it's in every single one.
Let $I = \mathbb{N}$, $A_1 = \{0, 1\}$, $A_2 = \{0, 1, 2\}$, $A_3 = \{0, 1, 2, 3\}$, and so on. That is, $\forall\, i \in I$, $A_i = \{0, 1, \dots, i\}$. Find the union and the intersection.
$$\bigcup_{i \in I} A_i = \{0, 1, 2, \dots\} = \mathbb{Z}_{\ge 0} \qquad \bigcap_{i \in I} A_i = \{0, 1\}$$
The sets keep growing, so their union gathers up every non-negative integer. The intersection only keeps what all of them share, and the smallest one, $A_1$, limits that to $\{0, 1\}$.
Slide through this family (and a few others) one set at a time, and watch the union and the intersection settle down.
Those answers are believable, but in this course "believable" isn't enough. Here are the proofs. Both use the set equality fact: show each side is a subset of the other.
Proof that $\bigcup_{i \in I} A_i = \mathbb{Z}_{\ge 0}$:
First, suppose that $n \in \mathbb{Z}_{\ge 0}$. If $n \ge 1$, then $n \in A_n$; and if $n = 0$, then $n \in A_1$. Either way, $n \in \bigcup_{i \in I} A_i$. This shows that $\mathbb{Z}_{\ge 0} \subseteq \bigcup_{i \in I} A_i$.
On the other hand, suppose that $m \in \bigcup_{i \in I} A_i$. Then there is some $i \in I$ such that $m \in A_i$. Since $A_i \subseteq \mathbb{Z}_{\ge 0}$, we have $m \in \mathbb{Z}_{\ge 0}$. Therefore $\bigcup_{i \in I} A_i \subseteq \mathbb{Z}_{\ge 0}$.
Conclusion: $\bigcup_{i \in I} A_i = \mathbb{Z}_{\ge 0}$. $\blacksquare$
The intersection proof follows the same two-step pattern, and it's even shorter.
Proof that $\bigcap_{i \in I} A_i = \{0, 1\}$:
If $n \in \{0, 1\}$ then $n \in A_i$, $\forall\, i \in I$. Therefore $n \in \bigcap_{i \in I} A_i$. So $\{0, 1\} \subseteq \bigcap_{i \in I} A_i$.
If $m \in \bigcap_{i \in I} A_i$ then $m \in A_1 = \{0, 1\}$. So $\bigcap_{i \in I} A_i \subseteq \{0, 1\}$.
Conclusion: $\bigcap_{i \in I} A_i = \{0, 1\}$. $\blacksquare$
Here's the union proof again, acted out one element at a time.
Both proofs had the same two-step shape, and that shape is worth remembering.
Notice the shape of both proofs: "Let $x$ be in the left side... therefore $x$ is in the right side," and then the same in reverse. This double-inclusion pattern is how you'll prove almost every set equality in this course. When in doubt, start by writing "Let $x \in$ ..."
Now try one yourself.
For each $i \in \mathbb{N}$, let $B_i = \{-i, -i + 1, \dots, i - 1, i\}$. Find $\bigcup_{i \in \mathbb{N}} B_i$ and $\bigcap_{i \in \mathbb{N}} B_i$.
$\bigcup_{i \in \mathbb{N}} B_i = \mathbb{Z}$ and $\bigcap_{i \in \mathbb{N}} B_i = \{-1, 0, 1\}$.
For the union: every integer $n$ lies in $B_{|n|}$ (or in $B_1$ if $n = 0$), and every $B_i$ is a subset of $\mathbb{Z}$. For the intersection: $-1, 0, 1$ lie in every $B_i$, and anything in all of them must lie in $B_1 = \{-1, 0, 1\}$.
Sometimes two sets have nothing in common at all.
We say that $A$ and $B$ are disjoint if $A \cap B = \emptyset$.
For a whole collection, we want every pair to be disjoint.
We say that a collection of sets $\{A_i\}_{i \in I}$ is pairwise disjoint if $A_i \cap A_j = \emptyset$ for all $i, j \in I$ with $i \neq j$.
Here's what the two definitions look like on small sets.
Are $\{1, 2\}$ and $\{3\}$ disjoint? Is the collection $\{1, 2\}$, $\{2, 3\}$, $\{1, 3\}$ pairwise disjoint? What about $\{A_i\}_{i \in \mathbb{N}}$ with $A_i = \{2i - 1, 2i\}$?
So be careful: "pairwise disjoint" is stronger than "the whole intersection is empty." Build each kind yourself.
Next, we can remove the elements of one set from another.
Why is set difference written with a backslash? Was the minus sign too easy to read?
The set difference of $A$ minus $B$ is $A \setminus B = \{x \in A : x \notin B\}$.
Think of it as "start with $A$, then throw out anything that's also in $B$."
Some books write A − B (with a minus sign) for $A \setminus B$. It means the same thing. This site always uses the backslash.
Back to the sets from the union example.
If $A = \{a, f, i\}$ and $B = \{a, b, f, g\}$, find $A \setminus B$ and $B \setminus A$.
$A \setminus B = \{i\}$ and $B \setminus A = \{b, g\}$.
So set difference is not commutative: it is not true, for general sets $A$ and $B$, that $A \setminus B = B \setminus A$. That raises a natural question.
When exactly is $A \setminus B = B \setminus A$? Prove your answer.
Claim: $A \setminus B = B \setminus A$ if and only if $A = B$.
Proof. If $A = B$, then $A \setminus B = \emptyset = B \setminus A$.
Conversely, suppose $A \setminus B = B \setminus A$. If there were some $x \in A \setminus B$, then $x \notin B$; but also $x \in B \setminus A$, so $x \in B$, a contradiction. So $A \setminus B = \emptyset$, which means every element of $A$ is in $B$: $A \subseteq B$. The same argument with $A$ and $B$ swapped gives $B \subseteq A$. By set equality, $A = B$. $\blacksquare$
If we glue the two differences together, the order stops mattering.
The symmetric difference of $A$ and $B$ is $A \triangle B = (A \setminus B) \cup (B \setminus A)$.
Back to our running example:
If $A = \{a, f, i\}$ and $B = \{a, b, f, g\}$, find $A \triangle B$.
$A \setminus B = \{i\}$ and $B \setminus A = \{b, g\}$, so $A \triangle B = \{b, g, i\}$.
Note: for any sets $A$ and $B$, $A \triangle B = B \triangle A$. The symmetric difference is "everything in exactly one of the two sets."
That description suggests a second formula for the symmetric difference. Prove it.
Prove that $A \triangle B = (A \cup B) \setminus (A \cap B)$.
Proof. ($\subseteq$) Let $x \in A \triangle B$. Then $x \in A \setminus B$ or $x \in B \setminus A$. In the first case $x \in A$ (so $x \in A \cup B$) and $x \notin B$ (so $x \notin A \cap B$). The second case is the same with $A$ and $B$ swapped. Either way, $x \in (A \cup B) \setminus (A \cap B)$.
($\supseteq$) Let $x \in (A \cup B) \setminus (A \cap B)$. Then $x$ is in $A$ or in $B$, but not in both. If $x \in A$, then $x \notin B$, so $x \in A \setminus B$. If $x \in B$, then $x \notin A$, so $x \in B \setminus A$. Either way, $x \in A \triangle B$. $\blacksquare$
Finally, when everything lives inside one big set $X$, we can talk about everything that is not in $A$.
If $A \subseteq X$ then the complement of $A$ in $X$ is $A^c = X \setminus A = \{x \in X : x \notin A\}$.
Two things to notice. First, $A^c$ depends on $X$: the same set has different complements in different universes. Second, for any $A \subseteq X$, $(A^c)^c = A$. Here's a small universe first.
Let $X = \{1, 2, \dots, 8\}$ and $A = \{2, 4, 6, 8\}$. Find $A^c$ and $(A^c)^c$.
$A^c = X \setminus A = \{1, 3, 5, 7\}$. Taking the complement again throws those out of $X$, which leaves $\{2, 4, 6, 8\}$. So $(A^c)^c = A$.
With infinite sets it works the same way, and the choice of $X$ matters even more.
Find the complement of $A = \mathbb{N}$ in $X = \mathbb{Z}$, and in $X = \mathbb{Q}$.
Switch the universe and watch the complement change while $A$ stays put.
Sets are unordered. But sometimes order is exactly what we need, like coordinates on a graph. Cartesian products build ordered pairs out of two sets.
The Cartesian product of $A$ and $B$, denoted $A \times B$, is the set of ordered pairs $(a, b)$ with $a \in A$ and $b \in B$:
$$A \times B = \{(a, b) : a \in A, b \in B\}$$
Pair every element of $A$ with every element of $B$:
Let $A = \{1, 2, x\}$ and $B = \{1, 2, y\}$. Find $A \times B$.
$$A \times B = \{(1, 1), (1, 2), (1, y), (2, 1), (2, 2), (2, y), (x, 1), (x, 2), (x, y)\}$$
Note: $(1, 2) \neq (2, 1)$ (order matters). Both pairs appear, and they are different elements.
A product is easiest to picture as a grid, with one dot per ordered pair.
You've been using a Cartesian product for years without the name:
Describe $\mathbb{R} \times \mathbb{R}$.
$\mathbb{R} \times \mathbb{R} = \{(x, y) : x \in \mathbb{R}, y \in \mathbb{R}\} = \mathbb{R}^2$. Geometrically, these are the $(x, y)$-points in the Cartesian plane.
The same idea works with any number of sets. If $A_1, \dots, A_n$ are sets, then
$$A_1 \times \dots \times A_n = \{(a_1, \dots, a_n) : a_1 \in A_1, \dots, a_n \in A_n\}$$
(ordered $n$-tuples). In the special case where every factor is the same set, we write $A^n = \underbrace{A \times \dots \times A}_{n\text{-times}}$ for the ordered $n$-tuples of elements of $A$.
If $A_1, \dots, A_n$ are finite then $|A_1 \times \dots \times A_n| = |A_1| \cdot |A_2| \cdots |A_n|$.
In the example above, $|A \times B| = 3 \cdot 3 = 9$, and there are indeed nine pairs.
Warning: the symbol $\times$ is used in sometimes ambiguous ways. Later on, we will also use the same symbol to define direct products of groups.
Let $A = \{1, 2\}$ and $B = \{x, y, z\}$. Find $|A \times B|$ and $|A \times B \times A|$. Is $A \times B = B \times A$?
$|A \times B| = 2 \cdot 3 = 6$ and $|A \times B \times A| = 2 \cdot 3 \cdot 2 = 12$.
No, $A \times B \neq B \times A$. For example, $(1, x) \in A \times B$, but every pair in $B \times A$ has a letter in its first slot, so $(1, x) \notin B \times A$. They have the same size, but they are different sets.
Last construction, and it's a big one: gather up every subset of a set into one new set.
The power set of a set $A$, denoted $\mathcal{P}(A)$, is the set of all subsets of $A$:
$$\mathcal{P}(A) = \{B : B \subseteq A\}$$
The elements of $\mathcal{P}(A)$ are themselves sets, so all the brace-counting skills from earlier come back here.
Some books write 2A for the power set. It means the same thing as $\mathcal{P}(A)$, which is what this site always uses. (The name will make sense in a minute.)
Here are the first few.
Find $\mathcal{P}(A)$ for $A = \emptyset$, $A = \{\Delta\}$, and $A = \{1, \{2\}\}$.
Careful with the first one: $\mathcal{P}(\emptyset) = \{\emptyset\}$ is not empty. It has exactly one element, namely $\emptyset$.
The sizes $1, 2, 4$ suggest a pattern. Build some power sets yourself and see if it holds up.
$\mathcal{P}(\emptyset)$ has $1$ element. Take the power set again: $2$. Again: $4$. Again: $16$. Once more: $65{,}536$. Who needs exponents?
If $|A| = n < \infty$ then $|\mathcal{P}(A)| = 2^n$.
"Proof." Every possible subset of $A$ is uniquely determined by looking at each element of $A$ and choosing whether or not to include it in the subset. There are $2$ choices for each of the $n$ elements, so the number of subsets is $\underbrace{2 \cdot 2 \cdots 2}_{n\text{-times}} = 2^n$.
That proof deserves a warning label.
Why the quotation marks around "Proof"? This argument "hides" the fact that we are relying on the principle of mathematical induction. The "$\cdots$" is doing real work that we haven't justified. The Spicy Bonus below fixes that.
Watch the doubling happen, one element at a time. This picture is the heart of the real proof.
The eight subsets of $\{a, b, c\}$ also fit together into a shape: tap one to see what's above and below it.
Now a quick check that the formula and the brace rules work together.
Let $A = \{1, 2\}$. Find $|\mathcal{P}(\mathcal{P}(A))|$. Is $\emptyset \in \mathcal{P}(A)$? Is $\emptyset \subseteq \mathcal{P}(A)$? Is $\{\emptyset\} \subseteq \mathcal{P}(A)$?
$|\mathcal{P}(A)| = 2^2 = 4$, so $|\mathcal{P}(\mathcal{P}(A))| = 2^4 = 16$.
All three statements are true. $\emptyset \subseteq A$, so $\emptyset$ is an element of $\mathcal{P}(A)$. The empty set is a subset of every set, including $\mathcal{P}(A)$. And since $\emptyset \in \mathcal{P}(A)$, the set $\{\emptyset\}$ is a subset of $\mathcal{P}(A)$.
Every question below makes a new version each time you press the button, in the same order as the lesson. Every wrong choice is a real mistake, and choosing one tells you which.
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Time to pay off that debt. Prove the theorem for real, using induction on the number of elements. The key idea is the one you saw in the Doubling Tree: adding one new element doubles the number of subsets.
Prove by induction on $n$: if $|A| = n$, then $|\mathcal{P}(A)| = 2^n$.
Proof. We use induction on $n = |A|$.
Base case ($n = 0$). Then $A = \emptyset$, whose only subset is $\emptyset$. So $\mathcal{P}(A) = \{\emptyset\}$ and $|\mathcal{P}(A)| = 1 = 2^0$.
Inductive step. Suppose every set with $n$ elements has exactly $2^n$ subsets, and let $|A| = n + 1$. Pick one element $a \in A$ and let $A' = A \setminus \{a\}$, so $|A'| = n$. Every subset $S \subseteq A$ falls into exactly one of two groups:
The two groups are disjoint and together contain every subset of $A$, so $|\mathcal{P}(A)| = 2^n + 2^n = 2^{n+1}$.
By induction, $|\mathcal{P}(A)| = 2^{|A|}$ for every finite set $A$. $\blacksquare$