Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Prove a set identity by element-chasing

Use when: you need to prove two set expressions are equal and no shortcut identity already covers the claim directly

Goal: a two-direction proof that every element of the left side lands in the right side, and every element of the right side lands in the left

Taught in Proving set identities two ways

Quick recipe

  1. Take an arbitrary element of the left side
  2. Track x through the definitions until it lands in the right side
  3. Repeat the whole argument in reverse
  4. Conclude equality from both containments together
  1. 1

    Let x be an arbitrary element of the left-hand set, then unpack exactly what that membership means using the definitions of the operations involved.

    Example

    For A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C): let x \in A \setminus (B \cup C), so x \in A and x \notin B \cup C.

    Why: an arbitrary x stands for every possible element at once, so anything proved about it holds for the whole set, not just one instance.

  2. 2

    Rewrite the membership condition step by step, using the definitions of union, intersection, difference, or complement, until it matches the right side exactly.

    Example

    x \notin B \cup C means x \notin B and x \notin C. Combined with x \in A, that gives x \in A \setminus B and x \in A \setminus C, so x \in (A \setminus B) \cap (A \setminus C).

    • the resulting chain of "and"/"or" conditions matches the right side's definition — x is shown to be in the right side, finishing this direction.
    • the conditions don't obviously match yet — keep unpacking one operation at a time instead of guessing the final form.

    Why: this shows every element satisfying the left side's condition also satisfies the right side's condition, which is exactly the subset containment \subseteq in this one direction.

  3. 3

    Start over with an arbitrary element of the right side, and track it through the same definitions until it lands back in the left side.

    Example

    Let x \in (A \setminus B) \cap (A \setminus C), so x \in A, x \notin B, and x \notin C. Then x \notin B \cup C, so x \in A \setminus (B \cup C).

    Why: showing one side is contained in the other only proves containment in one direction, not equality, so the reverse argument is a separate, necessary step.

  4. 4

    State that the left side sits inside the right side and the right side sits inside the left side, so the two sets are equal.

    Why: two sets are equal exactly when each one is contained in the other, which is what both directions together establish.

Common mistakes

  • Proving only one direction and treating that as a complete proof of equality.
  • Skipping a definition instead of unpacking it, such as leaving "x not in B union C" without also stating x is not in B and not in C.
  • Losing track of which side is which partway through the reverse direction.
  • Citing an identity by name mid-proof instead of unpacking definitions, which quietly switches to the algebraic method instead.