Sets: operations, power sets and proving set equality

Sets are the “data structure” of discrete mathematics. Functions, relations, graphs, probability: all are built on sets. On the midterm this topic usually brings a computation part (do the operations, write the power set) and a proof part (show that two sets are equal). The computation part is free marks; in the proof part you apply one of three methods like a template.

Golden rules:

1. A set is unordered and has no repeats. $\{1, 2, 3\} = \{3, 1, 2\} = \{1, 1, 2, 3\}$.
2. $\in$ and $\subseteq$ are different questions. The first asks about a single element, the second about all elements.
3. $\lvert \mathcal{P}(A) \rvert = 2^{\lvert A \rvert}$. Don’t forget to write the empty set and $A$ itself.
4. Set operations are logical operations. $\cap = \land$, $\cup = \lor$, complement $= \lnot$.
5. Two directions for equality, one example for inequality.

Basic definitions

Set: a well-defined collection of objects. The objects are called elements: $a \in A$.

Two ways of writing:

• Roster method (list): $A = \{2, 4, 6, 8\}$.
• Set-builder notation: $A = \{x \in \mathbb{Z}^+ \mid x \text{ is even and } x < 10\}$.

Standard sets: $\mathbb{N} = \{0, 1, 2, \dots\}$ (including 0 in Rosen), $\mathbb{Z}$ the integers, $\mathbb{Z}^+$ the positive integers, $\mathbb{Q}$ the rationals, $\mathbb{R}$ the reals. Intervals: $[a, b]$, $(a, b)$ and so on.

For every set, $\emptyset \subseteq A$ and $A \subseteq A$. The empty set is a subset because of “vacuous truth”: since $x \in \emptyset$ is never true, the conditional is automatically true.

PITFALL · $\emptyset$ versus $\{\emptyset\}$. $\emptyset$ is an empty box. $\{\emptyset\}$ is a box with an empty box inside: it has one element. $\lvert \emptyset \rvert = 0$, $\lvert \{\emptyset\} \rvert = 1$.

Power sets and Cartesian products

Power set $\mathcal{P}(A)$: the set of all subsets of $A$.

$\mathcal{P}(\{a, b, c\}) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$

8 elements: $2^3$. Why $2^n$? There are two choices for each element: it is either in the subset or not. With $n$ elements, $2 \cdot 2 \cdots 2 = 2^n$.

To write them systematically, group by size: 0 elements (1 subset), 1 element (3), 2 elements (3), 3 elements (1).

Cartesian product $A \times B = \{(a, b) \mid a \in A,\ b \in B\}$. The elements are ordered pairs: $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$. With $A = \{1, 2\}$, $B = \{p, q\}$:

$A \times B = \{(1, p), (1, q), (2, p), (2, q)\}, \qquad \lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert.$

The elements of $B \times A$ look like $(p, 1)$, with the first coordinate from $B$. So in general $A \times B \ne B \times A$. $A \times \emptyset = \emptyset$.

Set operations

If $A \cap B = \emptyset$, then $A$ and $B$ are disjoint.

Example. $U = \{1, \dots, 8\}$, $A = \{1, 2, 3, 4\}$, $B = \{3, 4, 5, 6\}$.

A ∩ B = {3, 4}            A ∪ B = {1, 2, 3, 4, 5, 6}
A − B = {1, 2}            B − A = {5, 6}
Ā = {5, 6, 7, 8}          A ⊕ B = {1, 2, 5, 6}

Inclusion-exclusion: $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$. In the example, $4 + 4 - 2 = 6$. The intersection is counted twice, so it is subtracted once.

Set identities

All of them are exact copies of the laws of logic:

Three ways to prove set equality

Way 1: Double inclusion

To show $X = Y$, show $X \subseteq Y$ and $Y \subseteq X$ separately.

Theorem. $\overline{A \cup B} = \overline{A} \cap \overline{B}$.

(⊆) Let x ∈ complement(A ∪ B). Then x ∉ A ∪ B, so it is not the case
    that x ∈ A or x ∈ B. By De Morgan's law (logic), x ∉ A and x ∉ B,
    i.e. x ∈ Ā and x ∈ B̄. Hence x ∈ Ā ∩ B̄.
(⊇) Let x ∈ Ā ∩ B̄. Then x ∉ A and x ∉ B, so x is in neither set,
    i.e. x ∉ A ∪ B. Hence x ∈ complement(A ∪ B).
Both inclusions hold, so the sets are equal.  ∎

Way 2: Membership table

The same as a truth table: 1 means “is an element”, 0 means “is not an element”. Three sets give 8 rows. Compute the column of each side; if they are the same, the sets are equal.

Theorem. $A - (B \cap C) = (A - B) \cup (A - C)$.

“Since the columns for $A - (B \cap C)$ and $(A - B) \cup (A - C)$ are identical, the two sets are equal.” ∎

When filling in the $X - Y$ column, the rule is: 1 if “1 in $X$ AND 0 in $Y$”. In the rows where $A = 0$ the difference is automatically 0; you fill in the lower half quickly.

Way 3: Set-builder and laws of logic

Justify each step with a definition or a law of logic. Question 9 is an example of this way. It is the shortest to write, but writing the reason for every line is mandatory.

TIP · Which way should I choose? If the question says “use a membership table”, use the table. If it says “Prove that”, the safest is double inclusion; the instructor usually does that in class. If time is short, the table is the most mechanical way and has the lowest chance of error.

Showing they are not equal

A single concrete example: choose small sets ($\{1\}$, $\emptyset$), compute both sides, and get different results. In a membership table, a row with different values gives you a ready-made example: put the element 1 into the sets that have a 1 in that row.

Common mistakes