Topology: Finite Intersection Property (Omake)

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. ]

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.

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.

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.

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.

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.