Topology: Finite Intersection Property (Omake)

The whole point of this article is the following seemingly trivial observation.

Theorem. A topological space X is compact if and only if it satisfies the finite intersection property (F.I.P.):

  • if \{C_i\} is a collection of closed subsets of X such that every finite intersection C_{i_1} \cap C_{i_2} \cap\ldots \cap C_{i_n}\ne\emptyset, then \cap_i C_i\ne\emptyset.

Proof.

Suppose X is compact. Then given a collection {Ci} of closed subsets of X with empty intersection, we have \cup_i (X-C_i) = X - \cap_i C_i = X so the open cover {XCi} has a finite subcover. This gives a finite collection of Ci with empty intersection.

The converse is just as easy: if F.I.P. holds and \{U_i\} is an open cover of X, then \cup_i U_i = X\implies \cap_i (X-U_i) = \emptyset. By F.I.P., there’s a finite collection (X-U_{i_1}) \cap \ldots\cap (X-U_{i_n})=\emptyset so \cup_n U_{i_n} = X is a finite subcover. ♦

Though this looks like a simple rephrasing of the definition of compact spaces, its underlying philosophy embodies an entire paradigm shift. [ Ok, that’s probably stretching it a little … ] The idea is that a closed subset of X typically represents a subset which satisfies certain nice conditions. Hence F.I.P. means that if every finite set of conditions can be satisfied by some object, then there’s some object that satisfies all conditions.

To make it a little more explicit, let’s prove the following.

Proposition. Suppose X_0, X_1, X_2,\ldots are non-empty compact Hausdorff spaces and f_n : X_n \to X_{n-1} is a collection of continuous maps:

\ldots \stackrel{f_{n+1}}\longrightarrow X_n \stackrel{f_n}\longrightarrow X_{n-1} \stackrel{f_{n-1}}\longrightarrow \cdots \stackrel{f_2}\longrightarrow X_1 \stackrel{f_1}\longrightarrow X_0.

Then there exists a sequence (\ldots, x_n, \ldots, x_2, x_1, x_0), where x_n \in X_n and f_n(x_n) = x_{n-1} for each n≥1.

Compactness is essential here. For example, if X_n = (0, \frac 1 n) and each fn is the inclusion map, then no such sequence exists since the intersection of all X>n is empty.

Proof.

Let X = \prod_{i=0}^\infty X_i which is compact by Tychonoff’s theorem. For each n≥1, let:

C_n = \{ (\ldots, x_2, x_1, x_0)\in X : f_i(x_i) = x_{i=1} \text{ for } 1\le i\le n\}.

Note that C_1 \supseteq C_2 \supseteq C_3 \supseteq \ldots . Also C_n is homeomorphic to Y_n := \prod_{i=n}^\infty X_i via the following mutually inverse maps:

\begin{aligned} C_n \to Y_n, &\quad (\ldots, x_n, \ldots, x_2, x_1, x_0)\mapsto (\ldots, x_n)\\ Y_n\to C_n, &\quad (\ldots, x_n) \mapsto (\ldots, x_n, f_n(x_n), f_{n-1}(f_n(x_n)), \ldots, f_1 (\ldots (f_n(x_n)))\ ).\end{aligned}

Thus C_n is non-empty and compact. Since X is Hausdorff, C_n is closed in XBy F.I.P., \cap_{n=1}^\infty C_n \ne\emptyset.

In particular, if Xn is finite with the discrete topology, then it’s compact Hausdorff and any map fn is continuous.

Corollary. If X_0, X_1, \ldots is a sequence of non-empty finite sets and f_n : X_n \to X_{n-1} is a collection of functions, then we can find (\ldots, x_2, x_1, x_0)\in \prod_n X_n such that f_n(x_n) = x_{n-1} for each n≥1.

Once again, a deceptively simple result. It looks obvious until one really attempts to prove it. [ Try proving it directly; bear in mind fn is not surjective in general. ]

blue-lin

Application: Infinite Four-Colour Theorem

We know the four-colour theorem for maps with finitely many countries, namely, any such map can be coloured by at most four colours such that no two countries which share a border have the same colour.

four_colours

What about a map with countably infinite number of regions? It’s not entirely clear that four colours suffice. One may be inclined to reason as follows: start with a region with finitely many countries – we know this can be coloured by four colours – then extend the colouring to other countries one at a time. The problem with this approach is that if we start with a bad colouring, then we may get stuck and be forced to retrace the steps, and how do we prove that retracing the steps must eventually lead to a valid colouring?

Compactness to the rescue.

Label each country as 1, 2, 3, … . Let Xn be the set of colourings of the map restricted to countries 1, …, n, with 4 colours such that two countries which share a border do not have the same colour. We have a map f_n : X_n \to X_{n-1} by ignoring the colour of the n-th country.

four_colours_more

Now, classical four-colour theorem tells us each Xn is non-empty. So by the above corollary, there’s a sequence (\ldots, x_2, x_1, x_0) with x_n \in X such that f_n(x_n) = x_{n-1} for each n. This corresponds to a colouring for the entire infinite map. ♦

Application: Infinite Tiling

Suppose we wish to fit a countably infinite set of shapes in a bounded region.

inf_tiling

Now we assume that every finite subset of shapes can be fitted within the bounded region without overlaps. [ We say that two shapes overlap if their interiors share a common point. Also a shape is within the bounded region as long as its interior is inside. ]

Claim. Under this assumption, the entire infinite class of shapes can be placed in the region without overlaps.

Proof.

Label the shapes by 1, 2, 3, … . For each n, let Xn be the set of ways to fit shapes 1 to n within the region. The map f_n : X_n \to X_{n-1} is given by removing shape n.

inf_tiling_proof

The placement of each shape i can be parametrised by coordinates (x_i, y_i) and a point on the unit circle representing its orientation. Thus Xn can be parametrised by 2n coordinates and n points on the unit circle, which forms a subset of R4n. This subset is clearly bounded; it’s also closed because its complement is open: e. g. if two shapes have overlapping interiors, then by perturbing all shapes a little, those two shapes still overlap. Thus, by the Heine-Borel theorem, Xn is compact. The above proposition tells us there’s a way to fit all shapes in. ♦

Note

Suppose we change the condition of overlap just a little: now two shapes are said to overlap if there’s a common point (even at the boundary). Then consider rectangles 1 × 2n, for n = 1, 2, 3, … , to be packed in the square 1 × 1. Since \sum_{n=1}^\infty 2^{-n} = 1, there’s a way to pack every finite set of rectangles in the square, but if we attempt to pack the entire infinite set, some of them must share an edge and thus overlap.

This entry was posted in Notes and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s