How would you prove an equality of sums of set cardinalities?

Question

I know how to prove equality in general sets using basic logic (for example: how to prove that for subsets $A,B,C$ of a universal set $U$, $A \cap(B \cup C)=(A \cap B) \cup(A \cap C)$). I also understand that to show equality in the cardinality between two sets, one must show a bijection between them. However, I don't understand how to prove something like: $|C \cap A|+|C \cap B|-|A \cap B| = |(C\cap A)\cup(C\cap B)|-|(A \cap B)\setminus C |$. I know this must be true after exhausting every possibility with venn diagrams so I guess this counts as a proof but I am wondering if there is a better way to prove these kinds of questions (more insightful proofs using basic logic).

Answer 1

We can proceed from left to right. Notice $A\cap B$ partitions as $\{(A\cap B)\cap C,(A\cap B)\setminus C\}$, so

$$ |C\cap A|+|C\cap B|-|A\cap B| = |C\cap A|+|C\cap B|-|A\cap B\cap C| - |(A\cap B)\setminus C| $$

Next, $A\cap B\cap C$ is $(C\cap A)\cap (C\cap B)$ so from the inclusion-exclusion principle

$$ |X\cup Y|=|X|+|Y|-|X\cap Y| $$

applied with $X=C\cap A$ and $Y=C\cap B$ the expression becomes

$$ =|(C\cap A)\cup(C\cap B)|-|(A\cap B)\setminus C|. $$

Answer 2

Subtraction of infinite cardinals is not well defined, but if we move each of the two negative terms to the opposite side we get $$ \tag{*} |C\cap A| + |C\cap B| + |(A\cap B)\setminus C| = |(C\cap A)\cup(C\cap B)|+|A\cap B| $$ which we have some chance of proving in general. (And when everything is finite it clearly implies your goal).

If you mark off each of those five sets on a Venn diagram you will find that every element in $C \cup (A\cap B)$ contributes one to each side of the equation, except that $A\cap B\cap C$ is in two sets on each side of the equality. So each side counts the same elements the same number of times.

To make this more symbolic than pointing to the Venn diagram, you can decompose each of the five areas into the basic regions of the Venn diagram: $$ C \cap A = (A\cap B\cap C) \cup (A\cap B^\complement \cap C) \\ C \cap B = (A\cap B\cap C) \cup (A^\complement \cap B\cap C) $$ and so forth. Each of the right-hand sides is a union of disjoint terms, so you can take the cardinality of each term separately: $$ |C \cap A| = |A\cap B\cap C| + |A\cap B^\complement \cap C| \\ |C \cap B| = |A\cap B\cap C| + |A^\complement \cap B\cap C| $$

After applying this to each of the five original terms, the two sides of (*) will be equal.