Prove that these Sets Containing Infinitely Many Incompressible Strings Exist

Question

We define a set $A$ to be special if: $$\liminf_{n \to \infty} \frac{|A^{\leq n}|}{n} = 0$$ I want to prove that there are special recursive sets that contain infinitely many incompressible strings.

Particularly, I have been told that if this problem is approached correctly, it is nearly trivial to solve; it can be solved particularly neatly. My question is what this approach would be --- I'm fairly certain I can just explicitly construct an example of such a set, but is there a better way to do it?

Answer 1

This argument is probably invalid.

I'm not sure that is your nice solution, but you can do it as follows

• Let $s = |\Sigma|$ be the size of the alphabet.
• There are $s^n-1$ strings of length $<n$ and $s^n$ strings of length $n$, so for any $n$ there is at least one incompressible string.
• Let $(a_k)_{k \in N} \subset \Sigma^*$ be a sequence of these strings for any length, then $A = \{a_{k^2} \mid k \in \mathbb{N}\}$ would be your special set.

I hope this helps $\ddot\smile$