Operations on Sets

If sets are the nouns of mathematics, the operations on sets are the verbs. Once you can describe collections of objects, you immediately want to combine them: glue two sets together, find the overlap, strip out the parts that share a property. Three operations — union, intersection, and difference — cover almost every combination you will ever need. They map, one-for-one, onto the logical connectives $\vee$, $\wedge$, and $\neg$ you met in §1.1, and that correspondence lets you prove set identities by translating them into propositional logic and back. The big result of this section — De Morgan's laws for sets — is exactly the logical De Morgan laws wearing a set-theoretic costume.

Union, intersection, difference

Given sets $A$ and $B$:

Union: $A \cup B = {x \mid x \in A ;\vee; x \in B}$ — everything in at least one of $A$, $B$.

Intersection: $A \cap B = {x \mid x \in A ;\wedge; x \in B}$ — everything in both $A$ and $B$.

Difference: $A \setminus B = {x \mid x \in A ;\wedge; x \notin B}$ — what remains of $A$ after deleting any elements that also lie in $B$.

Notice the perfect parallel: union is "or," intersection is "and," and difference is "and not." Anything you know about $\vee$, $\wedge$, and $\neg$ transfers to $\cup$, $\cap$, and $\setminus$.

Universal set and complement

In any given problem there is usually a tacit universal set $U$ — the larger arena from which all elements are drawn (the integers, the real numbers, the students in a class, etc.). Relative to this $U$, the complement of a set $A \subseteq U$ is

If you change the universal set, the complement changes — the complement of "even numbers" inside $\mathbb{Z}$ is the odd integers; inside $\mathbb{R}$ it is "all reals that are not even integers." Always name your $U$.

De Morgan's laws for sets

The two cornerstone identities of set algebra are:

In words: the complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements. The proof in each case is one line of propositional logic: $x \in \overline{A \cup B} ;\Leftrightarrow; \neg(x \in A \vee x \in B) ;\Leftrightarrow; (x \notin A) \wedge (x \notin B) ;\Leftrightarrow; x \in \overline{A} \cap \overline{B}$. The "push $\neg$ through, flip the connective" trick from logic is the proof of De Morgan for sets.

Disjoint sets

Two sets are disjoint if their intersection is empty: $A \cap B = \emptyset$. Disjointness is the set-theoretic version of "$P$ and $Q$ cannot both hold." A collection of pairwise disjoint sets whose union is the whole universal set is called a partition — partitions are the workhorse of counting arguments and (later) equivalence relations.

Pause and think: Why must the universal set $U$ be named before you can compute $\overline{A}$? Try writing $\overline{{1, 2, 3}}$ — what does the answer depend on? (Hint: the complement of the same three-element set is wildly different inside $\mathbb{Z}$, inside $\mathbb{N}$, or inside ${1, 2, 3, 4, 5}$.)

Try it

• Let $A = {1, 2, 3, 4}$ and $B = {3, 4, 5, 6}$. Before computing: predict whether $|A \cup B|$ equals $|A| + |B|$. Then compute $A \cup B$ and $A \cap B$ and explain what inclusion-exclusion has to do with it.
• Open the Venn-diagram widget. Predict which region represents $A \setminus B$. Now shade it and check.
• Predict first: if $A \subseteq B$, what is $A \setminus B$? What is $A \cup B$? What is $A \cap B$? Verify each with a concrete example.
• Test a De Morgan: take $U = {1,\ldots, 6}$, $A = {1, 2, 3}$, $B = {2, 3, 4}$. Compute both sides of $\overline{A \cap B} = \overline{A} \cup \overline{B}$ and verify equality.
• Are ${2, 4, 6}$ and ${1, 3, 5}$ disjoint? Does their union partition ${1, 2, 3, 4, 5, 6}$? What would it take to make a three-piece partition of the same universal set?

A trap to watch for

Beginners often confuse $\in$ with $\subseteq$. They are completely different: $\in$ relates an element to a set ("$2 \in {1, 2, 3}$"), while $\subseteq$ relates a set to a set ("${2} \subseteq {1, 2, 3}$"). Mixing them produces nonsense like "$2 \subseteq {1, 2, 3}$" (false — $2$ is not a set) or "${2} \in {1, 2, 3}$" (false — the set ${2}$ is not literally one of the three elements). The fix is to ask, every time: "is the left side an element of the right side (use $\in$) or a subset (use $\subseteq$)?"

What you now know

You can union, intersect, take differences, and complement sets — and you can prove identities like De Morgan's laws by translating to propositional logic. The next section closes Chapter 1 by tackling the trickiest of the connectives, the conditional $P \Rightarrow Q$, along with its biconditional sibling.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 1.
• Halmos, P. R. (1960). Naive Set Theory. Van Nostrand, §§3–5.
• Enderton, H. B. (1977). Elements of Set Theory. Academic Press, ch. 2.
• Kunen, K. (2009). The Foundations of Mathematics. College Publications, ch. 1.