# Subsequence equivalence: $(a_n)$ and $(b_n)$ in $\{0,1\}^\mathbb N$ are equivalent if they have some subsequences which are equal

Define two sequences $(a_n), (b_n) \in \{0, 1\}^\mathbb{N}$ are equivalent iff they have some subsequences that are equal.

How many equivalence classes are there? Is it uncountable?

It might be countable (unlikely but possible), since each equivalence class is uncountable.

Motivation: I wanted to count the number of "essentially different" ways for a rational sequence to converge to $0$. Two convergent sequences are equivalent iff they have some subsequences that are equal. I could determine that there are uncountably many of these by this construction:

$$a_n\neq b_n \in \left(\frac{1}{2^{n+1}}, \frac{1}{2^{n}}\right]\cap\mathbb{Q}$$ then any two such constructed $(a_n)$, $(b_n)$ will be inequivalent but convergent to $0$. There are clearly $\mathbb{N}^\mathbb{N}$ of them.

• Uncountably many, assign to each such representative subsequence the associated number in binary representation. (Of the form $\sum_{n=1}^{\infty}\frac{1}{2^n}a_n$) May 24, 2018 at 12:02

This isn't an equivalence relation, because it is not transitive. For instance, the sequence $a_n=0$ is "equivalent" to the sequence $b_n=\frac{1+(-1)^n}2$, which is in turn "equivalent" to $c_n=1$. Yet, $a$ and $c$ are not "equivalent".

• What is $-1$? The sequences only obtain $0$ and $1$. May 24, 2018 at 12:01
• Thanks, @AsafKaragila, now mine do too.
– user562983
May 24, 2018 at 12:03

There are two things here:

1. The relation is not even transitive. Consider the constant sequence $1$, the constant sequence $0$, and any alternating sequence $(a_n)$. Then $(a_n)$ is equivalent to both $(1)$ and $(0)$, but they are not equivalent to one another.

2. You are forgetting that the sequences of rationals can obtain many more values than just $\{0,1\}$.

But now to your actual question, note that there is a family $\{A_r\subseteq\Bbb N\mid r\in\Bbb R\}$ such that for $r\neq t$, the intersection $A_r\cap A_t$ is finite. Use this family to find $2^{\aleph_0}$ essentially different subsequences of $\frac1n$ which converge to $0$.

• I know about 2. My thought was to take a sequence $(b_n)\in \{0, 1\}^\mathbb{N}$, then obtain $a_n = (2+(-1)^{b_n})/2n$. Then if two binary sequences are inequivalent, then their induced sequences would also be inequivalent. May 24, 2018 at 13:16
• Well, your idea is not just about "a subsequence" then, it's about having an infinite subsequence with the same indexing. This is not enough to force the relation to be an equivalence relation, of course. May 24, 2018 at 14:47