Chapter 27 — Sets
Table of Contents
27.1 Set Notation and Basics
Definition. A set is a well-defined collection of distinct objects, called elements or members.
Notation:
- Roster form: $S = {1, 2, 3, 4}$
- Set-builder form: $S = {x \mid x \text{ is a positive integer less than } 5}$
- $a \in S$ means “$a$ is an element of $S$”
- $a \notin S$ means “$a$ is not an element of $S$”
Standard Number Sets:
| Symbol | Name | Description | |—|—|—| | $\mathbb{N}$ | Natural numbers | ${1, 2, 3, \ldots}$ (or ${0, 1, 2, \ldots}$) | | $\mathbb{Z}$ | Integers | ${\ldots, -2, -1, 0, 1, 2, \ldots}$ | | $\mathbb{Q}$ | Rational numbers | ${p/q \mid p, q \in \mathbb{Z}, q \neq 0}$ | | $\mathbb{R}$ | Real numbers | All points on the number line | | $\mathbb{C}$ | Complex numbers | ${a + bi \mid a, b \in \mathbb{R}}$ |
| Cardinality. The number of elements in a set $S$ is its cardinality, denoted $ | S | $ or $#S$. |
| Example: $ | {a, b, c} | = 3$. |
The empty set $\emptyset = {}$ has cardinality $0$.
Warning. Sets have no repeated elements and no order. So ${1, 2, 3} = {3, 1, 2} = {1, 1, 2, 3}$.
Exercise 27-1. List the elements of ${x \in \mathbb{Z} \mid x^2 < 20}$.
27.2 Union, Intersection, Complement
Set Operations. Given sets $A$ and $B$:
| Operation | Notation | Definition | |—|—|—| | Union | $A \cup B$ | ${x \mid x \in A \text{ or } x \in B}$ | | Intersection | $A \cap B$ | ${x \mid x \in A \text{ and } x \in B}$ | | Complement | $\overline{A}$ or $A^c$ | ${x \mid x \notin A}$ (relative to a universal set $U$) | | Difference | $A \setminus B$ | ${x \mid x \in A \text{ and } x \notin B}$ |
Example 27-1. Let $A = {1, 2, 3, 4, 5}$ and $B = {3, 4, 5, 6, 7}$.
- $A \cup B = {1, 2, 3, 4, 5, 6, 7}$
- $A \cap B = {3, 4, 5}$
- $A \setminus B = {1, 2}$
De Morgan’s Laws:
\(\overline{A \cup B} = \overline{A} \cap \overline{B}\) \(\overline{A \cap B} = \overline{A} \cup \overline{B}\)
“The complement of the union is the intersection of the complements” (and vice versa).
Exercise 27-2. Let $U = {1, 2, \ldots, 10}$, $A = {1, 3, 5, 7, 9}$, $B = {2, 3, 5, 7}$. Find $A \cup B$, $A \cap B$, $\overline{A}$, $A \setminus B$.
27.3 Venn Diagrams
A Venn diagram uses overlapping circles to visualize relationships between sets.
Two-Set Venn Diagram
For sets $A$ and $B$, the diagram divides the universal set into four regions:
| Region | Represents |
|---|---|
| Inside $A$ only | $A \setminus B$ |
| Inside $B$ only | $B \setminus A$ |
| Overlap | $A \cap B$ |
| Outside both | $\overline{A \cup B}$ |
Key formula:
\[|A \cup B| = |A| + |B| - |A \cap B|\]Example 27-2. In a class of 40 students, 25 play basketball and 20 play soccer. If 10 play both, how many play neither?
| $ | B \cup S | = 25 + 20 - 10 = 35$. |
Neither: $40 - 35 = 5$.
Three-Set Venn Diagram
Example 27-3 (Hospital Problem). In a hospital with 100 patients:
- 37 have condition $A$, 36 have $B$, 37 have $C$.
- 17 have $A \cap B$, 15 have $A \cap C$, 12 have $B \cap C$.
- 5 have all three ($A \cap B \cap C$).
By inclusion-exclusion:
\[|A \cup B \cup C| = 37 + 36 + 37 - 17 - 15 - 12 + 5 = 71.\]Patients with none of the conditions: $100 - 71 = 29$.
Exercise 27-3. In a class, 15 students take French, 12 take Spanish, and 8 take both. How many take at least one language?
Exercise 27-4. Verify the three-set hospital example by filling in each of the 8 regions of a 3-set Venn diagram.
27.4 Subsets and Counting
$A$ is a subset of $B$ (written $A \subseteq B$) if every element of $A$ is also in $B$.
$A$ is a proper subset of $B$ (written $A \subset B$) if $A \subseteq B$ and $A \neq B$.
The empty set $\emptyset$ is a subset of every set.
Number of Subsets. A set with $n$ elements has exactly $2^n$ subsets (including $\emptyset$ and the set itself).
Why? Each element is either in or out of a subset — 2 choices per element, so $2^n$ total.
Example. ${a, b, c}$ has $2^3 = 8$ subsets:
\(\emptyset,\; \{a\},\; \{b\},\; \{c\},\; \{a,b\},\; \{a,c\},\; \{b,c\},\; \{a,b,c\}.\)
Combinatorial Identity. The $2^n$ count connects to the Binomial Theorem (Chapter 25):
\[\sum_{k=0}^{n} \binom{n}{k} = 2^n\]The left side counts subsets of each size; the right side counts all subsets.
Exercise 27-5. How many subsets does ${1, 2, 3, 4, 5}$ have? How many proper subsets?
Exercise 27-6. How many subsets of ${1, 2, \ldots, 10}$ contain the element 1?
27.5 Inclusion-Exclusion
Principle of Inclusion-Exclusion (PIE). For two sets:
\[|A \cup B| = |A| + |B| - |A \cap B|\]For three sets:
\[|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\]The pattern continues, alternating between adding and subtracting.
Example 27-4. How many integers from 1 to 100 are divisible by 2 or 3?
-
$ A = \lfloor 100/2 \rfloor = 50$ (divisible by 2) -
$ B = \lfloor 100/3 \rfloor = 33$ (divisible by 3) -
$ A \cap B = \lfloor 100/6 \rfloor = 16$ (divisible by both, i.e. by 6)
\(|A \cup B| = 50 + 33 - 16 = 67.\)
Example 27-5. How many integers from 1 to 1000 are divisible by none of 2, 3, or 5?
By inclusion-exclusion applied to divisibility by 2, 3, and 5:
| $ | A \cup B \cup C | = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$. |
Divisible by none: $1000 - 734 = 266$.
Exercise 27-7. How many integers from 1 to 200 are divisible by 4 or 6?
The Big Picture — Russell’s Paradox
Can a set contain itself? Consider $R = {S \mid S \notin S}$, the “set of all sets that do not contain themselves.”
Is $R \in R$?
- If yes, then by definition $R \notin R$. Contradiction!
- If no, then by definition $R \in R$. Contradiction!
This is Russell’s Paradox (1901). It showed that naive set theory is inconsistent — you can’t just define any collection as a “set.” Modern mathematics uses axiomatic set theory (ZFC) to avoid such paradoxes by restricting what can be a set.
Problems to Solve for Chapter 27
Problem 500. If $A = {1, 2, 3, 4}$ and $B = {3, 4, 5, 6, 7}$, find $|A \cup B|$ and $|A \cap B|$.
Problem 501. In a class of 50 students, 30 like math, 25 like science, and 10 like both. How many like neither?
Problem 502. How many subsets of ${1, 2, 3, 4, 5, 6}$ contain at least 2 elements?
Problem 503. If $|A| = 10$, $|B| = 15$, and $|A \cup B| = 20$, find $|A \cap B|$.
Problem 504. Prove that for any finite sets $A$ and $B$, $|A \cup B| + |A \cap B| = |A| + |B|$.
Problem 505. In a survey of 200 people: 120 drink coffee, 80 drink tea, 40 drink both. How many drink neither coffee nor tea?
Problem 506. How many integers from 1 to 60 are divisible by 2, 3, or 5? How many are divisible by none of these? (Use inclusion-exclusion.)
Problem 507. Show that the number of subsets of an $n$-element set with an even number of elements equals the number with an odd number. (Hint: Binomial Theorem with $x = 1, y = -1$.)