Prove $|(S_1 \cup S_2 \cup S_3)^c| =|U| - (|S_1| + |S_2| + |S_3|) + (|S_1 \cap S_2|+ |S_1 \cap S_3| + |S_2 \cap S_3|) - |S_1 \cap S_2 \cap S_3|$

Question

$U$ stands for the Universe and $c$ denotes the complement.

Proof:

Let $X_0 = |U| \\ X_1 = (|S_1| + |S_2| + |S_3|) \\ X_2 = |S_1 \cap S_2|+ |S_1 \cap S_3| + |S_2 \cap S_3|) \\ X_3 = |S_1 \cap S_2 \cap S_3| \\ W:= X_0 - X_1 + X_2 - X_3.$

Let $x \in S_1 \cap (S_2 \cup S_3)^c.$ Then $W$ counts $x$ once in $X_0$ and subtracts it once in $|X_1|: 1 - 1 = 0.$

Let $x \in S_1 \cap S_2 \cup (S_3)^c.$ Then $W$ counts $x$ once in $X_0$, subtracts it twice in $X_1$ and adds it once in $|X_2|: 1 - 2 + 1 = 0.$

Let $x \in S_1 \cap S_2 \cap S_3.$ Then $W$ counts $x$ once in $X_0$, subtracts it thrice in $X_1$, adds it thrice in $X_2$ and subtracts it once in $|X_3|: 1 - 3 + 3 - 1 = 0.$

The above covers the cases when $x \in S_1$, $x \in S_1 \cap S_2$ and $x \in S_1 \cap S_2 \cap S_3$. We are missing one more case: $x \in (S_1 \cup S_2 \cup S_3)^c$. Here $W$ counts $x$ once. Thus $|(S_1 \cup S_2 \cup S_3)^c| = X_0 - X_1 + X_2 - X_3.$

Do you agree with this proof? Thanks.

Edit: The sets $S_1, S_2, S_3$ correspond to the sets $A, B, C$ in the picture.

Answer 1

For starters, the final step of the proof is confusing. You state that "we're missing one more case: $x \in (S_{1} \cup S_{2} \cup S_{3})^{c}$." Since you've thus far been discussing cases for the RHS, this line implies that the case in which $x$ belongs to the LHS is a separate case with respect to the RHS cases. But what you're trying to show is that the RHS cases collectively cover all scenarios in which $x$ belongs to the LHS, and in a way such that $x$ is counted once. So this is a perplexing statement.

Perhaps more importantly, the conclusion that "Here, $W$ counts $x$ once," is a statement which is unjustified due to the fact that the cases which you consider aren't explicitly connected to the original problem. In other words, you're connecting certain cases to a desired result, when no such connection has been made. It's like saying "Consider some cases in which the RHS equals 1. Now we're missing a final case: The LHS equals 1. Therefore the RHS equals 1, so the LHS = RHS." See how some very important connections are missing?

It's also a bit difficult to analyze your proof in full detail because of the approach. Beginning with a case-by-case breakdown of $x$ belonging to various sets, whose relevance aren't explicitly connected to the original problem, and then analyzing the number of ways in which $x$ is counted in each scenario is an unnecessarily brutal way of going about it. It goes far deeper into detail and cases than you need it to.

In certain extreme cases, I believe that this kind of approach is somewhat inevitable, because the only feasible alternative options are even more involved and lengthy. But the level of abstraction at which the fundamental set-theory tools no longer do the trick is far above the level of this problem. So let's simplify the method of proof. Then we won't have to bother ourselves with pesky details that are burdensome to the eye.

We can start by getting rid of the compliment sign:

$$|S_{1} \cup S_{2} \cup S_{3}|^{c} = |U| - |S_{1} \cup S_{2} \cup S_{3}|.$$

Now, we can break down $|S_{1} \cup S_{2} \cup S_{3}|$ using the inclusion-exclusion principle: [1]

$$|S_{1} \cup S_{2} \cup S_{3}| = |S_{1}| + |S_{2}| + |S_{3}| - (|S_{1} \cap S_{2}| + |S_{2} \cap S_{3}| + |S_{1} \cap S_{3}|) + |S_{1} \cap S_{2} \cap S_{3}|.$$

Simple plug and chug with the above into the former expression gives the answer we're looking for:

$$|S_{1} \cup S_{2} \cup S_{3}|^{c} = |U| - (|S_{1}| + |S_{2}| + |S_{3}|) + (|S_{1} \cap S_{2}| + |S_{2} \cap S_{3}| + |S_{1} \cap S_{3}|) - |S_{1} \cap S_{2} \cap S_{3}|.$$

[1] https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle