# 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?

• Is the limit of the $R_n$ their union, or do you mean something else? – Andrés E. Caicedo Jun 15 '17 at 13:50
• How do you figure that if $|R_n|=3^n$ then $R$ is uncountable? Consider for instance $R_n=\{ 1,2,\dots,3^n \}$; presumably the set-theoretic limit of that is just $\mathbb{N}$. – Ian Jun 15 '17 at 13:50
• Anyway, if limits are just unions: $\bigcup_{n\in\mathbb N}R_n$ is uncountable if and only if at least one of the $R_n$ is uncountable. In particular, a countable union of finite sets is always countable. – Andrés E. Caicedo Jun 15 '17 at 13:52
• Ok, so what precisely do you mean by limit? What are these sets? (Arbitrary sets? Sets of reals?) What precisely does $|A_n|$ mean? (Cardinality? Measure?) Does the notation mean that $n$ ranges over $\mathbb N$? – Andrés E. Caicedo Jun 15 '17 at 13:53
• @Ian: Actually, this works better if you don't use sets inside your limit, but their cardinality. Clearly, the sequence $3^n$ is a subsequence of the sequence $n$; so if the limit of $n$ is $\aleph_0$, the limit of $3^n$ cannot be different. So what we have here is a discontinuity. (Which, of course, is not a very surprising thing when you think about it... why should cardinality be continuous?) – Asaf Karagila Jun 15 '17 at 14:01

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.

• Incidentally, every perfect tree has continuum-many paths; this means that whenever I have a set of paths through a binary tree, it's either countable or has size continuum, regardless of whether the continuum hypothesis holds. The set of paths through a given tree is a closed set, but we can prove this for Borel sets as well. This is the beginning of descriptive set theory; the idea is that these sets are "too nice" to have weird properties - like being counterexamples to CH, or being nonmeasurable, or ... – Noah Schweber Jun 15 '17 at 14:39
• Thanks a lot. This was exactly what I needed. I got a bit confused but now I think i understand it – Pedro Jun 15 '17 at 14:54
• @Pedro Glad I could help! There's a lot to digest here - this was historically the beginning of a whole subfield of mathematical logic, and has a lot of technical nuance - so definitely let me know if there's a point you'd like me to explain better, I'll be happy to do so! – Noah Schweber Jun 15 '17 at 14:55
• I'll try to apply all of this to the proof I have in mind. If I get stuck how can i make you know? (if you want of course) – Pedro Jun 15 '17 at 15:00
• Just add a comment here, I'll be automatically notified. (I can't guarantee that I'll have time to help, but I think there's a decent chance I will.) And of course, if I can't help, you could ask it as a question here ... – Noah Schweber Jun 15 '17 at 15:05