In an article by Terrence Tao, Compactness and Compactification, which begins by stating some properties of finite sets $X$, the author writes the following:

(All sequences have constant subsequences) If $x_1,x_2,x_3,...\in X$ is a sequence of points in $X$, then there must exist a subsequence $x_{n_1},x_{n_2},...$ which is constant, thus $x_{n_1}=x_{n_2}=...=c$ for some $c\in X$. (This fact is sometimes known as the infinite pigeonhole principle.)

I am struggling to see what this means, and wondered why this is obvious.

For instance, take $X=\{1,2,3,4,5,6\}$, then let $(2,1,3,5,4,6)$ be some sequence of points in $X$. Then the only subsequences with the property written above are trivially $(2)$, $(1)$, ..., etc. Is this what the property is? In other words, is it an obvious, but not very interesting property, or am I missing something?

Additionally, how does it relate to the pigeonhole principle?

I am struggling to find an appropriate tag, so please feel free to edit and change the tags as you see fit.

  • 3
    $\begingroup$ Tao's sequences here are infinite sequences. Your supposed counterexample is finite. $\endgroup$ – Ethan Bolker Nov 20 '19 at 22:50
  • 1
    $\begingroup$ Did you notice the dots in "If $x_1,x_2,x_3,\dots\in X$"? That means we're talking about an infinite sequence, not a finite one. $\endgroup$ – Gerry Myerson Nov 20 '19 at 22:51
  • 1
    $\begingroup$ @EthanBolker Thank you for clarifying. I did not think I had produced a counterexample, but was trying to see what the theorem meant, obviously wrongly using finite sequences. $\endgroup$ – Benjamin Nov 20 '19 at 23:22
  • 1
    $\begingroup$ @GerryMyerson Thank you, Gerry, I realise now that it is an infinite sequence. $\endgroup$ – Benjamin Nov 20 '19 at 23:24

A sequence in $X$ is a function from $\Bbb N$ to $X$, where we denote the value of $n$ by $x_n$ for short.

A sequence has a value for every $n \in \Bbb N$, they go on forever.

And if we have a sequence $(x_n)$ define for each $x \in X$: $N_x=\{n \in \mathbb{N}: x_n =x\}$ and note that

$$\bigcup_{x \in X} N_x = \Bbb N$$ as every $n$ has a value in $X$ and so is in a unique $N_x$. And if all $N_x$ were finite, so would the union be as $X$ is finite, contradiction; so some $N_x$ is infinite, and writing $N_x=\{n_1, n_2, \ldots\}$ in increasing order we have a constant subsequence with value $x$.

The pigeonhole principle is clear: we have infinitely many pigeons going into finitely many "holes", so one hole must have infinitely many pigeons in it.

  • $\begingroup$ Thank you for your superb and lucid response! $\endgroup$ – Benjamin Nov 20 '19 at 23:19
  • $\begingroup$ @Benjamin you’re welcome. $\endgroup$ – Henno Brandsma Nov 21 '19 at 4:52

What this statement is saying is that when you take an infinite sequence of values from a finite sequence, it has a constant subsequence. For example if you define the sequence {2,1,2,1,2,1...} where the 2s and 1s alternate forever, this theorem you’ve pointed out claims that there is some infinite constant subsequence. And an obvious choice would be to take the subsequence {2,2,2,2...} simply taking the odd indexed terms. This property may seem pretty trivial but in many situations it can be very useful. While it’s not likely to ever happen, one hypothetical proof for the twin prime conjecture would be to find an infinite sequence of twin primes whose inverses have a convergent sum. If there were only finitely many twin primes, than any infinite sequence of twin primes would necessarily have an infinite constant subsequence, and this constant subsequence would force the sum of the inverses to diverge. The property is related to the pigeonhole principle because both theorems show that when we put a certain set of things into a certain set of boxes, at least one box must have a certain number of things put in it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.