Verifying Set Identities Through Element Membership

Hello! Last time, you computed set operations by asking whether each element belonged in the result. Today, that same question becomes a way to prove something: if two set expressions contain exactly the same elements, they are equal. If you can find an element that belongs to one expression but not the other, they are unequal.

We will use this method to verify an identity and to refute two convincing-looking false ones. It is more powerful than checking a few numerical examples, because a proof must work for every choice of the sets involved.

From a membership check to a proof

Suppose $A$ and $B$ are subsets of a fixed universe $U$. To prove that two expressions $S$ and $T$ are equal, choose an arbitrary $x\in U$ and establish

“Arbitrary” matters: you have not chosen a convenient number or assumed anything about where $x$ lies. Your reasoning must work wherever it lies. The phrase if and only if covers both directions: membership in $S$ guarantees membership in $T$, and membership in $T$ guarantees membership in $S$.

For example, swapping the order of a union cannot change its members:

Written out, the argument is short:

The middle step works because “or” is inclusive: it does not matter which alternative is stated first. Since this holds for every $x\in U$, the sets are equal. Computing, say, $\{1,2\}\cup \{2,3\}$ in both orders would illustrate the claim, but would not prove it for all sets.

For a second example, watch TrevTutor’s How to do a PROOF in SET THEORY. The selected portion proves $(A\cup B{)}^c=A^c\cap B^c$ by handling the two directions separately.

The video writes two subset proofs. Our union argument used a chain of “if and only if” statements instead. These are two presentations of the same requirement: neither side may have a member missing from the other.

Verify an identity with nested operations

Consider a claim involving difference and intersection:

It is tempting to manipulate the symbols by appearance alone. Membership gives you a safer route. Let $x\in U$ be arbitrary, and translate the left-hand side one operation at a time:

The important distinction is in the second line. Not being in both $B$ and $C$ means that $x$ is missing from at least one of them. It does not mean that $x$ is missing from both. The third line keeps the condition $x\in A$ in either possibility; the final line translates those possibilities back into set notation. Because every step works in both directions for an arbitrary $x$, the identity is verified.

This gives you a practical approach to an unfamiliar identity: expand each side into conditions about $x$, then check whether those conditions really say the same thing. A Venn diagram can help you anticipate an answer, but the membership argument explains why it holds.

Refute an identity by finding one mismatched member

Now replace the union on the right-hand side with an intersection:

The previous proof suggests where to look. Choose an $x$ that belongs to $A$ and $B$, but not $C$. It is not in $B\cap C$, so it belongs to the left-hand side. Yet it is not in $A\setminus B$, so it cannot belong to the intersection on the right. This one membership pattern shows what goes wrong.

To turn the pattern into an explicit counterexample, let

Then $B\cap C=\varnothing$, giving $A\setminus (B\cap C)=\{1\}$. But $A\setminus B=\varnothing$, so $(A\setminus B)\cap (A\setminus C)=\varnothing$. The proposed identity is false. Unlike a proof, a refutation needs only one valid choice of sets for which the sides differ.

Read Example 9.6 in CMSC 250: Set Theory and Proofs for another refutation. It uses a larger finite example; concentrate on the single kind of member that makes the sides unequal, rather than on every number in its rosters.

Here is the mismatch in membership language. On the left, $x\in A$ is enough to put $x$ in $A\cup (C\setminus B)$, even if $x\in B$. On the right, membership in $B$ removes $x$ from $(A\cup C)\setminus B$. That difference is the reason a counterexample exists; the particular numbers merely make it concrete.

A reliable decision rule is: for a proposed equality, compare membership of an arbitrary element on both sides. If the conditions match in both directions, you have a proof. If they can differ, describe the mismatched membership pattern and choose explicit sets that realise it. A few matching examples cannot establish an identity, but one counterexample can refute it.

Next, you will use unions and intersections in a different way: counting members of finite sets without counting overlaps twice.