1
Every set law mirrors a logical law
De Morgan for sets follows from De Morgan for propositions applied to the membership condition. There is nothing new to memorise, only a translation.
Lesson · Sets, Relations, and Functions · Sets
Set Identities and Proofs
The set identities are Logic and Proof's logical equivalences in set notation. Prove them by double inclusion or by a chain of laws — and know when a Venn diagram is a case check and when it is only a picture.
(A ∪ B)‾ = Ā ∩ B̄ De Morgan
(A ∩ B)‾ = Ā ∪ B̄ De Morgan
A ∩ (B ∪ C) = (A∩B) ∪ (A∩C) distribution
A ∪ (A ∩ B) = A absorption
Four identities worth knowing
Core ideas
What this lesson establishes
Every identity here is a logical equivalence in disguise, which means Logic and Proof already did most of the work.
2
Double inclusion always works
Take an arbitrary element of each side and show it belongs to the other. Longer than a chain of laws, and impossible to get wrong.
3
A Venn diagram is a case check, not a method
Three circles show all eight membership patterns, so a correctly shaded three-set diagram does establish a three-set identity. It cannot be written as named steps, it does not extend to more sets, and the usual four-circle picture is missing regions — so it finds identities; the proof is still written.
The material
The identities and how to establish them
The laws, then both proof routes on the same example.
identity A ∪ ∅ = A A ∩ U = A
domination A ∪ U = U A ∩ ∅ = ∅
idempotent A ∪ A = A A ∩ A = A
complementation (Ā)‾ = A
commutative A ∪ B = B ∪ A A ∩ B = B ∩ A
associative (A ∪ B) ∪ C = A ∪ (B ∪ C)
distributive A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
De Morgan (A ∪ B)‾ = Ā ∩ B̄ (A ∩ B)‾ = Ā ∪ B̄
absorption A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A
complement A ∪ Ā = U A ∩ Ā = ∅
difference A \ B = A ∩ B̄
Set every one of these beside the corresponding line in “Logical Equivalence” in Logic and Proof and the correspondence is exact: ∪ for ∨, ∩ for ∧, overbar for ¬, U for T, ∅ for F. The last line is the most useful in practice, because it removes \ from an expression and leaves only operations the laws speak about.
Theorem · De Morgan for sets
(A ∪ B)‾ = Ā ∩ B̄ for all sets A, B inside a universe U.
(⊆) Let x ∈ (A ∪ B)‾. Then x ∈ U and x ∉ A ∪ B, so it is not the case that x ∈ A or x ∈ B. By De Morgan for propositions, x ∉ A and x ∉ B, so x ∈ Ā and x ∈ B̄, hence x ∈ Ā ∩ B̄.
(⊇) Let x ∈ Ā ∩ B̄. Then x ∉ A and x ∉ B, so x is in neither, so x ∉ A ∪ B, so x ∈ (A ∪ B)‾.
Both inclusions hold, so the sets are equal.
□
The second half is the first half read backwards, because every step used a biconditional. When that happens the two inclusions can be written as a single chain of ⟺, which is shorter and just as rigorous — provided every step really is reversible.
The chain-of-laws route
A \ (A ∩ B)
= A ∩ (A ∩ B)‾ difference law
= A ∩ (Ā ∪ B̄) De Morgan
= (A ∩ Ā) ∪ (A ∩ B̄) distribution
= ∅ ∪ (A ∩ B̄) complement
= A ∩ B̄ identity
= A \ B difference law
Six named steps, no arbitrary elements, and each line justified. This is the faster route once the laws are familiar, and it fails safely: a step you cannot name is a step you have not made.
Why a Venn diagram is not enough
A three-set Venn diagram shows eight regions, which is every possible membership pattern, so shading it does establish a three-set identity. What it does not do is generalise: there is no readable Venn diagram for five sets, and the usual four-circle picture is missing regions. The diagram is a device for seeing what is true, and the proof is still owed.
Interactive
Set algebra
Two expressions, one membership
Method
Proving a set identity
Pick the route by how many operations are involved.
1
Two or three operations? Chain the laws
Rewrite \ as ∩ with a complement first, then apply De Morgan, distribution and absorption, naming each.
2
Anything unfamiliar? Double inclusion
Take an arbitrary x in the left side and derive membership in the right, then reverse. It always works and needs no recall.
3
Watch for reversibility
If every step is a biconditional you may write one chain of ⟺ instead of two inclusions. If any step is one-way, you owe both directions.
4
To refute, find one element
A single element in one side and not the other disproves the identity. The lab's difference row is exactly this.
Identities
Score 0 / 0Choose the answer you can justify.
Prove A \ (B ∪ C) = (A \ B) ∩ (A \ C)
By the chain of laws, which is shorter than double inclusion here.
A \ (B ∪ C)
= A ∩ (B ∪ C)‾ difference law
= A ∩ (B̄ ∩ C̄) De Morgan
= (A ∩ A) ∩ (B̄ ∩ C̄) idempotent, backwards
= (A ∩ B̄) ∩ (A ∩ C̄) commutative and associative
= (A \ B) ∩ (A \ C) difference law, twice
Step three is the one that looks like a trick. Replacing A by A ∩ A is legitimate because idempotence is an equality and may be used in either direction — and it is what lets the single A be shared between the two factors.
Common mistakes
1
Distributing a complement across an operation without flipping it(A ∪ B)‾ is Ā ∩ B̄, not Ā ∪ B̄. This is the same slip as the propositional one, and the lab separates the two in one click.
2
Treating a Venn diagram as a proof for arbitrarily many setsThree circles cover eight regions. Four circles do not cover all sixteen, so the usual four-set picture is not a case check at all.
3
Using a step you cannot nameEvery line of a chain proof should cite a law. "Rearranging" is where errors hide, and the fix is to write which law licenses the rearrangement.
Check your understanding
✓
Finish when you can prove an identity both ways.
Prove (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B) — both sides are A △ B — once by double inclusion and once by chaining laws. The second will be shorter; the first will be the one you can always produce.
Note: Sets under ∪, ∩ and complement form a Boolean algebra, exactly as propositions under ∨, ∧ and ¬ do. That is why the two lists of laws match line for line, and why the remarks about circuits in “Normal Forms and Boolean Algebra”, in Logic and Proof, apply here too.