4
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 12 at 10:08
  • $\begingroup$ @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 $? $\endgroup$
    – Mr. Prince
    Feb 12 at 10:24
  • $\begingroup$ Do you really mean $\{ a_{ni} \}$, or should it be $\{ a_{n_i} \}$? $\endgroup$
    – Martin R
    Feb 12 at 10:29
  • 1
    $\begingroup$ @MartinR You're right, it should be the latter. I'll correct it. $\endgroup$
    – Mr. Prince
    Feb 12 at 10:51
  • 1
    $\begingroup$ 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$)? $\endgroup$
    – Martin R
    Feb 12 at 11:05

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Clean proof, this is quite inline with my intuitive picture of the problem. $\endgroup$
    – Mr. Prince
    Feb 12 at 11:42
1
$\begingroup$

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

ADDENDUM :

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Martin R
    Feb 12 at 11:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mr. Prince
    Feb 12 at 11:18
  • $\begingroup$ I added that interpretation too , @MartinR , though OP title indicates my earlier interpretation ! Now OP Comment too is confirming that ! $\endgroup$
    – Prem
    Feb 12 at 11:23
  • $\begingroup$ @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 $. $\endgroup$
    – Mr. Prince
    Feb 12 at 11:57
  • $\begingroup$ 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 ? $\endgroup$
    – Prem
    Feb 12 at 14:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .