Set Operations and Boolean Identities

Set Operations as Membership Tests

Unions, intersections, complements, and differences are ways to describe which elements belong to a set. Their identities are useful because they let us rewrite a complicated set expression without changing its elements. The safest way to derive or check such a rewrite is to take an arbitrary element and translate each operation into a membership condition.

Throughout this tutorial, $X$ is an arbitrary underlying set, and $A,B,C\subseteq X$. No measure or measurability assumption is involved. A complement is always taken relative to $X$; changing the underlying set can therefore change a complement. Two sets are equal precisely when they have the same elements: $E=F$ means that, for every $x\in X$, $x\in E$ if and only if $x\in F$.

Definition: The union $A\cup B$ consists of the elements in $A$ or in $B$, or in both. The intersection $A\cap B$ consists of the elements in both $A$ and $B$. The complement of $A$ is $A^c=X\setminus A=\{x\in X:x\notin A\}$. The difference $A\setminus B$ is $\{x\in X:x\in A\text{ and }x\notin B\}$.

The words “or” and “and” in these definitions have their inclusive and simultaneous meanings, respectively. Thus an element belonging to both $A$ and $B$ lies in $A\cup B$, while an element lies in $A\cap B$ only if it belongs to each set. Complement records failure of membership in $A$, but only among elements of $X$.

Distributive Identities

Theorem (Distributive laws): For all subsets $A,B,C$ of $X$, $$ A\cap(B\cup C)=(A\cap B)\cup(A\cap C), \qquad A\cup(B\cap C)=(A\cup B)\cap(A\cup C). $$

Proof. Fix any $x\in X$. For the first identity, the membership definitions give $x\in A\cap(B\cup C)$ if and only if $x\in A$ and $(x\in B\text{ or }x\in C)$. This holds if and only if $(x\in A\text{ and }x\in B)$ or $(x\in A\text{ and }x\in C)$, which holds if and only if $x\in(A\cap B)\cup(A\cap C)$. For the second identity, $x\in A\cup(B\cap C)$ if and only if $x\in A$ or $(x\in B\text{ and }x\in C)$. This holds if and only if $(x\in A\text{ or }x\in B)$ and $(x\in A\text{ or }x\in C)$, which holds if and only if $x\in(A\cup B)\cap(A\cup C)$. Since the equivalences hold for every $x\in X$, each pair of sets is equal. This argument also covers the case $X=\varnothing$: there is no element that could belong to either side, so both sides of each identity are empty. $\square$

The two identities express different ways of distributing one operation over the other. In the first, intersection distributes over union; in the second, union distributes over intersection. They can be applied in either direction. For example, the first identity can expand an intersection with a union, or factor a union of two intersections that share the factor $A$.

Worked Example: Checking Both Distributive Laws

Let $X=\{1,2,3,4,5,6,7,8\}$, $A=\{1,2,3,5\}$, $B=\{2,4,5,7\}$, and $C=\{1,4,5,8\}$. Calculate both sides of $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$.

First, $B\cup C=\{1,2,4,5,7,8\}$. Intersecting with $A=\{1,2,3,5\}$ keeps exactly the elements common to the two sets, so $A\cap(B\cup C)=\{1,2,5\}$. On the other side, $A\cap B=\{2,5\}$, and $A\cap C=\{1,5\}$. Their union is $\{1,2,5\}$. Thus both sides equal $\{1,2,5\}$.

For the second law, $B\cap C=\{4,5\}$, so $A\cup(B\cap C)=\{1,2,3,4,5\}$. Also $A\cup B=\{1,2,3,4,5,7\}$, and $A\cup C=\{1,2,3,4,5,8\}$. Their intersection is $\{1,2,3,4,5\}$, again giving the same set. Check: the elements $6,7,8$ are excluded from this last intersection because $6$ is in neither union, $7$ is absent from $A\cup C$, and $8$ is absent from $A\cup B$; the five elements $1,2,3,4,5$ occur in both unions.

De Morgan’s Laws and Complements

