# If a sequence $\{ a_n \}$ is contained in a finite union of sets, then there is a subsequence of $\{ a_n \}$ contained in only one of the sets.

Edit: It has been pointed out that the title is stated ambiguously, please refer to the post by @Prem as to why. The title should actually be:

If a sequence $$\{ a_n \}$$ is contained in a finite union of sets, then there is a subsequence of $$\{ a_n \}$$ contained entirely in one of the sets.

In other words, if $$\{a_{n_i} \}$$ is the desired subsequence, then there is some $$1 \leq k \leq m$$ such that $$a_{n_i} \in E_k$$ for all $$i$$ where $$\{n_i\}$$ is the index selection sequence.

I'm working on a proof in which I would like to use the following result:

Suppose that a sequence $$\{ a_n \}$$ is contained in a finite union of sets $$E_1 \cup \dots \cup E_m$$, then there exists a subsequence $$\{ a_{n_i} \}$$ of $$\{ a_n \}$$ contained entirely in one of the $$E_k$$ where $$1 \leq k \leq m$$. Here $$\{n_i\}$$ is the index selection sequence.

However, I have trouble finding a proof of this result in any of my textbooks. I've looked around the internet as well but haven't found anything.

Intuitively, I'm certain that this is true, so I tried cooking up a proof of my own but I'm worried it might not be correct/rigorous:

Since the sequence $$\{ a_{n} \}$$ is infinite, we must have that it occurs infinitely often in at least one of the sets $$E_1, \dots, E_m$$. But this implies that there is some subsequence $$\{ a_{n_i} \}$$ contained entirely in one of the sets $$E_1, \dots, E_m$$.

• It's a bit hand-wavy, but it works. It's sort of like the infinite version of the pigeonhole principle. Here's an alternate, less handwavy approach: if $\{a_n\} \cap E_i$ is finite for each $i = 1, \ldots, m$, then$$\left|\bigcup_{i=1}^m \{a_n\} \cap E_i\right| \le\sum_{i=1}^m |\{a_n\} \cap E_i| < \infty.$$Now take the contrapositive. Feb 12 at 10:08
• @TheoBendit So essentially, if the sequence occurs finitely many times in each of the sets $E_1, \dots, E_m$ then the cardinality $$\left | \bigcup_{i=1}^m \{ a_n \} \cap E_i \right |$$ is finite. So the contrapositive would be that if said cardinality is infinite, then the sequence occurs infinitely often in at least one of the sets $E_1, \dots, E_m$? Feb 12 at 10:24
• Do you really mean $\{ a_{ni} \}$, or should it be $\{ a_{n_i} \}$? Feb 12 at 10:29
• @MartinR You're right, it should be the latter. I'll correct it. Feb 12 at 10:51
• Please clarify: The title states “... contained in only one of the sets.” Does that mean that you look for a subsequence which is contained in exactly one set $E_k$ (and no other set $E_j$ with $j \ne k$)? Feb 12 at 11:05

For a rigorous proof one should consider the sets of indices $$I_1, I_2, \ldots, I_m$$ defined by $$I_k = \{ n \in \Bbb N \mid a_n \in E_k \} \, .$$ Then $$I_1 \cup I_2 \cup \cdots \cup I_m = \Bbb N$$, so at least one of these sets contains infinitely many elements, say $$I_{K}$$.

Then there exists a bijection $$f: \Bbb N \to I_K$$, and $$\{ a_{f(n)} \}$$ is a subsequence of $$\{ a_n\}$$ with all elements contained in $$E_K$$.

• Clean proof, this is quite inline with my intuitive picture of the problem. Feb 12 at 11:42

The Proof is wrong because the Original Claim (Currently) itself is wrong.

OP is imagining Cases like $$E_1=\{1^{-n}\}$$ & $$E_2=\{2^{-n}\}$$ & $$E_3=\{3^{-n}\}$$ where some Sequence $$\{a_n\}$$ with some Sub-Sequence "might" have the Property.

