INCLUSION EXCLUSION PRINCIPLE FREE

This creates an overcount once again, and so we continue, alternating sign as we go, until we reach the intersection of all of the sets in the collection. However, now we have subtracted those elements contained in three or more sets too many times, so we have to add back the sum of the three-way intersections. This may be explained intuitively by stating that if we simply take as the cardinality of the union the sum of the cardinalities of the constituent sets, then we have counted those elements that lie in more than one of those sets more than once, so we subtract the sum of the cardinalities of two-way intersections. The general form of the theorem for a collection A 1, ⋯, A n. The upshot is that the combinatorial inclusion-exclusion principle is equivalent to the statement that exact sequences of vector spaces have trivial Euler characteristic! This little formula that we teach in primary or secondary school turns out to be intimately connected with one of the fundamental tools of homological algebra and the abstract approach to linear algebra.The inclusion-exclusion principle is a theorem of set theory relating to the cardinality of a set defined as the union (mathematics) of a finite, or at most countable, collection of sets. Of course, as I said before we could have proved it from the other side, but that would require a lot of messy hands-on work with bases and such. Then all these dimensions we’re talking about are cardinalities of various subsets of the sets we started with, and the combinatorial inclusion-exclusion principle follows.

INCLUSION EXCLUSION PRINCIPLE FREE

These free vector spaces will have nontrivial intersections corresponding to the nonempty intersections of the sets, and we’ve got canonical basis elements floating around to work with. Given a collection of sets, just construct the free vector space on each of them. First add the dimension of each subspace, then subtract the dimension of each pairwise intersection, then add back in the dimension of each triple intersection, and so on.įrom here it’s the work of a moment to derive the combinatorial inclusion-exclusion principle. The result is that the dimension of a sum of subspaces is the alternating sum of the dimensions of the -fold intersections. The th map consists of including each -fold intersection into each of the -fold intersections it lies in, with positive and negative signs judiciously sprinkled throughout to make the sequence exact. The th term consists of the direct sum of the intersections of the subspaces, taken at a time. We include the dimensions of the individual subspaces, exclude the dimensions of the pairwise intersections, and include back in the dimension of the triple intersection.įor larger numbers of subspaces we can construct longer and longer exact sequences. Taking the Euler characteristic and juggling again we find

We stick these maps all together to have the long exact sequence Now is injective, and its image is exactly the kernel of. The image of is exactly the kernel of, but this time it has a nontrivial kernel itself! Now we need another mapĭefined by. We use the pairwise intersections to cover the kernel by the mapĭefined by. Then the kernel contains triples like, , and. What about three subspaces, , and ? We start off again withĭefined by. Which is the inclusion-exclusion principle for two subspaces. Taking the Euler characteristic we find that On the other hand, its image is precisely the set of pairs that kills off. Now it’s clear that has a trivial kernel. But rather than talk about elements, let’s use the intersection to parametrize the kernel! We’ve got another linear map, defined by. Specifically, if and have a nontrivial intersection then it gives us a nontrivial kernel. This function is always surjective, but it may fail to be injective. It’s not bilinear - linear in each of and separately - which would mean bringing in the tensor product. Note carefully that this is linear as a function of the pair. This tells us that there’s a linear map defined by. Every vector in is the sum of a vector in and a vector in. Now we consider the sum of the subspaces. The thing to remember is that and might have a nontrivial intersection - their sum may not be direct. 1 Principle of inclusion and exclusion Very often, we need to calculate the number of elements in the union of certain sets. We’ll never really need that space, so we don’t need to give it a name. Let’s start with just two subspaces and of some larger vector space. We could argue directly in terms of bases, but it’s much more interesting to use the linear algebra we have at hand. Predictably enough, this formula is reflected in the subspaces of a vector space. In combinatorics we have a method of determining the cardinality of unions in terms of the sets in question and their intersection: the Inclusion– Exclusion Principle.

Inclusion exclusion principle