Set identities: distributive and De Morgan laws
Intersection spreads over union the way multiplication spreads over addition. Which rules like that hold for sets, and how can anyone be sure a proposed rule holds for every choice of sets?
Where you are 15 in Sets
Why this exists
In arithmetic, a(b + c) = ab + ac lets one expression be rewritten as another. Sets built with \cup, \cap and complement need rules of the same kind. “Not in either list” and “not in the first and not in the second” describe the same things; “in A, and in B or C” is the same as “in A and B, or in A and C”. Rules like these, true for every choice of sets, are set identities, and each one turns out to be a law of logic in disguise.
Definition
Throughout, A, B, C are subsets of a stated universal set U, and A^{c} is the complement of A in U, as in Union, intersection and complement.
A set identity is an equation between two expressions built from set letters, U, \varnothing, \cup, \cap and complement, that holds for every choice of the sets. Since sets are equal when they have the same elements (Subsets, proper subsets and equal sets), it says both sides always contain the same elements.
The distributive laws. Intersection distributes over union, and union over intersection:
De Morgan’s laws for sets. The complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements:
Membership table. For an expression in n set letters, a membership table has one row for each way an element can sit relative to the letters, 2^{n} rows in all, with 1 for “in” and 0 for “out”. Each further column records whether an element of that row is in the set heading the column. It is a truth table with 1 and 0 in place of T and F.
Intuition
In Figure 1, an element of A \cap (B \cup C) is in A and in at least one of B, C: the two lenses A \cap B and A \cap C taken together.
In Figure 2, the overlap of A \cup B and A \cup C is all of A, plus whatever lies in both B and C.
De Morgan’s laws are about what lies outside. Outside both loops is where “outside A” and “outside B” overlap (Figure 3). Outside the lens is everything outside at least one loop (Figure 4).
A diagram shows one arrangement, so it suggests an identity without proving it. Three circles cut U into eight regions, one for each in/out pattern, and these are the eight rows of a membership table (Figure 5).
Results
Every set law is a logic law. Fix x \in U and write a, b, c for the statements x \in A, x \in B, x \in C. Then x \in A \cup B is a \lor b, x \in A \cap B is a \land b, and x \in A^{c} is \neg a, while x \in U is always true and x \in \varnothing always false. So each identity below matches a Logical equivalence, with \cup for \lor, \cap for \land, complement for \neg, U for T and \varnothing for F.
- Identity: A \cup \varnothing = A and A \cap U = A, from P \lor \text{F} \equiv P and P \land \text{T} \equiv P.
- Domination: A \cup U = U and A \cap \varnothing = \varnothing, from P \lor \text{T} \equiv \text{T} and P \land \text{F} \equiv \text{F}.
- Idempotent: A \cup A = A and A \cap A = A, from P \lor P \equiv P and P \land P \equiv P.
- Complement: A \cup A^{c} = U and A \cap A^{c} = \varnothing, from P \lor \neg P \equiv \text{T} and P \land \neg P \equiv \text{F}.
- Double complement: (A^{c})^{c} = A, from \neg\neg P \equiv P.
- Commutative: A \cup B = B \cup A and A \cap B = B \cap A, from the same laws for \lor and \land.
- Associative: (A \cup B) \cup C = A \cup (B \cup C) and (A \cap B) \cap C = A \cap (B \cap C), from the same laws for \lor and \land.
- Distributive: the two laws above, from P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R) and P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R) in logic.
- De Morgan: the two laws above, from \neg(P \lor Q) \equiv \neg P \land \neg Q and \neg(P \land Q) \equiv \neg P \lor \neg Q.
- Absorption: A \cup (A \cap B) = A and A \cap (A \cup B) = A, from P \lor (P \land Q) \equiv P and P \land (P \lor Q) \equiv P.
The associative laws let a union or intersection of three sets be written without brackets, as A \cup B \cup C. Several of these were met in Union, intersection and complement, and absorption in Subsets, proper subsets and equal sets.
Membership tables decide identities. Two expressions in finitely many set letters are equal for all sets exactly when their columns agree in every row. If they disagree in some row, sets with one element placed as that row says make the two sides different.
Why it is true
The translation. For x \in U,
The outer steps are the definitions of \cap and \cup. The middle step is the distributive law for statements: both sides are true exactly when a is true and at least one of b, c is true. The two sets have the same elements, so they are equal. For De Morgan,
where the middle step is De Morgan’s law for statements. Every law in Results is proved this way: translate, apply the logic law, translate back.
Membership tables. Proof. Whether x is in A \cup B, A \cap B or A^{c} depends only on whether x is in A and in B. Building an expression one operation at a time, whether x is in it depends only on its in/out pattern for the letters, which is its row. If two expressions agree in every row, each x \in U is in both sides or in neither, so the sides are equal. If they disagree in some row, let U = \{1\} and put 1 into exactly the letters marked 1 in that row. Then 1 is in one side and not the other, so the equation is not an identity. \square
Worked examples
A membership table for the second distributive law
Prove A \cup (B \cap C) = (A \cup B) \cap (A \cup C) with a membership table.
SolutionWrite L for the left side and R for the right. Three letters give 2^{3} = 8 rows. L is 1 when A or B \cap C is 1. R is 1 when A \cup B and A \cup C are both 1: a 1 under A or B, and a 1 under A or C.
| A | B | C | B \cap C | L | R |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
In row 010, for instance, A \cup C is 0, so R is 0. The L and R columns agree in all eight rows, so the identity holds for all sets.
De Morgan on the divisors of 36
Let U = \{1, 2, 3, 4, 6, 9, 12, 18, 36\}, the positive divisors of 36. Let A be the even ones and B the multiples of 3. Check both De Morgan laws.
SolutionHere A = \{2, 4, 6, 12, 18, 36\} and B = \{3, 6, 9, 12, 18, 36\}, so A^{c} = \{1, 3, 9\} and B^{c} = \{1, 2, 4\}.
Since A \cap B = \{6, 12, 18, 36\}, we get (A \cap B)^{c} = \{1, 2, 3, 4, 9\}, and A^{c} \cup B^{c} is the same set: the divisors that are not multiples of 6.
Since A \cup B = \{2, 3, 4, 6, 9, 12, 18, 36\}, we get (A \cup B)^{c} = \{1\}, and A^{c} \cap B^{c} = \{1\} too. Only 1 is neither even nor a multiple of 3.
De Morgan for three sets
Prove (A \cup B \cup C)^{c} = A^{c} \cap B^{c} \cap C^{c}.
SolutionProof. By the associative law, A \cup B \cup C = (A \cup B) \cup C, a union of the two sets A \cup B and C. De Morgan’s law for two sets gives
Applying it again to (A \cup B)^{c} gives (A^{c} \cap B^{c}) \cap C^{c}, which the associative law lets us write as A^{c} \cap B^{c} \cap C^{c}. \square
Repeating the same two steps extends the law to any finite number of sets.
Simplifying with the laws
Simplify (A \cup B)^{c} \cup (A^{c} \cap B).
SolutionBy De Morgan, (A \cup B)^{c} = A^{c} \cap B^{c}, so the expression is
Both parts are intersections with A^{c}, so the first distributive law, read right to left, gives A^{c} \cap (B^{c} \cup B). By the commutative and complement laws B^{c} \cup B = U, and by the identity law A^{c} \cap U = A^{c}. The expression simplifies to A^{c}: outside A, whether inside B or not.
Refuting a proposed identity
Decide whether A \cap (B \cup C)^{c} = (A \cap B^{c}) \cup (A \cap C^{c}) holds for all sets.
SolutionThe left side L translates to a \land \neg(b \lor c), which is a \land \neg b \land \neg c by De Morgan: in A and in neither B nor C. The right side R is (a \land \neg b) \lor (a \land \neg c): in A and missing at least one of B, C. Both sides are 0 in every row with A = 0, so only four rows matter:
| A | B | C | L | R |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
The rows 110 and 101 disagree, so this is not an identity. Row 110 gives a counterexample: U = \{1\}, A = B = \{1\}, C = \varnothing. Then B \cup C = \{1\}, so L = \varnothing, while A \cap C^{c} = \{1\} makes R = \{1\}.
Every 1 in L is a 1 in R, so L \subseteq R always. The correct identity has an intersection in the middle:
In at least two of three sets
Prove that for all sets
Call the left side L and the right side R.
| A | B | C | L | R |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
The columns agree, so the identity holds. L is 1 when some pair of letters are both 1: the element is in at least two of the sets. R is 1 when every pair contains a 1, that is, when at most one letter is 0, which with three letters is again “in at least two”.
Boundaries
One stated universal set. Laws with complements, U or \varnothing hold when every complement in the equation is taken in the same U.
For all sets, not for some. A \cup B = A \cap B is true when A = B but false for A = \{1\}, B = \varnothing, so it is not an identity.
The arithmetic parallel stops. Union distributes over intersection, but a + bc is not (a + b)(a + c) for numbers. The set laws come from logic, where \lor and \land each distribute over the other.
Finitely many sets. A membership table with n letters has 2^{n} rows. For infinitely many sets there is no table; De Morgan’s laws still hold, proved by following one element, but that lies beyond this lesson.
Where this goes next
The proof that follows one element through each side, written as two subset arguments in prose, is Proving a set identity, where these laws meet set difference, A \setminus B = A \cap B^{c}. De Morgan’s law for several sets is how “none of the above” gets counted in Inclusion-exclusion for three or more sets, and derangements.
Exercises
Checking laws on particular sets
For Exercises 1 to 3, U = \{0, 1, 2, \dots, 9\}, A = \{0, 2, 4, 6, 8\}, B = \{0, 3, 6, 9\} and C = \{1, 2, 3, 4\}.
- Find A \cap (B \cup C) and (A \cap B) \cup (A \cap C).
- Find A \cup (B \cap C) and (A \cup B) \cap (A \cup C).
- Find (A \cup C)^{c} and A^{c} \cap C^{c}.
- Take U = \mathbb{R}, let A be the numbers with x < 2 and B those with x > 5. Find (A \cup B)^{c} and A^{c} \cap B^{c}.
Membership tables
- Prove (A \cap B)^{c} = A^{c} \cup B^{c} with a membership table.
- Prove A \cup (A^{c} \cap B) = A \cup B with a membership table.
- Decide whether (A \cup B)^{c} \cap C = C \cap (A^{c} \cup B^{c}) holds for all sets. If not, give a counterexample.
- Decide whether A \cap (B \cap C)^{c} = (A \cap B^{c}) \cup (A \cap C^{c}) holds for all sets. Compare Example 5.
- How many rows does a membership table need for an identity in four sets? In n sets?
Simplifying with the laws
Simplify each expression, naming the law used at each step.
- (A \cup B) \cap (A \cup B^{c})
- (A^{c} \cap B^{c})^{c}
- (A \cap B \cap C) \cup (A \cap B \cap C^{c}) \cup (A \cap B^{c})
- \big((A \cup B) \cap A^{c}\big)^{c}
Three sets and more
- Prove (A \cap B \cap C)^{c} = A^{c} \cup B^{c} \cup C^{c} from the two-set laws.
- Write \big((A \cup B) \cap C\big)^{c} so that every complement sits on a single letter.
- Let U = \{1, 2, \dots, 30\}, and let A, B, C be the multiples of 2, 3 and 5 in U. List A^{c} \cap B^{c} \cap C^{c} and write it as one complement.
- Prove A \cap (B \cup C \cup D) = (A \cap B) \cup (A \cap C) \cup (A \cap D) from the two-set distributive law.
Reasoning
- Show with a = 1, b = 2, c = 3 that a + bc = (a + b)(a + c) fails for numbers, and explain why A \cup (B \cap C) = (A \cup B) \cap (A \cup C) holds for sets.
- An equation between set expressions holds every time U has exactly one element, whatever the sets inside U. Explain why it is an identity.
- Apply the first distributive law to the sets A^{c}, B^{c}, C^{c}, take the complement of both sides, and use De Morgan’s laws to derive the second distributive law.
- Show that A \cup B = A \cap B holds exactly when A = B.
Answers
- Both are \{0, 2, 4, 6\}: B \cup C = \{0, 1, 2, 3, 4, 6, 9\}, A \cap B = \{0, 6\}, A \cap C = \{2, 4\}.
- Both are \{0, 2, 3, 4, 6, 8\}: B \cap C = \{3\}, A \cup B = \{0, 2, 3, 4, 6, 8, 9\}, A \cup C = \{0, 1, 2, 3, 4, 6, 8\}.
- Both are \{5, 7, 9\}: A^{c} = \{1, 3, 5, 7, 9\} and C^{c} = \{0, 5, 6, 7, 8, 9\}.
- Both are the numbers with 2 \le x \le 5: A^{c} is x \ge 2 and B^{c} is x \le 5.
- In rows 11, 10, 01, 00, both (A \cap B)^{c} and A^{c} \cup B^{c} read 0, 1, 1, 1. They agree.
- In rows 11, 10, 01, 00, A^{c} \cap B reads 0, 0, 1, 0, so the left side reads 1, 1, 1, 0, the same as A \cup B.
- Not an identity. The right side is C \cap (A \cap B)^{c}: in C and missing A or B; the left needs missing both. Rows 101 and 011 differ. Counterexample: U = A = C = \{1\}, B = \varnothing; the left side is \varnothing, the right side \{1\}.
- An identity. By De Morgan (B \cap C)^{c} = B^{c} \cup C^{c}, then distribute A \cap over the union. Example 5 had a union inside the complement.
- 2^{4} = 16 rows; 2^{n} in general, one for each in/out choice for each set.
- A. Distributive: A \cup (B \cap B^{c}); complement: A \cup \varnothing; identity: A.
- A \cup B. De Morgan: (A^{c})^{c} \cup (B^{c})^{c}; double complement: A \cup B.
- A. Distributive on the first two parts: (A \cap B) \cap (C \cup C^{c}) = A \cap B by the complement and identity laws. Then (A \cap B) \cup (A \cap B^{c}) = A \cap (B \cup B^{c}), which is A \cap U = A.
- A \cup B^{c}. De Morgan twice and double complement: (A^{c} \cap B^{c}) \cup A; commutative and distributive: (A \cup A^{c}) \cap (A \cup B^{c}); complement and identity: A \cup B^{c}.
- Proof. By the associative law and De Morgan, (A \cap B \cap C)^{c} = (A \cap B)^{c} \cup C^{c}, and De Morgan again gives (A^{c} \cup B^{c}) \cup C^{c}; associativity drops the brackets. \square
- (A^{c} \cap B^{c}) \cup C^{c}: De Morgan on the intersection, then on A \cup B.
- \{1, 7, 11, 13, 17, 19, 23, 29\}, the numbers divisible by none of 2, 3, 5; it is (A \cup B \cup C)^{c}.
- Proof. By associativity B \cup C \cup D = (B \cup C) \cup D. The distributive law gives \big(A \cap (B \cup C)\big) \cup (A \cap D), and applying it again inside gives the right side. \square
- 1 + 2 \cdot 3 = 7 but (1 + 2)(1 + 3) = 12. For sets, membership turns \cup into \lor and \cap into \land, and P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R) holds in all eight rows of its truth table.
- With one element, every row of the membership table is produced by placing that element as the row says. So the sides agree in every row, and by the membership table result they are equal for all sets.
- Start from A^{c} \cap (B^{c} \cup C^{c}) = (A^{c} \cap B^{c}) \cup (A^{c} \cap C^{c}) and take complements; equal sets have equal complements. The left becomes A \cup (B^{c} \cup C^{c})^{c} = A \cup (B \cap C), and the right becomes (A^{c} \cap B^{c})^{c} \cap (A^{c} \cap C^{c})^{c}, which is (A \cup B) \cap (A \cup C).
- If A = B, both sides are A. If A \cup B = A \cap B, then A \subseteq A \cup B = A \cap B \subseteq B, and likewise B \subseteq A, so A = B.