Michi’s blog

Michi’s blog » Homological Inclusion-Exclusion and the Mayer-Vietoris sequence

Homological Inclusion-Exclusion and the Mayer-Vietoris sequence

January 9th, 2009
10:44 pm

This blogpost is inspired to a large part by comments made by Rob Ghrist, in connection to his talks on using the Euler characteristic integration theory to count targets detected by sensor networks.

He pointed out that the underlying principle inducing the rule
$\chi(A\cup B) = \chi(A)+\chi(B)-\chi(A\cap B)$
goes under many names, among those \emph{Inclusion-Exclusion}, favoured among computer scientists (and combinatoricists). He also pointed out that the origin of this principle is the Mayer-Vietoris long exact sequence
$\cdots\to H_{n}(A\cap B)\to H_{n}(A)\oplus H_{n}(B)\to H_{n}(A\cup b)\to\cdots$

In this blog post, I’d like to give more meat to this assertion as well as point out how the general principle of Inclusion-Exclusion for finite sets follows immediately from Mayer-Vietoris.

Inclusion-Exclusion, and the passage from two sets to many

The basic principle of Inclusion-Exclusion says that if we have two sets, and , then the following relationship of cardinalities holds:
$|A\cup B| = |A| + |B| – |A\cap B$

A first proof would be performed by referring to an appropriate Venn
diagram, or by pointing out that if we try to count all the elements
of $A\cup B$ by adding the counts for and , then we’ve overcounted the elements of $A\cap B$ , and thus need to subtract these.

Now, this is good and convincing for the situation where we have just two sets, but what if we had a whole family? What if we had $A_{1},\dots,A_{n}$ ? Well, our old friend the complete induction rides to our rescue. Suppose we had already proven that for n-1 sets $A_{i}$ , the following formula holds:
$\left|\bigcup_{i\in\{1,\dots,n-1\}} A_{i}\right| = \sum_{k=1}^{n-1} (-1)^{1+k}\sum_{S\subseteq\{1,\dots,n-1\}, |S|=k}\left|\bigcap_{s\in S} A_{s}\right|$

If you think this formula is imposing, let me show you the first few ways it works out, so that you can get a feeling for it:

$|A_{1}\cup A_{2}| = |A_{1}| + |A_{2}| – |A_{1}\cap A_{2}$

$\begin{multline*} |A_{1}\cup A_{2}\cup A_{3}| = \\ |A_{1}|+|A_{2}|+|A_{3}|-|A_{1}\cap A_{2}|-|A_{1}\cap A_{3}|-|A_{2}\cap A_{3}|+\\ |A_{1}\cap A_{2}\cap A_{3}| \end{multline*}$

Here it starts becoming apparent why it is called the Inclusion-Exclusion formula: we include all elements from all sets, but then we’ve gotten too many elements from the pairwise intersections, so we exclude those, but then we’ve gotten too few elements from the triple intersections, so we re-include those, but then we’ve gotten too few elements from the quadruple intersections – and on it goes.

If our assumption holds, we can consider what the appropriate size of the union of different sets should be. We can pick one set, say $A_{n}$ , and treat it separately. Then, certainly, the union of the rest has size given by the formula, by our induction assumption. So, consider what happens when we add in the elements in $A_{n}$ . We then overcount all elements in any of the intersections $A_{i}\cap A_{n}$ , so we have to subtract those. But we then have undercounted all elements in any intersection on the form $A_{i}\cap A_{j}\cap A_{n}$ , so we need to add those back in. And so we go on, and for each intersection that occurred in the formula for n-1 sets, we find ourselves forced to add one new term, of the opposite sign, that counts the intersection of that old term with $A_{n}$ .

Thus, the new formula takes on the exact guise of the general formula we wanted to prove, since the terms involving $A_{n}$ are precisely indexed, in that formula, by the terms excluding $A_{n}$ , but with opposite signs.

Encoding set sizes homologically

So, now that we know that pairwise Inclusion-Exclusion implies the general Inclusion-Exclusion, let us take a look on how we can express Inclusion-Exclusion with homology. We note first of all that $H_{0}(X)$ counts the number of path-connected components of a space . This follows easily from a few properties. First, a basis for the -chains of is given by the points in . Second, two -chains are homologous precisely if there is a -chain whose boundary is the difference between those -chains. The boundary of a path is the difference of its endpoints, so we end up with two basis elements being homologous precisely if there is a path connecting them.

