On this page
When you first encounter discrete mathematics, proofs can feel like a maze. A classic example is the question: prove that if A ∪ B = A ∩ B, then A = B.
While it is tempting to try and draw a picture or rely on intuition, formal mathematics requires a rigorous argument. The standard way to prove that two sets are equal is a method known as "element chasing" or double inclusion (1).
What is element chasing?
In set theory, two sets are defined as equal if they contain exactly the same elements. To prove that A = B, we must prove two things:
Every element of A is also in B (meaning A is a subset of B, written as A ⊆ B).
Every element of B is also in A (meaning B is a subset of A, or B ⊆ A).
Element chasing gets its name because you take an arbitrary, unnamed element (usually called x) from one set and "chase" it through a series of logical steps until you prove it must belong to the other set.
Educational psychologists suggest that breaking down a complex problem into a structured sequence of rules helps manage cognitive load during learning (2). By always following the same two-part template for set equalities, you remove the guesswork of how to start a proof.
How to prove A ∪ B = A ∩ B implies A = B
Let us apply this framework to our target problem. We are given the premise that A ∪ B = A ∩ B. Our goal is to prove A = B.
Part 1: Prove A ⊆ B
Step 1: Let x be an arbitrary element of A (written as x ∈ A).
Step 2: By the definition of a union, if x is in A, it is definitely in the combined set A ∪ B. So, x ∈ A ∪ B.
Step 3: We are given that A ∪ B = A ∩ B. Since x is in the union, it must also be in the intersection. So, x ∈ A ∩ B.
Step 4: By the definition of an intersection, any element in A ∩ B must be in both A and B. Therefore, x ∈ B.
Conclusion: We started with an arbitrary element in A and showed it must be in B. Therefore, A ⊆ B.
Part 2: Prove B ⊆ A
Step 1: Let y be an arbitrary element of B (written as y ∈ B).
Step 2: By the definition of a union, if y is in B, it is in A ∪ B. So, y ∈ A ∪ B.
Step 3: Using our premise again, A ∪ B = A ∩ B. Therefore, y ∈ A ∩ B.
Step 4: By the definition of an intersection, y must be in both sets. Therefore, y ∈ A.
Conclusion: We started with an element in B and showed it is in A. Therefore, B ⊆ A.
Since we have shown both A ⊆ B and B ⊆ A, we have proven that A = B.
Why not just use a Venn diagram?
Venn diagrams are fantastic for visualizing relationships, but they are not formal proofs. A Venn diagram shows a specific, idealized scenario. For instance, drawing two overlapping circles assumes that A and B have some elements in common, some unique to A, and some unique to B.
But what if A is empty? What if A is entirely contained within B? While you can sometimes draw all possible configurations, as the number of sets increases, the diagrams become impossible to manage. Element chasing relies on universal definitions, meaning the logic holds true whether the sets are infinite, empty, or overlapping.
What are the common mistakes in set equality proofs?
When writing these proofs in an exam, students often lose marks for a few predictable reasons:
Forgetting the second half: Students often prove A ⊆ B and stop, assuming the logic automatically works in reverse. However, one-way inclusion only proves that one set is smaller or equal to the other, not that they are identical.
Reusing the same variable: It is a good habit to use different variables (like x and y) for the two parts of the proof. Using x for both can lead to confusing circular logic if you accidentally reference a previous step.
Skipping definitions: Writing "x ∈ A ∪ B, so x ∈ A ∩ B" without explicitly stating "because we are given A ∪ B = A ∩ B" will cost you marks. Every leap must be justified by a stated premise or a mathematical definition.
Why this framework works for exams
Whether you are proving De Morgan's laws or solving three-set Venn problems with inclusion-exclusion, the element chasing template is foolproof. It stops you from staring at a blank page.
Whenever you need to practice these logical structures, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning.
Just as you use the formula 2ⁿ to find the number of subsets and the power set, element chasing is the algorithm for equality. Learn the template, state your definitions, and let the logic carry you to the conclusion.
