Nicolás Matte Bon asked me if I have a reference for which Cantor-Bendixson ranks of subshifts can be realized. I do not have a reference, but I always assumed I know the answer (countable and finite ordinals in the countable case, and any countable ordinal in general), and that the constructions are easy. Trying to explain this to him, I realized I do not actually know a construction in the general case.

I’ll attempt a proof from scratch, but first a brief discussion of literature: First, this result may well be in the literature directly. I would not be surprised if e.g. the result can be obtained directly by relativizing the known results for effective -subshifts, see [1]. Unfortunately I never read this paper in much detail, and don’t know the exact construction.

I can’t help to also tell the “fascinating” story of the ranks of -SFTs, which are now fully understood. The final answer is for computable (and of course the finite ordinals), see [2] (by Törmä). The problem arose from [3], and was “almost” solved in Jeandel and Vanier [4], who obtained all computable ordinals with a finite (and not too large) constant . We optimized the constant to 5 in [5] by using counter machines instead of Turing machines, and in his thesis Törmä used one-counter machines to get it down to 4. He finally used a result from [6] to get the final answer in [2]. The optimality in turn is from [7], and is also a non-trivial result.

Ok, onto the results. We’ll use the Von Neumann model for ordinals, so and are synonymous. Here we define the *Cantor-Bendixson rank* of a subshift (shift-invariant compact subset) to be the smallest ordinal such that , where for ordinal is defined by removing isolated points transfinitely.

The final set is perfect. Since a perfect set with at least two points is uncountable, if the original subshift is countable (i.e. has countably many points), the final set is empty; otherwise it is still uncountable (the rank must be countable since subshifts are second-countable, and thus we remove only countably many countable sets in the derivation process).

For countable subshifts the characterization is easy to prove:

Theorem. The Cantor-Bendixson ranks of countable -subshifts are precisely the finite ordinals, and for limit ordinals .

Suppose is a countable subshift with rank . If is a limit ordinal, then is a decreasing intersection of closed sets. That’s impossible by the descending chain condition for compact sets (note that each is compact).

If where is a limit ordinal, then is a finite subshift, thus of finite type, and a finite type subshift cannot be the decreasing intersection of subshifts (note that each is compact), since at some point you already forbid a set of forbidden patterns.

So an infinite rank is of the form for some , and since the topology is second-countable, is a countable ordinal.

For the construction (for the case of infinite or large ranks), consider a closed subset of Cantor space . Let be the Cantor-Bendixson rank (again it’s clear it cannot be a limit ordinal), and the last nonempty step.

Since is finite, we can homeomorph to a set of points of finite support (meaning finitely many s), and all other points to points of infinite support. (To do this, first observe that in any clopen set we can clearly move any single point to a finite-support point by adding a constant configuration cellwise mod to the tail, and then we can do this separately in a clopen partition separating the points of . Then to make other points infinite support, first intersperse s between coordinates of all points, and then have a homeomorphism start flipping all s to as soon as the prefix differs from all points of .)

We may also suppose that has at least two elements (by possibly replacing by a direct union initially) and then we may assume two of the points in are and .

After this preprocessing, code each as

,

take the smallest subshift containing all these points. This is just the orbits of the , and the point of all zeroes (the limit points , are directly of the form by our preprocessing). Now it’s easy to see that points disappear exactly according to the derivative process of . So contains no points of the form , thus . On the other hand contains the all-zero point.

For any , we can take as take the ordinal with the order topology. By one standard definition of countable ordinals this embeds in the interval and by topology it embeds in Cantor space. Its CB-rank is , so the previous construction gives rank .

For finite , the above construction gives all , and are trivial to obtain. Square.

For the general (and the uncountable) case, I didn’t find a simple construction, and can only supply a proof sketch which I found convincing enough. If you know a simpler proof, or another proof, or a reference, or of a mistake in this argument, or other, I’d be interested in hearing it. I may make another attempt at a more detailed proof at some later point.

Theorem. The Cantor-Bendixson ranks of uncountable -subshifts are precisely the countable ordinals.

Proof sketch. The rank must be countable for the same reason as in the previous theorem.

For the construction, take any countable ordinal . Biject , and if has , then pick a word which is not in the Fibonacci subshift but is in its th SFT approximation.

We can furthermore ensure, by picking very long such words, that the words for distinct ordinals look very different. Concretely, we want to be able to find a point where appears in the center, which is in the th SFT approximation, and which quickly converges to the Fibonacci subshift on both sides, e.g. the tails are literally Fibonacci; and we want that in these points no other appears. This is easy to achieve by picking the words very long and random and in increasing order of deliberately avoiding previous ones.

Now pick some point in the Fibonacci subshift. Note that the SFT approximations of the Fibonacci subshift are transitive. Now construct a point for each in a dovetailing fashion: to construct , put a single at the origin, continue it to the left by a Fibonacci tail, and continue it to the right by transitioning it arbitrarily close to each for infinitely many times, in arbitrary order.

The crucial points are that

- appears exactly once in this point, and
- between the “dives” into approximating points we quickly transition into words from the Fibonacci subshift.
- between these dives, we have longer and longer Fibonacci words in between,

The first point is easy to achieve by how we chose the words , and the second and third are easy as well since the points have arbitrarily long words from the Fibonacci subshift in both tails, which we can continue with their natural continuations in the Fibonacci subshift, when we want to transition from one approximation to another.

Now the Cantor-Bendixson derivative removes points precisely after all smaller points have been removed, so you remove all of them precisely at the th step. At that step, what you have left is the Fibonacci subshift, which no longer changes (a Fibonacci subshift is going to be there automatically, or you can just stick it in there explicitly if you don’t believe me). Square.

References:

[1] Douglas Cenzer, Ali Dashti, Ferit Toska & Sebastian Wyman*.* **Computability of Countable Subshifts in One Dimension.** *Theory Comput Syst* **51**, 352–371 (2012). https://doi.org/10.1007/s00224-011-9358-z

[2] Ilkka Törmä: **Cantor-Bendixson ranks of countable SFTs.** CoRR abs/1803.03605 (2018).

[3] Alexis Ballier, Bruno Durand, Emmanuel Jeandel: **Structural aspects of tilings.** STACS 2008.

[4] Emmanuel Jeandel, Pascal Vanier: **-sets and tilings.** Theory and Applications of Models of Computation, 2011, Springer.

[5] Ville Salo, Ilkka Törmä: **Constructions with countable subshifts of finite type.** Fundamenta Informaticae, 2013.

[6] Peter Cholak and Rod Downey. **On the Cantor-Bendixon rank of recursively enumerable sets.** J. Symbolic Logic, 58(2):629–640, 1993.

[7] Alexis Ballier and Emmanuel Jeandel. **Structuring multi-dimensional subshifts.** ArXiv e-prints, September 2013