Question on proving set equalities using binary representations.

56 Views Asked by At

Recently, I had to prove something which rested on the set equality $(A - B) \cap C = (A \cap C) - (B \cap C)$, and found this question in which a user shows a method of proving such equalities by associating each set with a power of 2 and "populating" it with all integers between $0$ and $2^n - 1$ (where n is the number of sets involved in the expressions) which contain the power of 2 associated to the set, then proceeding to test the equality on these sets.

I'd like to understand why this method actually proves the equalities and how it works but couldn't find more information about it (except for using binary strings as a way to encode subsets, but I wasn't able to find a connection).

1

There are 1 best solutions below

0
On BEST ANSWER

The process is essentially an extensive proof by cases. Suppose for instance we have 3 sets $A,B,C$ like in your example. You want to show that, given some element $x$, you have $x \in (A-B) \cap C$ iff $x \in (A \cap C) - (B \cap C)$. Then we can split this into $2^3$ cases, depending on whether $x\in A$ or not, whether $x\in B$ or not, and whether $x\in C$ or not. Each of these cases is assigned a number from $0$ to $7=2^3-1$. Then, you just check each case, which amounts to showing that the two sets "contain" the same numbers.