Set laws let us rewrite expressions without changing their elements. To justify a law, compare membership on both sides. Each object must belong to the left-hand set exactly when it belongs to the right-hand set.

Two search filters are equivalent when they return exactly the same records for every allowed input. Similar-looking filter names alone do not establish equivalence.

Let A, B and C be subsets of a fixed universal set U. All complements below are relative to this same U. The symbol ⇔ means if and only if: a transition is valid in both directions. To prove a set equality, compare membership for an arbitrary object x.

• Identity: $A\cup\varnothing=A$.
• Distribution: $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$.

Choose an arbitrary object x. Each ⇔ in the chain below can be read in both directions. The chain shows that x belongs to one union exactly when it belongs to the other. Because x was arbitrary, the two unions have the same elements.

For an arbitrary object x, compare membership in the left-hand set.

Expand the definition of union; the equivalence holds in both directions.

Swapping the two alternatives does not change whether at least one is true.

Use the definition of union in reverse.

Every object belongs to one union exactly when it belongs to the other, so the sets are equal.

$\{1,2\}\cap(\{1\}\cup\{3\})=(\{1,2\}\cap\{1\})\cup(\{1,2\}\cap\{3\})$.

The left side is {1}. On the right, the two intersections are {1} and the empty set; their union is also {1}.

If $U=\{1,2,3\}$, $A=\{1\}$ and $B=\{2\}$, then .

Only 3 is absent from both A and B within this U.

$\{1,2\}\setminus\{2,3\}=\{1\}$, while $\{2,3\}\setminus\{1,2\}=\{3\}$.

These sets provide a counterexample to commutativity of set difference.

A law is proved by chasing an arbitrary element through both sides. It is disproved by one choice of sets where the two sides differ.

• A set identity is proved by a chain of statements each read in both directions.
• Commutativity, associativity, distribution, absorption and De Morgan hold for all sets.
• Difference is not commutative, and one pair of sets shows it.
• A false law is refuted by a single counterexample, never by a failed attempt at a proof.

Great work! You now know how to:

• Prove a set identity by chasing an arbitrary element through both sides
• Name the standard laws and apply them to simplify an expression
• Refute a proposed law with a single counterexample