How slow should a set grow in order to be countable? Let $R_n$ be the set of binary sequences of length $n$ and $A_n$ the subset of sequences having some property. The cardinality of $R_n$ is $2^n$ and the set of infinite binary sequences is uncountable
What should be the cardinality of $A_n$ to ensure that the subset of infinite binary sequences having such property is countable/uncountable?
 A: Based on your edit, it sounds like you're asking the following. For each $n$, we have some set $A_n$ of binary strings of length $n$; and you're asking about the set $\mathcal{A}$ of infinite binary strings, whose length-$n$ initial segments lie in $A_n$ for all $n$. For instance, if $A_n$ is the set of length-$n$ binary sequences with no "$11$"s, then "$00000000000...$" would be in $\mathcal{A}$. And so on.
If this is correct, then there is a description of when $\mathcal{A}$ is countable - but it's not as simple as a constraint on the growth of the $A_n$s; it has to do with how they interact with each other. And this leads to a complicated answer, which is more technical than you might be expecting. What I've written is really only a sketch - let me know if there are parts you don't understand, and I'll try to fill them in better.
First, let's make the picture a bit more understandable. $\mathcal{A}$ is really the set of paths through a certain binary tree $T$, whose length-$n$ nodes are exactly the strings in $A_n$. (I'm assuming here that the $A_n$s are nested appropriately - if $\sigma\in A_{n+1}$, the length-$n$ initial segment of $\sigma$ is in $A_n$. You only get into $A_{n+1}$ by going through $A_n$.) For simplicity, let's assume that we can always extend an element of $A_n$ to an element of $A_{n+1}$ - that is, there are no "dead ends" in the tree $T$.
One nice feature of this tree picture is that we can just describe the tree, and not have to describe each $A_n$ separately. E.g. if we take $A_n$ to be the set of binary sequences of length $n$ with no "$11$"s, we can more quickly describe this picture as "The tree of binary sequences with no "$11$"s." I'll do so below.
Now we can "prune" such a tree, as follows. Say a path $f$ is isolated if there is some finite sequence $\sigma$ such that $f$ is the only path going through $\sigma$; intuitively, this means that for some $n$, there's some $\sigma\in A_n$ such that


*

*$\sigma$ has only one extension in $A_{n+1}$

*and only one extension in $A_{n+2}$ 

*and so on,
that is, from the perspective of $\sigma$ the $A_n$s stop growing at all.
Exercise: regardless of what $T$ is, there can be only countably many isolated paths. This is because we can associate each isolated path to a finite binary sequence which isolates it ...
OK, so this gives us our first result:

If every element of $\mathcal{A}$ is isolated, then $\mathcal{A}$ is countable.

But that's not the only way that $\mathcal{A}$ could be countable! For example, let $T$ be the tree of finite binary sequences not containing "$10$." There are only countably many of these - they're either the zero-sequence or a sequence of the form $000...000111111111...$. But if you draw the tree $T$, you'll see that the element $0000000...$ is not isolated! It's the "limit" of other elements: namely, in an appropriate sense $0111..., 00111..., 000111..., ...$ approaches the zero-sequence.
How will we account for this? Simple - we keep pruning! The all-zeroes path becomes isolated once we remove the isolated paths. And we can keep going: we remove the paths that become isolated once we remove the isolated paths, and then we remove the paths that become isolated once we remove those paths, and so on.
At this point, it might be good to see another example:

Consider the tree $T$ of finite binary sequences such that: if they have at least two "$1$," then there is no $0$ following the second $1$. That is, they look like a string of zeroes, then a one, then a string of zeroes, and then unending ones. By "string" here I mean possible-empty, possibly-infinite; so e.g. the all-zeroes sequence is a path through $T$, as is the all-$1$s sequence. This tree looks a lot like infinitely many copies of the tree from the previous example, "glued together" along a path.

It's a very good exercise to try to draw this tree. In this tree, we have lots of isolated paths, lots of limits-of-isolated-paths paths, and one limit-of-limits-of-isolated-paths path. So the tree "vanishes" after we prune three times.
We can go into the transfinite, too: after all the finite steps, we take "what's left" - that's a new tree! And then we can prune its isolated paths, and so on.
This is the Cantor-Bendixson process. It can be hard to visualize at first, but it's quite useful. And a very nice theorem states that this process characterizes when $\mathcal{A}$ is uncountable:


*

*If $\mathcal{A}$ is countable, then at some (countable) stage the entire tree disappears.

*If $\mathcal{A}$ is uncountable, then our tree never disappears; in fact, at some (countable) stage, we're left with a perfect tree - a (nonempty) tree with no isolated paths at all! *(This tree is called the perfect kernel of the original tree, and the set of paths through it is called the perfect kernel of $\mathcal{A}$.)* An example of a perfect tree is the full binary tree, $2^{<\omega}$.
So whether $\mathcal{A}$ is countable or not is characterized exactly by the Cantor-Bendixson process. Unfortunately, this is rather complicated, and definitely not what you were hoping for - but there it is.