Thus, two -chain elements are homologous precisely if they’re in the same path-component of . So, the homology classes of -chains are precisely the path-connected components.

So, the -degree homology classes count path-components. How do we use that? Well … if we consider a finite set with the discrete topology – i.e. open sets are single points and any unions of single point sets, then a path is a continuous function $[0,1]\to X$ , i.e. one where the preimage of any open set is open. Thus, the preimage of any point is an open set. Suppose a path contains more than one point. Then we can partition the interval [0,1] into two disjoint open sets, by taking one set to be the preimage of one of the points, and the other set to be the preimage of everything else. However, the interval [0,1] is connected, which means that if there are two such open sets, one of them has to be empty.

Thus, the path-connected components of a discrete topological space are the points themselves. So if is discrete, then $H_{0}(X) = |X|$ .

Long exact sequences in homology and the Mayer-Vietoris sequence

It is a theorem from homological algebra that if we have a short exact sequence of chain complexes
$0\to A_{*}\to B_{*}\to C_{*}\to 0$
then there is a long exact sequence in homology given by
$\cdots\to H_{n}(A_{*})\to H_{n}(B_{*})\to H_{n}(C_{*})\to H_{n-1}(A_{*})\to\cdots$

Almost all interesting long exact sequences in topology are special cases of this particular fact. We will derive one interesting sequence: the Mayer-Vietoris sequence from this.

Take a topological space . The singular chain complex $C_{*}(X)$ forms a chain complex with $C_{n}(X)$ the free abelian group of -chains and the differential given by the usual formula.

Suppose we have two spaces: and . Then any -chain on $X\cap Y$ is an -chain on and an -chain on . So we get an inclusion map $C_{n}(X\cap Y)\to C_{n}(X)\oplus C_{n}(Y)$ by $\sigma\mapsto(\sigma,-\sigma)$ . We choose this sign instead of the image $(\sigma,\sigma)$ to make the next step cleaner. It is an injection because $C_{n}$ is a free abelian group, and the injections
$X\leftarrow X\cap Y\rightarrow Y$ are set maps on bases for the corresponding chain groups.

Compatibility of this map with the differential is almost as easy. If we first apply the differential and then map into the direct sum, we get the map $\sigma\mapsto d\sigma\mapsto(d\sigma,-d\sigma)$ . If we instead first map into the direct sum, and then apply the differentials, we get the map $\sigma\mapsto(\sigma,-\sigma)\mapsto(d\sigma,-d\sigma)$ . These are equal, and thus the map we’ve constructed is a chain map.

So, $C_{*}(X\cap Y)\to C_{*}(X)\oplus C_{*}(Y)$ is an injective map of chain complexes.

If we now have a pair of chains, we can construct a chain on the union of the two spaces. An -chain on is automatically an -chain on $X\cup Y$ . Similarly, an -chain on is automatically an -chain on $X\cup Y$ . So both $C_{n}(X)$ and $C_{n}(Y)$ inject into $C_{n}(X\cup Y)$ by the same kind of argument as with the injection $C_{n}(X\cap Y)\to C_{n}(X)$ .

The injections we get this way can be put together to a map $C_{n}(X)\oplus C_{n}(Y)\to C_{n}(X\cup Y)$ by, for instance, $(\sigma,\tau)\mapsto\sigma+\tau$ . I am going to fudge over the issue of whether the -chains on and form a generating set for the -chains on $X\cup Y$ , and just take it on faith that this works. The details are not particularly difficult – they are just obnoxiously long and annoying.

Now, given that we believe we can get a generating set by taking the union of the bases for the -chains on and , then this means that the map I gave above is surjective. Indeed, a basis element $\sigma\in C_{n}(X)$ is hit by the element $(\sigma,0)$ , and a basis element $\tau\in C_{n}(Y)$ is hit by the element $(0,\tau)$ .

This argument proves exactness at the first and last term of the short exact sequence
$0\to C_{*}(X\cap Y)\to C_{*}(X)\oplus C_{*}(Y)\to C_{n}(X\cup Y)\to 0$
and it remains to prove exactness at the middle term. So we need to prove that
$\mathrm{ker}((\sigma,\tau)\mapsto\sigma+\tau) = \mathrm{im}(\sigma\mapsto(\sigma,-\sigma))$