That Property is actually false.

Counter Example 1 :
Let $$E_1=E_2=E_3$$ , then no matter what $$\{a_n\}$$ is , every Sub-Sequence occurs in all three Sets.

Counter Example 2 :
Let $$E_1=\{0,1\} , E_2=\{0,2\} , E_3=\{1,2\} , E_4=\{0,1,2\}$$ , & let $$\{a_n\}=\{0,1,2,0,1,2,\cdots\}$$ : every Sub-Sequence occurs in multiple Sets.

Counter Example 3 :
Let $$E_1=E_2=\{2^{-n}\}$$ & $$E_3=E_4=\{3^{-n}\}$$ & $$E_5=E_6=\{\text{what-ever}\}$$ , then no matter what $$\{a_n\}$$ is , every Sub-Sequence occurs in at least two Sets.

[[ The Answer might have to be updated when OP "updates" the Question to add the Criteria of Disjointedness , hence I will preemptively add that below ]]

## Updated Claim :

Sets $$E_m$$ are Pair-wise Disjoint , having no common elements.

## Updated Proof :

Consider the first Element & choose all Elements $$\{D_n\}$$ in the Sequence coming from the matching $$E_m$$.
When these Elements from $$E_m$$ are infinite , we have the necessary Sub-Sequence.
When these Elements are finite , then we can exclude those Elements to make the new $$\{a_n\}$$ where we will also exclude the matching $$E_m$$.

We now take the new first Element & choose Elements from the matching $$E_m$$.
When these Elements from $$E_m$$ are infinite , we have the necessary Sub-Sequence.
When these Elements are finite , then we can exclude those Elements to make the new $$\{a_n\}$$ where we will also exclude the matching $$E_m$$.

We can not repeat that arbitrarily , because we have finite number of Sets.
Eventually , we will have to reach the last Set standing.
That last Set standing contributes all the elements of the last $$\{a_n\}$$
What-ever Sub-Sequence we take now , we will we have the necessary Sub-Sequence from one $$E_m$$.

When we want something else & want to show that some Set $$E_m$$ contributes infinite elements to $$\{a_n\}$$ , to give a Sub-Sequence from one Set , the Proof is even easier.
If all the $$E_m$$ had contributed finite number of elements to $$\{a_n\}$$ , then we will have finite number of elements in total.
To get infinite number of elements towards $$\{a_n\}$$ , at least one $$E_m$$ should have contributed those infinite number of elements.
Choose those Elements from the earliest $$E_m$$ to get the necessary Sub-Sequence.

• Apparently my interpretation of the question is different from yours (but yours is definitely reasonable). I have left a comment at the question and asked for clarification. Feb 12 at 11:06
• You are absolutely right, the way I stated the question is ambiguous, sorry about that. I will add a paragraph in my post clarifying the question. Feb 12 at 11:18
• I added that interpretation too , @MartinR , though OP title indicates my earlier interpretation ! Now OP Comment too is confirming that !
– Prem
Feb 12 at 11:23
• @Prem Just to be absolutely clear, I do not necessarily want to require the sets to be pairwise disjoint. Although that does imply the result when overlap is acceptable. A quite basic application of the result could be as follows: Suppose that the sets $C_1, \dots, C_m$ are closed sets, and consider the the union $C = C_1 \cup \dots \cup C_m$. Let $x$ be an adherent point of $C$, then there is a sequence $\{ x_n \}$ contained in $C$ such that $x_n \rightarrow x$. The result implies that a subsequence of $\{ x_n \}$ is entirely contained in some $C_k$ and hence $x \in C$. Feb 12 at 11:57
• Oh ok , I got where you want you to use that ! Does the ADDENDUM address your requirement , @Mr.Prince , so that I can update the answer wording accordingly ?
– Prem
Feb 12 at 14:27