Back to the on-screen lesson ·
Union, intersection and difference as conditions on membership, the element method for proving an identity, and counting a union without counting the overlap twice.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to read a set operation as a condition on membership, prove a set identity by the element method in both directions, and say when a chain of equivalences may replace the two halves. You will also be able to count the union of two or three finite sets by inclusion and exclusion, and identify the overlap correctly when the conditions are divisibility by two numbers that share a factor.
You have used sets informally since school — the set of solutions, the domain of a function, an interval on the line. Unit 1 gave you the connectives, and that is all a set operation is: the union is or, the intersection is and, the difference is and not. What is new is the habit of proving a set identity rather than drawing a picture of it.
$x \in A$ says $x$ is an element of $A$. $A \subseteq B$ says every element of $A$ is one of $B$, and it allows $A = B$; $A \subsetneq B$ rules that out. $\varnothing$ is the empty set, which is a subset of everything. Two sets are disjoint when their intersection is empty, and $|A|$ is the cardinality — for a finite set, how many elements it has.
| Operation | An element is in it when |
|---|---|
| $A \cup B$ | it is in $A$ or in $B$ (or both) |
| $A \cap B$ | it is in $A$ and in $B$ |
| $A \setminus B$ | it is in $A$ and not in $B$ |
| $A^{c}$ | it is in the universe and not in $A$ |
| $A \times B$ | it is a pair $(a, b)$ with $a \in A$ and $b \in B$ |
Read across that table once more: the right-hand column is entirely made of unit 1's connectives. That is not a coincidence, and it is what makes set identities provable rather than merely drawable.
The element method. To prove $X = Y$ for sets: take an arbitrary $x \in X$ and show $x \in Y$, then take an arbitrary $x \in Y$ and show $x \in X$. Two inclusions, $X \subseteq Y$ and $Y \subseteq X$, because set equality is exactly the conjunction of those two — which is the biconditional of lesson 3 wearing different notation.
Most of the time the two halves are the same chain of equivalences read in opposite directions, and then you may write it once as a chain of if and only ifs. Say that you are doing that, and check that every link really is reversible; a chain with one one-way link proves one inclusion and not the other.
A Venn diagram is not a proof. It is an excellent way to find the identity and a poor way to establish it: a picture of three sets can be drawn to show every one of the eight regions, but a picture of four cannot, and nothing in the drawing tells you that.
Another way: steps
To prove $X = Y$:
Another way: example
$A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$. Unfolded, the left is $x \in A \wedge \neg(x \in B \vee x \in C)$; De Morgan turns that into $x \in A \wedge x \notin B \wedge x \notin C$, which is the right. One law of lesson 3, and the identity is a theorem rather than a picture.
For finite sets, $|A \cup B| = |A| + |B| - |A \cap B|$. The proof is the element method again: every element of the union lies in exactly one of three regions — $A$ only, $B$ only, both — and the right-hand side counts each region once.
Three sets need the pattern extended:
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
Add the singles, subtract the pairs, add the triple. The alternating signs are what unit 4 will generalise; the reason for them is that an element in all three sets is counted three times, removed three times, and has to be put back once.
The practical trap is the overlap. Among $1$ to $60$, the numbers divisible by $3$ and by $4$ are the multiples of $12$ — the least common multiple, which happens to be $3 \times 4$ here. For $3$ and $6$ it is $6$, not $18$, and using the product would undercount the overlap and overcount the union.
Confusing an element with the set containing it. $1 \in \{1, 2\}$ and $\{1\} \subseteq \{1, 2\}$; $1 \subseteq \{1,2\}$ and $\{1\} \in \{1,2\}$ are both false. The difference matters enormously once power sets arrive in the next lesson.
Forgetting the empty set. $\varnothing$ is a subset of every set and an element of almost none.
*Reading or exclusively.* The union contains everything in both.
Proving one inclusion. $X \subseteq Y$ is half of $X = Y$, and it is the half that is usually easy.
Draw two circles and the identity $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$ becomes obvious, which is exactly why it is worth drawing. But the picture works because it happens to show all the regions, and with four sets no plane diagram of overlapping circles does. The element method does not care how many sets there are, because it argues about one element at a time, and that is the whole reason to learn it on identities you could have drawn.
Claim: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. Let $x$ be an arbitrary element of the left side.
Start from one arbitrary element.
Then $x \in A$ and ($x \in B$ or $x \in C$). Distributing, that is ($x \in A$ and $x \in B$) or ($x \in A$ and $x \in C$), which is the right side.
One law of lesson 3 does the work.
Every step is an equivalence, so reading the chain backwards gives the other inclusion, and the two sets are equal.
Say that the steps reverse; do not leave it implied.
How many of $1$ to $60$ are divisible by $3$ or by $4$? There are $20$ multiples of $3$ and $15$ of $4$.
Count each condition alone.
Both conditions hold for the multiples of $12$, of which there are $5$.
The overlap is the least common multiple's multiples.
So the answer is $20 + 15 - 5 = 30$. Had the divisors been $3$ and $6$, the overlap would be the multiples of $6$, not of $18$ — the product is the wrong overlap whenever the divisors share a factor.
The overlap is where this goes wrong.
Unfold the left: $x \in A$ and not ($x \in B$ and $x \notin C$).
Write the membership condition out.
De Morgan on the inner bracket: $x \in A$ and ($x \notin B$ or $x \in C$).
The negation flips the connective.
Distributing over the or gives ($x \in A$ and $x \notin B$) or ($x \in A$ and $x \in C$), which is the right side. So yes — and notice that the whole proof was two laws from lesson 3 applied to a membership condition, with no picture drawn at any point.
Let $A = [5, 10]$ and $B = [7, 13]$, both closed. Give $A \cap B$.
This task has no paper form; do it on a device.
Two finite sets have $|A| = 30$, $|B| = 18$ and $|A \cap B| = 12$. What is $|A \cup B|$?
Answer:
Two finite sets have $|A| = 25$, $|B| = 10$ and $|A \cap B| = 10$. Fill in the table.
| How many elements | |
|---|---|
| $|A \cup B|$ | |
| $|A \setminus B|$ |
Match each set expression to what it says about membership.
| everything in at least one of the two sets | everything in both sets at once | everything in the first set that is not in the second | every ordered pair with its first entry from the first set | every subset of the set, the empty set and the whole set included | |
|---|---|---|---|---|---|
| $A \cup B$ | |||||
| $A \cap B$ | |||||
| $A \setminus B$ | |||||
| $A \times B$ | |||||
| $\mathcal{P}(A)$ |
How many of the numbers $1$ to $36$ are divisible by $3$ or by $6$?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Let $A = [5, 10]$ and $B = [7, 13]$, both closed. Give $A \cap B$.
This task has no paper form; do it on a device.
You can prove a set identity by taking an arbitrary element and rewriting its membership condition, and count a union without double counting. Say in your own words why a Venn diagram is not a proof, and what the two halves of a set equality are. Next: the sets whose elements are themselves sets or pairs, and how many of them there are.
10. Your turn: is $A \setminus (B \setminus C) = (A \setminus B) \cup (A \cap C)$?, step 3