Theorem (De Morgan’s laws): For all subsets $A,B\subseteq X$, $$ (A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c. $$

Proof. Fix $x\in X$. The first equality follows because $x\in(A\cup B)^c$ if and only if $x\notin A\cup B$. By the definition of union, this is equivalent to saying that $x\notin A$ and $x\notin B$. That is equivalent to $x\in A^c\cap B^c$. For the second equality, $x\in(A\cap B)^c$ if and only if $x\notin A\cap B$. An element fails to belong to the intersection precisely when it fails to belong to at least one of the two sets. Thus $x\notin A$ or $x\notin B$, which is equivalent to $x\in A^c\cup B^c$. Each equivalence holds for every $x\in X$, proving both equalities. If $X=\varnothing$, all four sets in each equality are empty, so the statements hold in that case as well. $\square$

The change from union to intersection, and from intersection to union, is essential: the complement of “in $A$ or $B$” means “not in $A$ and not in $B$.” The complement of “in both $A$ and $B$” means “not in $A$ or not in $B$.” The complement of $A$ is still relative to $X$ in both formulas.

Worked Example: Applying De Morgan’s Laws

Take $X=\{a,b,c,d,e,f\}$, $A=\{a,b,d\}$, and $B=\{b,c,d,e\}$. Compute the two sides of each De Morgan identity.

First, $A\cup B=\{a,b,c,d,e\}$, so $(A\cup B)^c=\{f\}$. Next, $A^c=\{c,e,f\}$ and $B^c=\{a,f\}$. Their intersection is $A^c\cap B^c=\{f\}$, which agrees with the complement of the union.

For the other identity, $A\cap B=\{b,d\}$, so $(A\cap B)^c=\{a,c,e,f\}$. The union of the complements is $A^c\cup B^c=\{a,c,e,f\}$. Check: the only elements of $X$ absent from $A\cap B$ are $a,c,e,f$, exactly the elements in the union of the two complements. Elements outside $X$ are not considered in either complement.

Differences and Useful Rewrites

Proposition: For all $A,B,C\subseteq X$, $$ A\setminus B=A\cap B^c, \qquad A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C), \qquad A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C). $$

Proof. For any $x\in X$, membership in $A\setminus B$ means that $x\in A$ and $x\notin B$, which is precisely membership in $A\cap B^c$. For the second identity, $x\in A\setminus(B\cup C)$ means $x\in A$ and $x\notin B\cup C$. The latter condition means $x\notin B$ and $x\notin C$. Together, these conditions say $x\in A\setminus B$ and $x\in A\setminus C$, or $x\in(A\setminus B)\cap(A\setminus C)$. For the third identity, $x\in A\setminus(B\cap C)$ means $x\in A$ and $x\notin B\cap C$. The latter condition means $x\notin B$ or $x\notin C$. Hence $x\in A\setminus B$ or $x\in A\setminus C$, which is exactly membership in $(A\setminus B)\cup(A\setminus C)$. Since each equivalence holds for every $x$, all three equalities follow. $\square$

Worked Example: Removing Two Sets

Let $X=\{0,1,2,3,4,5,6\}$, $A=\{0,1,2,3,5\}$, $B=\{1,4,5\}$, and $C=\{2,4,6\}$. Check the identity $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$.

Combining the removed sets gives $B\cup C=\{1,2,4,5,6\}$. The elements of $A$ not in this union are $0$ and $3$, so $A\setminus(B\cup C)=\{0,3\}$. Separately, removing $B$ from $A$ leaves $A\setminus B=\{0,2,3\}$, and removing $C$ leaves $A\setminus C=\{0,1,3,5\}$. The elements common to these two results are $0$ and $3$, so their intersection is $\{0,3\}$.

Check: the only elements of $A$ that are in neither $B$ nor $C$ are $0$ and $3$. They are exactly the elements in both $A\setminus B$ and $A\setminus C$, confirming the equality from the membership definition.

A Common Error and a Reliable Check

A frequent mistake is to assume that set difference distributes over intersection in the same way it distributes over union. In fact, the correct identity is $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$, not an intersection on the right.

For a concrete counterexample, let $X=\{1,2\}$, $A=\{1,2\}$, $B=\{1\}$, and $C=\{2\}$. Since $B\cap C=\varnothing$, the left side $A\setminus(B\cap C)$ is $A\setminus\varnothing=\{1,2\}$. But $A\setminus B=\{2\}$ and $A\setminus C=\{1\}$, whose intersection is $\varnothing$, not $\{1,2\}$. Replacing that incorrect intersection by a union gives $\{2\}\cup\{1\}=\{1,2\}$, as the proved identity requires.

For a general identity, the membership method is usually more dependable than visual intuition. Write down what it means for an arbitrary $x$ to belong to the left side. Translate each operation into “and,” “or,” or “not,” and then compare the resulting condition with membership in the proposed right side. For finite sets, calculating both sides independently is a useful additional check; it can reveal an error in a calculation, although it cannot replace a proof for arbitrary sets.

Check Your Understanding

Use membership conditions to justify your answers, and remember that complements are relative to the stated underlying set.

For $A,B,C\subseteq X$, prove $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ by testing an arbitrary $x\in X$.
Write $A\setminus(B\cap C)$ using only differences and a union, and explain why the union appears.
If $X=\{1,2,3,4\}$ and $A=\{1,3\}$, calculate $A^c$. What would change if the underlying set were $\{1,2,3,4,5\}$?
Give a finite-set example that disproves the incorrect identity $A\setminus(B\cap C)=(A\setminus B)\cap(A\setminus C)$.
Prove $(A\cup B)^c=A^c\cap B^c$ by translating membership on both sides into conditions on $x$.