Pigeon Hole Principle And Infinite Sets

Question

Lemma: Let $(X,d)$ be a metric space and $K\subset X$ be compact. Define $A \subset K$ to be an infinite subset of $K$.Then we can can construct a decreasing chain of infinite subsets $A_{n} \subset A$, with an associated sequence $(x_{n})_{n\in\mathbb{N}}$ such that: $$ A_{n} \subseteq B\big(x_{n},\frac{1}{n}\big)$$

Proof: They use an earlier proposition:

{*} $(K,d)$ is complete, and for every $\epsilon>0$ there is a finite subet $I \subset X$ such that: $$[1] \qquad K \subset \bigcup \limits_{i \in I} B(x_{i},\epsilon) $$

• They then claim that the lemma above is provable by induction - supposing we have constructed some $A_{k} \subset \dots \subset A_{1} \subset A$, then by {*}, set $\epsilon = \frac{1}{k+1}$, then there is some finite $N$ such that: $$ [2] \qquad K \subset \bigcup \limits_{i=1}^{N} B\big(x_{i},\frac{1}{k+1}\big)$$

• Apparently the fact that $A_{k}$ is infinite means that, by the pigeon hole principle, there is an infinite subset $A_{k+1} \subset A_{k}$, and an element $x_{n+1} \in I $ such that $A_{k+1} \subset B\big(x_{k+1},\frac{1}{k+1}\big)$

Question:

• I'm very confused as to how the pigeon hole principle applies here (especially since I thought it's only really valid for finite sets, and won't I run into [vague, unspecified] cardinality issues with infinite ones? Essentially, especially given that this is just a subset relation in [2], I don't see why I can't just stuff everything into one open ball in the union?.

Answer 1

The "infinite pigeonhole principle" being used here is that if an infinite set $X$ is contained in the union of finitely many sets, then at least one of those sets must contain infinitely many points of $X$. (I don't know how common this terminology is. One book where it is used is Mathematics and Its History, Third Edition by John Stillwell, but there must be many others.)

In your lemma, let's consider how to start the induction. We know that $K$ is contained in the union of finitely many balls of radius 1. By the infinite pigeonhole principle, at least one of those balls must contain infinitely many points of $A$. We choose $A_1$ to be the intersection of $A$ with that ball. Then we cover $K$ with a finite collection of balls of radius $1/2$. One of those must contain infinitely many points of $A_1$. Take $A_2$ to be the intersection of $A_1$ with that ball. Dot dot dot.