Technique for proving Inclusion-Exclusion principle combinatorically

[CGandC]

This is a popular combinatorial proof for the Inclusion-Exclusion principle but I was wondering what kind of proof technique they use?

Initially I thought - since we have cardinalities on both sides of the equality , I thought we'd have to show a bijection exists between the set on the left side and the overall set on the right side, but this way is difficult here ( partly because it is not exactly clear what set the cardinalities on the right-hand side represent ).

Then I thought maybe we could use what's called " Combinatorial proof " ( which is essentially the same thing as building a bijection between both sides of the equation although not in a forward manner ) and for this I'd show how to calculate the number of elements on the left-hand side and the right-hand side and then show they're equivalent; but using this technique stumbles me again since a-priori we don't have an indication to what the number of elements on both sides of the equations might be or how to even calculate them.

Then I tried to think more about the proof above: what they are doing is to take an arbitrary element in ## \bigcup_{1 \leq i \leq n} A_i ## and show how many times it appears ( counts ) in the left-hand side and the right-hand side of the equation. But I don't exactly see how this proves that the equation above is valid since all they did prove is that x is counted the same on both sides of the equation. Also, What kind of proof technique they use? is the technique they use is a variant of " Combinatorial proof " ?

Note: In applying " Combinatorial Proof " we usually have an equation for the cardinalities of some sets, for example we could have a problem such as proving that ## { n \choose k } = { n \choose n-k } ## ( not the algebraic way); and the proof is done by showing each side of the equation is a different way to count the number of elements of the same set.
However note that in such an example we did not prove by doing the following: Take an arbitrary element x of some set S whose cardinality is ## { n \choose k } ##, count the number of times it appears ( counts ) in this set and showed it counts exactly the same number of times in the set whose cardinality is ## { n \choose n-k } ## ---- such proof method is only reflected in the proof above of Inclusion-Exclusion principle and I have not seen elsewhere.

 

[Office_Shredder]

I feel like you're trying too hard to put a label on a proof, which doesn't feel healthy. Mostly I think this is combinatorial - writing down the sum of m choose ks is combinatorial. Expanding ##(1-1)^m## is just algebra, but a pretty clever application of it.

 

[fresh_42]

But I don't exactly see how this proves that the equation above is valid since all they did prove is that x is counted the same on both sides of the equation.

We can list all elements in the union ##\cup A_i =\{x_1,\ldots,x_k\}## and perform the argument on every single ##x_j##. This means we have a well-defined function ##f: |\cup A_i| \longrightarrow \mathbb{N}_0## from the number of elements in the union to a certain number of elements on the right. The proof shows ##f(|\{x\}|)=1##, and ##f(|\{\}|)=0## is obvious. Your question can now be phrased as: Why is
$$
k=f(k)=f(|\{x_1,\ldots,x_k\}|) \stackrel{?}{=} \sum_j f(\{x_j\}) \stackrel{\text{proof}}{=} k\cdot 1=k
$$
Hence the equalities on the far most left and far most right imply equality in the middle.

Edit: Maybe the left most requires an induction to be rigorous: ##f(n+1)=f(n)+1.##

Also, What kind of proof technique they use? is the technique they use is a variant of " Combinatorial proof " ?

I think it can be called counting. It counts twice and observes that the results are the same. It is a direct proof.

 

[CGandC]

Q1: So by counting a set we we essentially prove there exists a bijection from that set to ##\mathbb{N}_0 ##? ( we just show existence, but not how the bijection is actually defined )

Q2: Also, I have a bit difficulty of seeing this but why ## k=f(k) ##?

 

[fresh_42]

Q1: So by counting a set we we essentially prove there exists a bijection from that set to ##\mathbb{N}_0 ##? ( we just show existence, but not how the bijection is actually defined )

It is not the bijection that makes the problem, since both sides are only sets of a single number. Of course, they are bijective. We probably could use the sets themselves, too, by translating the entire expression on the right in terms of a boolean algebra. But those minuses will be a nightmare. Nevertheless, it should be principally possible. The union as the entire set, and then the many subsets as a giant expression of unions and intersections. Looks again as an induction proof over the number of sets ##A_i.##

Q2: Also, I have a bit difficulty of seeing this but why## k=f(k) ##?

I think the key, and far easier than the approach in Q1 is actually to prove ##f(n+1)=f(n)+1## by induction. It means to examine what happens if we add one element to the union. The induction base is trivial: ##f(|\{x\}|)=f(1)=1=0+1=f(|\{\}|)+1.## Say ##\cup A_i=\{x_1,\ldots,x_n\}## and ##n## equals the right hand side of the function by induction hypothesis. We then consider ##A_{n+1}=\{x=x_{n+1}\}## with an additional element ##x\not\in\cup_{i=1}^nA_i .## All sums on the right have next to be considered, since they are one index longer now. However, ##A_{n+1}\cap A_i = \{\}## for all ##i\leq n##, hence only the first sum changes: ##\sum_{i=1}^{n+1}|A_i|=|A_{n+1}|+\sum_{i=1}^{n}|A_i|=1+\sum_{i=1}^{n}|A_i|## and with the unchanged other sums we formally get ##f(n+1)=f(n)+1.## Since ##f(1)=1, ## we have ##f(k)=k## for any ##k##.

This must be brought into some order and my clumsy argument should be written more carefully, but I think it contains all formal steps now. But it is really very formal.

 

[CGandC]

Ok thanks! , I think I'll have to digest this for awhile. Are you familiar with another theory proved almost the same way as in the proof above? maybe it'd help if I'd see more proofs with this kind of pattern.