Denis Gorodkov

set-equality

10 min read

Set equality and element-chasing proofs

This write-up covers one idea and one proof technique, both of which appear repeatedly through the course. The idea: what it means for two sets to be equal. The technique: element-chasing.

1. Set equality

Recall the mental model from lecture: a set is an answering machine. Feed it any object, and it answers yes () or no (). The set says yes to and no to everything else.

Two sets are equal when they give exactly the same answers to every question.

Idea

means: for every object , .

This is called the principle of extensionality. It says a set is completely determined by its elements. Nothing else — not the order in which you list them, not whether you list them more than once — matters at all:

These are the same set. Order and repetition in the listing are irrelevant; only membership counts.

The principle also tells you what doesn’t count as a proof. Writing requires verifying that exactly the integers and satisfy — not just gesturing at the formula.

2. Subsets

Definition. is a subset of , written , if every element of is also an element of :

Geometrically, the Venn diagram for shows ‘s circle sitting entirely inside ‘s.

Two important boundary cases: the empty set is a subset of every set (vacuously — there is nothing in that fails to be in ), and every set is a subset of itself.

Now notice: to say , we need the answering-machine condition to hold in both directions. That is exactly the same as saying and .

Idea

.

This reformulation is the key to proving set equalities. Instead of one unwieldy task — checking all objects simultaneously — you have two containment problems, each of which has a clear proof structure.

3. The element-chasing template

To prove , you chase a generic element: you take an arbitrary element , and you show — using only the definition of and logic — that must belong to . The is completely generic; it represents every possible member of at once.

Combining the two containments, every proof of has the same skeleton:

Proof that :

Let . Argue from the definition of that .

Let . Argue from the definition of that .

The labels and indicate which containment you are proving. The proof ends after both directions are established; the symbol (called a tombstone or halmos) signals the conclusion.

The rough-work heuristic

Before writing a proof, ask: what does actually mean? Unpack every set-builder expression and every operation (, , , ) into a statement purely in terms of and logical connectives (, , , ). Then ask: which logical steps get me from here to where I need to go? That chain of reasoning is your rough work. Only once you have it do you write the clean proof.

4. The four regions

Before working through examples it is worth naming the four regions that appear in every two-set Venn diagram.

In this diagram:

  • — the left crescent (in but not )
  • — the lens (in both)
  • — the right crescent (in but not )
  • Everything outside both circles — in neither

Every element of the universe belongs to exactly one of these four regions. This partition into cases is what drives the case analysis in most element-chasing proofs.

5. Worked example: the absorption law

Claim. For any sets and : .

Drawing the picture first

The Venn diagram makes this plausible at once: is the lens sitting inside ‘s circle. Unioning with something already inside cannot reach any new territory.

The shaded region is — and, as we are about to prove, it is also . The diagram doesn’t establish this (it only shows one configuration of and ), but it gives us confidence and tells us what the proof must say.

Rough work

Direction : show every lies in .

What does mean? By definition of union: or .

  • Case 1: . Done — already.
  • Case 2: . By definition of intersection, and . In particular . Done.

Direction : show every lies in .

What does require? That or . We have , so the first disjunct holds immediately.

Clean write-up

Proof. : Let . By definition of union, either or . In the first case directly. In the second case, means and , so in particular . Either way .

: Let . Since , we have or , which is precisely .

Rough work vs. write-up

The rough work and the clean proof contain exactly the same ideas. The write-up drops the exploratory commentary (“what does this mean?”), orders the logical steps cleanly, and removes the self-doubt. The tombstone signals that both directions are complete. Writing the rough work first is not a shortcut — it is the proof; the write-up is just its final form.

6. A more involved example: distributivity of over

Claim. For any sets , , : .

This is exactly the distributive law, mirroring for numbers. The proof requires tracking an or (from ) inside an and (from ), which calls for a case split.

Rough work

Direction : Let . Unpack: and , i.e., or .

  • Case 1: . Then and , so , and therefore . ✓
  • Case 2: . Then and , so , and therefore . ✓

Direction : Let . Unpack: or .

  • Case 1: . Then and . Since , we have . So and , giving . ✓
  • Case 2: . Then and , so , and again . ✓

Venn diagram check

The shaded region below is : the part of that overlaps with at least one of or .

Clean write-up

Proof. : Let . Then and . From the union, either or . If , then . If , then .

: Let . If , then and , so . If , then and , so .

7. What a Venn diagram does — and doesn’t — do

Venn diagrams are an excellent tool. Use them to:

  • generate a guess about whether an identity looks plausible,
  • plan the case structure of your proof (each region corresponds to a logical case),
  • check your answer after completing a proof.

But a diagram is not a proof. It shows one specific configuration of the sets — drawn with circles of particular sizes and positions. A proof must establish the identity for all possible sets: ones that barely overlap, ones where , ones where , ones where . No diagram covers all of these at once.

The element-chasing technique works because it reasons about a generic element — one about which you know only what the definition tells you, nothing more. It therefore applies to every configuration simultaneously.

A common confusion

A diagram can suggest a result is false by exhibiting a counterexample: draw and with no overlap and observe that some candidate identity fails in that picture. That is a valid argument (a counterexample), because a single configuration suffices to disprove a universal claim. What a diagram cannot do is prove a universal claim.

Graph View