Now, since $\sigma+(-\sigma)=0$ , the inclusion of the image in the kernel is obvious. So, suppose now that $\sigma\in C_{n}(X)$ , $\tau\in C_{n}(Y)$ and $\sigma+\tau=0$ . Then, in $C_{n}(X\cup Y)$ , we know that $\sigma=-\tau$ . But then, $\tau\in C_{n}(X)$ since $\sigma\in C_{n}(X)$ and similarly $\sigma\in C_{n} (Y)$ since $\tau\in C_{n}(Y)$ . So $\sigma,\tau\in C_{n}(X\cap Y)$ and $\tau=-\sigma$ . But then this kernel element really is in the image of the inclusion we gave.

So this is a short exact sequence of chain complexes. It follows from the theorem of long exact sequences in homology that there is an associated long exact sequence, called the Mayer-Vietoris sequence:
$\cdots\to H_{n}(X\cap Y)\to H_{n}(X)\oplus H_{n}(Y)\to H_{n}(X\cup Y)\to H_{n-1}(X\cap Y)\to\cdots$

Putting it all together

Suppose is a discrete topological space. Then any continuous map from a -simplex $\Delta^{k}$ to is by necessity constant at one point. So all the singular simplices in are constant maps, and thus a basis for any -chain group is given by just the points in as such. The differential acts on such a constant map by sending it to an alternating sum of identical maps the cardinality of which is one more than the dimension of the simplex. So the differential vanishes at every other point in the chain complex, and is an isomorphism on the rest. But then we have exactly two possibilities for a homology computation:

Case 1: $C_{n}(X)\overset1\to C_{n-1}(X)\overset0\to C_{n-2}(X)$

Here, the kernel is the entire chain group. But so is the image. Thus the homology group is trivial.

Case 2: $C_{n}(X)\overset0\to C_{n-1}(X)\overset1\to C_{n-2}(X)$

Here, the kernel is trivial, but then again, so is the image. Thus, again, so is the homology group.

The only part not really covered by this is the homology group $H_{0}(X)$ , since this is computed from a diagram on the shape $C_{1}(X)\overset0\to C_{0}(X)\to0$ . So $H_{0}(X)$ behaves like we showed above, and is the only non-trivial homology group of the discrete space.

But then, the only bit that remains non-zero in the Mayer-Vietoris sequence is
$0\to H_{0}(X\cap Y)\to H_{0}(X)\oplus H_{0}(Y)\to H_{0}(X\cup Y)\to 0$

If we have a short exact sequence of free abelian groups, then this relates the number of basis elements in each of the groups with the structure of the sequence. Let our short exact sequence be given by $0\to A\to B\to C\to 0$ . then, by injectivity of the map $A\to B$ , the cardinality of a basis of the image in is equal to the cardinality of a basis for . By surjectivity of the map $B\to C$ , and by Noether’s theorem, the cardinality of a basis of is equal to the cardinality of a basis of the kernel of this map, plus the cardinality of a basis of . By exactness in the middle, this kernel basis is equal to the image basis from A. So, we have, writing |G| for the cardinality of a basis of the free abelian group , that |B| = |A|+|C| . Thus, |A|-|B|+|C|=0 .

And if we apply this to the Mayer-Vietoris sequence fragment we acquired, it follows that
$|X\cap Y| – |X| – |Y| + |X\cup Y| = 0$
and thus
$|X\cup Y| = |X| + |Y| – |X\cap Y|$

Algebra, Combinatorics, Homology and Homotopy, Mathematics, Topology

3 People had this to say...

And no link? Sure, some of the details are off (damn the edge cases) as noted in the comments, but it’s easy enough to patch.

This is ’cause I said I didn’t like Buffy, isn’t it?

It’s definitely because of Buffy!

Also, it’s because I wrote the thing up on the flight over – with the resulting lack of internet access – and didn’t bother to patch up ANY links to ANYWHERE of it. Thanks for the pointer though.

Btw: the right answer was “shut up, I like it!”

Homological Inclusion-Exclusion and the Mayer-Vietoris sequence

Inclusion-Exclusion, and the passage from two sets to many

Encoding set sizes homologically

Long exact sequences in homology and the Mayer-Vietoris sequence

Putting it all together

3 People had this to say...

Want your say?

About me

Travel plans

Blogroll

Family

Mathematician blogs

Archives

Michi’s blog

Homological Inclusion-Exclusion and the Mayer-Vietoris sequence

Inclusion-Exclusion, and the passage from two sets to many

Encoding set sizes homologically

Long exact sequences in homology and the Mayer-Vietoris sequence

Putting it all together

3 People had this to say...

Want your say?

About me

Travel plans

Categories

Blogroll

Family

Mathematician blogs

Archives