Recipe

Prove set equality by double inclusion

Use when: you must prove A=B for sets described by a rule, where listing and comparing every element isn't possible

Goal: both subset directions established, together showing A=B

Taught in Set equality and double inclusion

1. 1

   Let x be an arbitrary, unspecified element of A. Using the rule that defines A, derive that x also satisfies the rule that defines B.

   Example

   Let A=\{x\in\mathbb Z: x \text{ is a multiple of } 10\} and B=\{x\in\mathbb Z: x \text{ is a multiple of } 2 \text{ and a multiple of } 5\}. Let x\in A, so x=10k for some integer k. Then x=2(5k), a multiple of 2, and x=5(2k), a multiple of 5. So x\in B.

   Why: this establishes A\subseteq B, the first of the two directions double inclusion requires.

2. 2

   Now let x be an arbitrary element of B, and using B's rule, derive that x also satisfies A's rule.

   Example

   Let x\in B, so x=2m and x=5n for integers m,n. Since 2 and 5 share no common factor, x being a multiple of both forces x to be a multiple of 10. So x\in A.

   Why: this establishes B\subseteq A, the direction the first half alone never covers.

3. 3

   Once both A\subseteq B and B\subseteq A are shown, conclude A=B. Neither direction alone is enough.

   Example

   A\subseteq B (Step 1) and B\subseteq A (Step 2) together give A=B.

   • both directions were shown — A=B.
   • only one direction was shown — the proof establishes containment only, not equality.

   Why: two sets are equal exactly when each contains the other, the double-inclusion principle this section states.