Logic and Set Theory
2.3 Other Set Operations
Intersection and Union
We can combine sets the same way we combine logical statements, using "and" and "or." In fact, the parallel is exact: intersection mirrors the logical conjunction ($\land$), and union mirrors the logical disjunction ($\lor$).
Definition: Set Intersection
The intersection of two sets $A$ and $B$, written $A \cap B$, is the set of all elements that are in both $A$ and $B$:
$$A \cap B = \{x \mid x \in A \land x \in B\}$$
Definition: Disjoint Sets
Two sets are disjoint if they share no elements, that is, if $A \cap B = \emptyset$.
Example: Finding intersections
Find $A \cap B$ in each of the following.
- $$A = \{1, 2, 3, 4\}$$ $$B = \{3, 4, 5, 6\}$$
- $$A = \{0, 2, 4, 6, \ldots\}$$ $$B = \{1, 3, 5, 7, \ldots\}$$
- $$A = \{2, 4, 6, \ldots\}$$ $$B = \mathbb{N}$$
Show Solution
- $A \cap B = \{3, 4\}$, the elements common to both.
- The even whole numbers and the odd natural numbers share no elements: $A \cap B = \emptyset$. The sets are disjoint.
- Every positive even number is also a natural number, so $A \subseteq B$. Therefore $A \cap B = A = \{2, 4, 6, \ldots\}$.
MyOpenMath: Set Intersections
Definition: Set Union
The union of two sets $A$ and $B$, written $A \cup B$, is the set of all elements that are in $A$ or in $B$ (or both):
$$A \cup B = \{x \mid x \in A \lor x \in B\}$$
Example: Finding unions
Find $A \cup B$ in each of the following.
- $A = \{1, 2, 3, 4\}$, $B = \{3, 4, 5, 6\}$
- $A = \{0, 2, 4, 6, \ldots\}$, $B = \{1, 3, 5, 7, \ldots\}$
- $A = \{2, 4, 6, \ldots\}$, $B = \mathbb{N}$
Show Solution
- $A \cup B = \{1, 2, 3, 4, 5, 6\}$, list everything from both, without repeating.
- Together the even whole numbers and odd natural numbers cover every whole number: $A \cup B = \mathbb{W}$.
- The positive even numbers are already inside $\mathbb{N}$, so adding them doesn't enlarge it: $A \cup B = \mathbb{N}$.
MyOpenMath: Set Unions
Example: Operations with the empty set
Find each of the following, where $A = \{a, b, c\}$.
- $A \cap \emptyset$
- $A \cup \emptyset$
- $\emptyset \cap \emptyset$
- $\emptyset \cup \emptyset$
Show Solution
- $A \cap \emptyset = \emptyset$. There are no elements shared with an empty set.
- $A \cup \emptyset = A = \{a, b, c\}$. Adding nothing leaves the set unchanged.
- $\emptyset \cap \emptyset = \emptyset$.
- $\emptyset \cup \emptyset = \emptyset$.
Relative Complement (Set Difference)
The complement $\bar{A}$ removes all of $A$ from the universal set. But sometimes we want to remove the elements of one set from another specific set, regardless of what $U$ is. That operation is the set difference.
Definition: Set Difference
The set difference $B - A$ (also called the complement of $A$ relative to $B$, or "$B$ remove $A$") is the set of all elements in $B$ that are not in $A$:
$$B - A = \{x \mid x \in B \land x \notin A\}$$
Notice that $B - A$ and $A - B$ are generally not the same, the order matters. Think of it like subtraction: $5 - 3 \neq 3 - 5$.
Example: Computing set differences
Let $A = \{d, e, f\}$, $B = \{a, b, c, d, e, f\}$, $C = \{a, b, c\}$, and $D = \{c, d, e, f\}$. Find each of the following.
- $A - B$
- $A - C$
- $B - C$
- $C - B$
- $C - D$
Show Solution
- $A - B$: every element of $A$ is already in $B$, so removing $B$'s elements from $A$ takes everything. $A - B = \emptyset$.
- $A - C$: $A = \{d,e,f\}$ and $C = \{a,b,c\}$ share nothing, so nothing is removed. $A - C = \{d,e,f\} = A$.
- $B - C$: remove $\{a,b,c\}$ from $\{a,b,c,d,e,f\}$. $B - C = \{d, e, f\}$.
- $C - B$: every element of $C$ is also in $B$, so everything is removed. $C - B = \emptyset$.
- $C - D$: $C = \{a,b,c\}$, $D = \{c,d,e,f\}$. The only shared element is $c$, so $C - D = \{a, b\}$.
MyOpenMath: Set Difference
Rules for Set Operations
Set operations follow algebraic-style laws, several of which mirror the logical laws we proved with truth tables earlier. This isn't a coincidence, the logical connectives $\land$ and $\lor$ directly correspond to $\cap$ and $\cup$.
Does Grouping Matter?
Example: Distributive law for sets
Is the following statement true? Let $A = \{a,b,c\}$, $B = \{c,d\}$, $C = \{d,e,f\}$ and check:
$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$
Show Solution
Compute each side separately:
Left side: $B \cup C = \{c, d, e, f\}$, so $A \cap (B \cup C) = \{a,b,c\} \cap \{c,d,e,f\} = \{c\}$.
Right side: $A \cap B = \{c\}$; $A \cap C = \emptyset$; $(A \cap B) \cup (A \cap C) = \{c\} \cup \emptyset = \{c\}$.
Both sides equal $\{c\}$. The distributive law holds: intersection distributes over union.
De Morgan's Laws for Sets
Just as De Morgan's Laws in logic state $\sim(p \land q) \equiv \sim p \lor \sim q$, there are corresponding laws for sets.
Example: De Morgan's Law for Sets
Use a Venn diagram to show that $\overline{A \cap B} = \bar{A} \cup \bar{B}$.
Show Solution
Divide the universal set $U$ into four regions based on membership in $A$ and $B$:
- $r_1$: inside $A$ only
- $r_2$: inside both $A$ and $B$
- $r_3$: inside $B$ only
- $r_4$: inside $U$ but outside both $A$ and $B$
The region $r_4$ is the part of the universal set $U$ outside both circles.
$A \cap B$ consists of region $r_2$ only, so $\overline{A \cap B}$ is everything else: $r_1 \cup r_3 \cup r_4$.
$\bar{A}$ is everything not in $A$: regions $r_3 \cup r_4$.
$\bar{B}$ is everything not in $B$: regions $r_1 \cup r_4$.
$\bar{A} \cup \bar{B} = r_1 \cup r_3 \cup r_4$.
Both sides describe the same regions. Therefore $\overline{A \cap B} = \bar{A} \cup \bar{B}$.
MyOpenMath: Set Operations and Venn Diagrams
Three-Set Problems
One of the most practical applications of set operations is counting. When several sets overlap, a three-circle Venn diagram lets you track exactly how many elements fall into each distinct region. The key technique is to start from the inside and work outward.
Example: Survey with three overlapping sets
In a survey of 110 college freshmen, the following information was gathered about their high school course backgrounds:
- 25 took physics
- 45 took biology
- 48 took mathematics
- 10 took physics and mathematics
- 8 took biology and mathematics
- 6 took physics and biology
- 5 took all three subjects
- How many students took biology, but neither physics nor mathematics?
- How many students took physics, biology, or mathematics (at least one)?
- How many students did not take any of the three subjects?
Show Solution
Label the sets $P$ (physics), $B$ (biology), $M$ (mathematics). Work from the innermost region outward.
Center (all three): $5$.
Two-subject regions (subtract the all-three count from each pair):
- Physics and math only (not bio): $10 - 5 = 5$
- Biology and math only (not physics): $8 - 5 = 3$
- Physics and biology only (not math): $6 - 5 = 1$
Single-subject regions (subtract all overlapping regions from each total):
- Physics only: $25 - 5 - 5 - 1 = 14$
- Biology only: $45 - 5 - 1 - 3 = 36$
- Mathematics only: $48 - 5 - 3 - 5 = 35$
The region outside all three circles represents the 11 students who took none of the subjects.
- Biology only (no physics, no math): 36.
- Add all seven regions: $14 + 36 + 35 + 5 + 3 + 1 + 5 = \mathbf{99}$.
- Students in none of the three subjects: $110 - 99 = \mathbf{11}$.