Discrete Math › Section F · Discrete structures revisited › Topic F.1
Sets and set operations
Sets are the containers out of which nearly every other structure in mathematics is built, from graphs and relations to databases. This topic gathers the notation, the relationships between sets and the operations on them into one careful reference.
Collections without order
A set is an unordered collection of distinct objects, called its elements or members. Only membership matters: \(\{1, 2, 3\}\), \(\{3, 1, 2\}\) and \(\{1, 1, 2, 3\}\) are all the same set, because each contains exactly 1, 2 and 3. That is the key contrast with a sequence, where order and repetition count. Two sets are equal exactly when they have the same elements. Sets have appeared throughout this course, as the vertex sets of graphs and the outcomes being counted; this topic collects the language in one place so that it can be used precisely.
Describing sets
Write \(x \in A\) for "\(x\) is an element of \(A\)" and \(x \notin A\) otherwise. Small sets can be listed in braces. Larger ones use set-builder notation, \(\{x \in \mathbb{Z} : x^2 < 10\}\), read "the integers \(x\) such that \(x^2 < 10\)", which is \(\{-3, -2, \ldots, 3\}\). Standard sets are \(\mathbb{N} = \{0, 1, 2, \ldots\}\) (some authors start at 1, so check), the integers \(\mathbb{Z}\), the rationals \(\mathbb{Q}\) and the reals \(\mathbb{R}\). The empty set \(\varnothing\) has no elements. The cardinality \(|A|\) of a finite set is its number of elements.
Elements and subsets
\(A \subseteq B\) means every element of \(A\) is also in \(B\). Every set is a subset of itself, and \(\varnothing\) is a subset of every set, since it has no element that could fail the test. A proper subset, \(A \subsetneq B\), is a subset that is not equal to \(B\). Keep membership and inclusion apart. In \(A = \{1, \{2\}, 3\}\), the set \(\{2\}\) is an element, so \(\{2\} \in A\), but 2 itself is not, so \(2 \notin A\); meanwhile \(\{1, 3\} \subseteq A\). To prove \(A = B\), the standard method is to prove both \(A \subseteq B\) and \(B \subseteq A\).
Power sets
The power set \(\mathcal{P}(A)\) is the set of all subsets of \(A\). For \(A = \{a, b, c\}\) it has 8 elements: \(\varnothing\), \(\{a\}\), \(\{b\}\), \(\{c\}\), \(\{a, b\}\), \(\{a, c\}\), \(\{b, c\}\) and \(\{a, b, c\}\). In general \(|\mathcal{P}(A)| = 2^{|A|}\): building a subset means deciding, for each of the \(n\) elements in turn, whether it is in or out, which by the product principle of "The sum and product principles" gives \(2^n\) choices. Both \(\varnothing\) and \(A\) itself are always included, so even \(\mathcal{P}(\varnothing) = \{\varnothing\}\) has one element.
The basic operations
Fix a universal set \(U\) containing everything under discussion. The union \(A \cup B\) holds the elements in \(A\) or \(B\) or both. The intersection \(A \cap B\) holds the elements in both; if it is empty, \(A\) and \(B\) are disjoint. The difference \(A \setminus B\), also written \(A - B\), holds the elements of \(A\) that are not in \(B\). The complement \(\overline{A}\) holds the elements of \(U\) that are not in \(A\), so \(\overline{A} = U \setminus A\). Each operation matches a logical connective: or, and, and not, as in the topic "Statements, connectives, and quantifiers".
Worked example: computing with sets
Let \(U = \{1, 2, \ldots, 12\}\), let \(A = \{2, 3, 5, 7, 11\}\), the primes in \(U\), and let \(B = \{1, 3, 5, 7, 9, 11\}\), the odd numbers. 1. \(A \cap B = \{3, 5, 7, 11\}\): the odd primes. 2. \(A \cup B = \{1, 2, 3, 5, 7, 9, 11\}\). 3. \(A \setminus B = \{2\}\) and \(B \setminus A = \{1, 9\}\), so set difference is not symmetric. 4. \(\overline{A \cup B} = \{4, 6, 8, 10, 12\}\), the even numbers that are not prime. 5. Check the sizes: \(|A \cup B| = 5 + 6 - 4 = 7\), matching the list in step 2.
Venn diagrams and set identities
A Venn diagram draws \(U\) as a rectangle and each set as a region inside it, with overlaps showing intersections. Two overlapping circles cut the rectangle into four regions, and three circles into eight, one for each combination of in and out. Diagrams suggest identities, which then need proof. The most useful are the distributive laws, such as \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\), and De Morgan's laws:
These mirror the logical laws for not, or and and exactly, because "\(x \in A\)" is a statement.
Worked example: proving an identity
Prove \(A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\) by showing that each side is a subset of the other. 1. Take \(x\) in the left side. Then \(x \in A\) and \(x \notin B \cup C\), so \(x \notin B\) and \(x \notin C\). 2. Hence \(x \in A \setminus B\) and \(x \in A \setminus C\), so \(x\) is in the right side. 3. Take \(x\) in the right side. Then \(x \in A\), \(x \notin B\) and \(x \notin C\), so \(x \notin B \cup C\). 4. Hence \(x \in A \setminus (B \cup C)\). Both inclusions hold, so the sets are equal. The step from "not in \(B \cup C\)" to "not in \(B\) and not in \(C\)" is De Morgan's law at work.
Cartesian products
The Cartesian product \(A \times B\) is the set of all ordered pairs \((a, b)\) with \(a \in A\) and \(b \in B\). For \(A = \{1, 2\}\) and \(B = \{x, y, z\}\) it has the six pairs \((1, x)\), \((1, y)\), \((1, z)\), \((2, x)\), \((2, y)\), \((2, z)\). In general \(|A \times B| = |A| \cdot |B|\). Order inside a pair matters, so \(A \times B \ne B \times A\) unless the sets are equal or one is empty. The coordinate plane is \(\mathbb{R} \times \mathbb{R}\), a relation from \(A\) to \(B\) is a subset of \(A \times B\), and a database table is a subset of a product of column value sets.
Common mistakes to avoid
First, confusing \(\in\) with \(\subseteq\): \(2 \in \{1, 2\}\) but \(\{2\} \subseteq \{1, 2\}\). Second, thinking \(\varnothing\) and \(\{\varnothing\}\) are the same: the first has no elements, the second has one. Third, forgetting \(\varnothing\) or the whole set when listing a power set. Fourth, treating difference as symmetric, when \(A \setminus B\) and \(B \setminus A\) usually differ. Fifth, misapplying De Morgan's law by keeping the operation: the complement of a union is the intersection of the complements. Sixth, adding \(|A| + |B|\) for a union without subtracting the overlap.
Key takeaways
A set is determined by its elements alone, with no order or repetition. Use \(\in\) for membership and \(\subseteq\) for inclusion, and prove equality by double inclusion. A set with \(n\) elements has \(2^n\) subsets. Union, intersection, difference and complement match or, and, but not, and not, and obey distributive and De Morgan laws. The Cartesian product collects ordered pairs and has \(|A| \cdot |B|\) elements. For a union of two finite sets, \(|A \cup B| = |A| + |B| - |A \cap B|\), the start of "Overlaps and inclusion-exclusion".
Flashcards
Flashcard
An unordered collection of distinct elements
Test your understanding
Question 1 of 5
A set A has 6 elements. How many subsets does A have, counting the empty set and A itself?
Question 2 of 5
Let A = {1, {2}, 3}. Which statement is true?
Question 3 of 5
Let A = {1, 2, 3, 4} and B = {3, 4, 5}. What is A ∖ B?
Question 4 of 5
By De Morgan's laws, the complement of A ∩ B equals which set?
Question 5 of 5
If |A| = 3 and |B| = 5, how many elements does the Cartesian product A × B have?
