What It Means for Two Set Expressions to Be Equal
A set identity asserts that two expressions define the same set under the stated assumptions. For example, an identity involving \(A\), \(B\), and \(C\) is understood to hold for every allowed choice of those sets. The expressions may look different, but equality requires that every object belong to the left-hand set exactly when it belongs to the right-hand set.
The previous tutorial, “De Morgan's Laws,” used this principle to prove identities involving complements. The same approach works for unions, intersections, and other set expressions. Recall that \(x\in A\cup B\) means \(x\in A\) or \(x\in B\), while \(x\in A\cap B\) means \(x\in A\) and \(x\in B\). Translating symbols into these membership conditions turns a set equality into a statement in logic.
There are two useful ways to organize the proof. One is to start with an arbitrary object \(x\) and prove that membership on one side is equivalent to membership on the other. The other is to prove two inclusions: every element of the first set belongs to the second, and every element of the second belongs to the first. Equality by Double Inclusion, established earlier in this course, guarantees that these two inclusions prove equality.
A Membership Proof in Both Directions
A membership proof usually begins by fixing an arbitrary object \(x\). Translate membership in one side of the proposed identity, simplify the resulting condition, and translate it back into set notation. If this leads to the membership condition for the other side, the equivalence is established. Equivalences are useful here because each step preserves both directions: an object is in the first set if and only if it is in the last.
For example, in proving a distributive identity, the logical equivalence between “\(P\) and (\(Q\) or \(R\))” and “(\(P\) and \(Q\)) or (\(P\) and \(R\))” is the key step. It allows the membership condition to be rewritten without changing which objects satisfy it.
Theorem (Distributive Laws). Let \(A,B,C\) be sets. Then $$ A\cap(B\cup C)=(A\cap B)\cup(A\cap C) $$ and $$ A\cup(B\cap C)=(A\cup B)\cap(A\cup C). $$
Proof. We prove the first identity by comparing membership conditions. Let \(x\) be any object. By the membership characterizations of intersection and union, $$ \begin{aligned} x\in A\cap(B\cup C) &\Longleftrightarrow x\in A\text{ and }(x\in B\text{ or }x\in C)\\ &\Longleftrightarrow (x\in A\text{ and }x\in B) \text{ or }(x\in A\text{ and }x\in C)\\ &\Longleftrightarrow x\in(A\cap B)\cup(A\cap C). \end{aligned} $$ The middle equivalence is the distributive law for the logical connectives “and” and “or.” Since the equivalence holds for every object \(x\), the two sets have the same elements and are equal.
For the second identity, again let \(x\) be any object. Then $$ \begin{aligned} x\in A\cup(B\cap C) &\Longleftrightarrow x\in A\text{ or }(x\in B\text{ and }x\in C)\\ &\Longleftrightarrow (x\in A\text{ or }x\in B) \text{ and }(x\in A\text{ or }x\in C)\\ &\Longleftrightarrow x\in(A\cup B)\cap(A\cup C). \end{aligned} $$ Here the middle equivalence is the other distributive law for “and” and “or.” As this holds for every \(x\), the sets are equal. \(\square\)
These two identities have the same overall shape as the familiar distributive rules in algebra, but the operations are set union and set intersection. The proofs do not depend on the sets being finite, nor on any particular universe: they apply to arbitrary sets.
Worked Example: Evaluating Both Sides of a Distributive Identity
Let $$ U=\{-2,-1,0,1,2,3,4,5\},\quad A=\{-1,1,3,5\},\quad B=\{0,1,2,3\},\quad C=\{2,3,4\}. $$ We will check the identity \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\) for these particular sets.
First, the elements common to \(B\) and \(C\) are \(2\) and \(3\), so $$ B\cap C=\{2,3\}, \qquad A\cup(B\cap C)=\{-1,1,2,3,5\}. $$ Next, $$ A\cup B=\{-1,0,1,2,3,5\} $$ and $$ A\cup C=\{-1,1,2,3,4,5\}. $$ The elements common to these last two sets are \(-1,1,2,3,5\). Therefore, $$ (A\cup B)\cap(A\cup C)=\{-1,1,2,3,5\}=A\cup(B\cap C). $$ This calculation illustrates the identity for the chosen sets. The theorem, rather than this one calculation, establishes that it holds for every choice of \(A,B,C\).
Proving an Identity by Double Inclusion
When a membership equivalence becomes cumbersome, equality by double inclusion provides a clear structure. To prove \(X=Y\), first take an arbitrary \(x\in X\) and use the definitions to show \(x\in Y\). This proves \(X\subseteq Y\). Then take an arbitrary \(y\in Y\) and show \(y\in X\), proving \(Y\subseteq X\). Both directions are necessary: one inclusion alone proves only that one set is contained in the other.
The argument may feel similar to a membership equivalence, and mathematically the two methods express the same requirement. The double-inclusion format is particularly helpful when each direction has a different or asymmetric starting point. It also makes the proof's obligations visible: the first direction cannot be omitted merely because the second seems straightforward.
Theorem (Absorption Laws). Let \(A\) and \(B\) be sets. Then $$ A\cup(A\cap B)=A \qquad\text{and}\qquad A\cap(A\cup B)=A. $$
Proof. We first prove \(A\cup(A\cap B)=A\) by double inclusion. If \(x\in A\cup(A\cap B)\), then either \(x\in A\), or \(x\in A\cap B\). In the second case, membership in the intersection implies \(x\in A\). In either case, \(x\in A\), so $$ A\cup(A\cap B)\subseteq A. $$ Conversely, if \(x\in A\), then the union membership condition immediately gives \(x\in A\cup(A\cap B)\). Thus $$ A\subseteq A\cup(A\cap B). $$ Equality by Double Inclusion proves \(A\cup(A\cap B)=A\).
For the second identity, suppose \(x\in A\cap(A\cup B)\). Membership in the intersection implies \(x\in A\), so $$ A\cap(A\cup B)\subseteq A. $$ Conversely, suppose \(x\in A\). Then \(x\in A\cup B\) by the union membership condition, because \(x\in A\). Thus \(x\) belongs to both \(A\) and \(A\cup B\), which means \(x\in A\cap(A\cup B)\). Therefore $$ A\subseteq A\cap(A\cup B). $$ Equality by Double Inclusion gives \(A\cap(A\cup B)=A\). Both identities follow. \(\square\)
The absorption laws say that adding a restricted part of \(A\) to \(A\) does not enlarge it, and intersecting \(A\) with a set that already contains all of \(A\) does not remove any of its elements. The repeated appearance of \(A\) is important: the extra expression \(A\cap B\) is already contained in \(A\), while \(A\cup B\) already contains \(A\).
Worked Example: Simplifying an Expression by Absorption
Consider \(D\cup(D\cap E)\), where \(D\) and \(E\) are any sets. The absorption law gives $$ D\cup(D\cap E)=D. $$ The reason can also be checked directly. If \(x\in D\cup(D\cap E)\), then either \(x\in D\), or \(x\in D\cap E\); the second alternative also implies \(x\in D\). Thus the left side contains no element outside \(D\). Conversely, every \(x\in D\) belongs to the union because it satisfies the first alternative. The two sets therefore contain exactly the same elements.
For a concrete check, take \(D=\{m,n,p\}\) and \(E=\{n,q\}\). Then \(D\cap E=\{n\}\), so $$ D\cup(D\cap E)=\{m,n,p\}\cup\{n\}=\{m,n,p\}=D. $$ This calculation reflects the general reason: the intersection contributes only an element already in \(D\).
Turning Set-Builder Notation into a Proof
Sets described by conditions can often be compared without listing their elements. Suppose two sets have the same candidate domain \(U\), and one is described by a condition \(P(x)\) while the other is described by \(Q(x)\). The equality-of-condition-defined-sets result established earlier in this course says that it is enough to show \(P(x)\) and \(Q(x)\) are equivalent for every \(x\in U\). The set operations themselves translate directly into logical connectives.
Worked Example: Distributing Conditions over Integer Sets
Let \(U=\{-3,-2,-1,0,1,2,3,4\}\), and define $$ A=\{x\in U:x\text{ is even}\},\quad B=\{x\in U:x<0\},\quad C=\{x\in U:x\geq2\}. $$ The distributive identity says $$ A\cap(B\cup C)=(A\cap B)\cup(A\cap C). $$ We can see why it holds by examining the condition for an arbitrary \(x\in U\).
Membership on the left means that \(x\) is even and that either \(x<0\) or \(x\geq2\). In symbols, its condition is $$ x\text{ is even and }(x<0\text{ or }x\geq2). $$ This is equivalent to $$ (x\text{ is even and }x<0) \text{ or }(x\text{ is even and }x\geq2), $$ which is exactly the membership condition on the right. For a direct listing, \(A=\{-2,0,2,4\}\), \(B=\{-3,-2,-1\}\), and \(C=\{2,3,4\}\). Hence $$ A\cap(B\cup C)=\{-2,2,4\} $$ and $$ (A\cap B)\cup(A\cap C)=\{-2\}\cup\{2,4\}=\{-2,2,4\}. $$ The condition argument explains the identity generally; the finite calculation confirms the result for this particular choice.
Parentheses and Counterexamples
Parentheses indicate which operations are grouped together. In \(A\cap(B\cup C)\), first form the union \(B\cup C\), then intersect with \(A\). A proposed identity that drops or relocates a parenthesis may assert something quite different. The distributive law gives \((A\cap B)\cup(A\cap C)\), with \(A\) intersected with each part before their union; it does not permit an unrelated term to be moved outside those intersections.
A counterexample is an efficient way to show that a proposed general identity is false. To disprove an assertion that is meant to hold for all sets, it is enough to give one choice of sets for which the two sides differ. A useful strategy is to choose very small sets, then look for an object that appears on one side but not the other. This does not prove a true identity, but it can prevent an invalid claim from being treated as a theorem.
Worked Example: Finding a Counterexample to an Incorrect Identity
Consider the proposed identity $$ A\cap(B\cup C)=(A\cap B)\cup C. $$ It is not a distributive law: on the right, \(C\) is included without being intersected with \(A\). Choose the universe \(U=\{p,q,r\}\) and sets $$ A=\{p\},\qquad B=\varnothing,\qquad C=\{q\}. $$ Then \(B\cup C=\{q\}\), so $$ A\cap(B\cup C)=\{p\}\cap\{q\}=\varnothing. $$ On the other side, \(A\cap B=\varnothing\), and therefore $$ (A\cap B)\cup C=\varnothing\cup\{q\}=\{q\}. $$ The left side is empty while the right side contains \(q\), so the two sides are unequal. This single example disproves the proposed identity as a statement about all sets.
The correct distributive expression is \((A\cap B)\cup(A\cap C)\). In the same example it equals $$ \varnothing\cup(\{p\}\cap\{q\}) =\varnothing\cup\varnothing =\varnothing, $$ which agrees with \(A\cap(B\cup C)\). The example makes the role of parentheses visible: every part of the union must be intersected with \(A\).
Choosing a Proof Method
The two proof formats are related, but one may be more convenient than the other in a particular problem. A chain of membership equivalences is often concise when the same logical transformations apply in both directions. Double inclusion is often easier to organize when starting from either side gives a natural route to the other. In either format, the proof must justify each change using a membership definition or a previously established result.
| Method | What to establish | Useful when |
|---|---|---|
| Membership equivalence | \(x\in X\Longleftrightarrow x\in Y\) for arbitrary \(x\) | Set operations translate into a short chain of logical equivalences |
| Double inclusion | \(X\subseteq Y\) and \(Y\subseteq X\) | Each direction has a clear argument from its own starting set |
| Finite computation | Both sides have the same listed elements for chosen sets | Checking an example or illustrating a general law |
| Counterexample | One choice of sets makes the two sides unequal | Disproving a proposed identity intended to hold universally |
In each question, treat the sets as arbitrary unless particular sets are specified. Use the membership definitions of union and intersection, and make sure that a proposed proof establishes equality rather than only one inclusion.
Check Your Understanding
- State the two distributive laws for union and intersection.
- To prove \(X=Y\) by double inclusion, which two subset relations must be established?
- Let \(A=\{1,3\}\), \(B=\{2,3\}\), and \(C=\{3,4\}\). Compute \(A\cup(B\cap C)\) and \((A\cup B)\cap(A\cup C)\).
- Why does \(x\in A\cap(B\cup C)\) imply that \(x\in(A\cap B)\cup(A\cap C)\)?
- Give a brief explanation of why \(A\cup(A\cap B)=A\).
- What is sufficient to disprove a proposed identity that is claimed to hold for all sets?